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.