# Thread: Prove recurrence relation equals sum of permutations

1. ## Prove recurrence relation equals sum of permutations

OK, I am stuck on this MI proof of the following:

Define $a_{0}=1$ and for $n\geq1$, define $a_{n}=na_{n-1}+1$.
Prove: For $n\geq0 a_{n} = \sum_{j=0}^{n}(n)_{j}$.

First prove the base case for n=0. By definition $a_{0}$=1. Now show $\sum_{j=0}^{0}(0)_{j}=\left(0\right)_{0}=1$.

This proves the base case.

Now assume $a_{k}=ka_{k-1}+1=\sum_{j=0}^{k}(k)_{j}$. (IHYP)

We need to show that $a_{k+1}=(k+1)a_{k}+1=\sum_{j=0}^{k+1}(k+1)_{j}$.

I can manipulate the left hand side. What I'm having a problem with is the permutation on the RHS.

I can take the k+1 term out which gives (k+1)! but I'm still left with the sum of $(k+1)_{j}$. I can factor out $\frac{(k+1)}{(k+1-j)}(k)_{j}$ but that doesn't seem to make sense either.

Could someone give me a hint on how to get rid of the $(k+1)_{j}$ in the sum?

Thanks.

2. Originally Posted by oldguynewstudent
OK, I am stuck on this MI proof of the following:

Define $a_{0}=1$ and for $n\geq1$, define $a_{n}=na_{n-1}+1$.
Prove: For $n\geq0 a_{n} = \sum_{j=0}^{n}(n)_{j}$.

First prove the base case for n=0. By definition $a_{0}$=1. Now show $\sum_{j=0}^{0}(0)_{j}=\left(0\right)_{0}=1$.

This proves the base case.

Now assume $a_{k}=ka_{k-1}+1=\sum_{j=0}^{k}(k)_{j}$. (IHYP)

We need to show that $a_{k+1}=(k+1)a_{k}+1=\sum_{j=0}^{k+1}(k+1)_{j}$.

I can manipulate the left hand side. What I'm having a problem with is the permutation on the RHS.

I can take the k+1 term out which gives (k+1)! but I'm still left with the sum of $(k+1)_{j}$. I can factor out $\frac{(k+1)}{(k+1-j)}(k)_{j}$ but that doesn't seem to make sense either.

Could someone give me a hint on how to get rid of the $(k+1)_{j}$ in the sum?

Thanks.
Hint!

$\sum_{j=0}^{n}(n)_{j}=2^n$

Edit: Is $(n)_{j}$ mean n choose j, ${n\choose{j}}$?

3. Originally Posted by Also sprach Zarathustra
Hint!

$\sum_{j=0}^{n}(n)_{j}=2^n$

Edit: Is $(n)_{j}$ mean n choose j, ${n\choose{j}}$?
$(n)_{j}$ is nPj or the j permutaions of n objects. Or the number of j lists without repetition from an n-set.