# 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 $\displaystyle a_{0}=1$ and for $\displaystyle n\geq1$, define $\displaystyle a_{n}=na_{n-1}+1$.
Prove: For $\displaystyle n\geq0 a_{n} = \sum_{j=0}^{n}(n)_{j}$.

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

This proves the base case.

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

We need to show that $\displaystyle 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 $\displaystyle (k+1)_{j}$. I can factor out $\displaystyle \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 $\displaystyle (k+1)_{j}$ in the sum?

Thanks.

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

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

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

This proves the base case.

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

We need to show that $\displaystyle 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 $\displaystyle (k+1)_{j}$. I can factor out $\displaystyle \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 $\displaystyle (k+1)_{j}$ in the sum?

Thanks.
Hint!

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

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

3. Originally Posted by Also sprach Zarathustra
Hint!

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

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