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

Define

and for

, define

.

Prove: For

.

First prove the base case for n=0. By definition

=1. Now show

.

This proves the base case.

Now assume

. (IHYP)

We need to show that

.

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

. I can factor out

but that doesn't seem to make sense either.

Could someone give me a hint on how to get rid of the

in the sum?

Thanks.