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.