Proof by induction - stuck on n+1

[rachaelmw]

The problem is thus:

Show that $\displaystyle I_n = A_n + eB_n$ where $\displaystyle A_n = (-1)^{n+1} n!$ and $\displaystyle B_n = \sum_{k=0}^n (-1)^k \frac{n!}{(n-k)!}$

I derived the results $\displaystyle I_n = e - nI_{n-1}$ and $\displaystyle I_n =\int_0^1 e^t t^n dt$ from a previous problem.

So, for the first step of induction, I must prove that the equation $\displaystyle I_n = A_n + eB_n$ holds where n=1. This is mostly plug and play and results in:
$\displaystyle I_1 = (-1)^{1+1} 1! + e \sum_{k=0}^1 (-1)^k \frac{1!}{(1-k)!}$
$\displaystyle = 1(1) + e(0)$
$\displaystyle = 1$

Alright, so I know that the equation holds for n=1. I must now prove that it holds for n+1, but I have no idea how to add n+1 to each side. I know that $\displaystyle I_{n+1} = e - (n+1)I_n$ in the end, but I'm obviously screwing up somewhere on the right hand side. I know that $\displaystyle B_n$ expands to $\displaystyle 1 - n + n(n-1) - n(n-1)(n-1) + ...+ (-1)^n n!$. So I can add $\displaystyle -1^{n+1} (n+1)!$ to each side as the next term in that particular series, but what about the $\displaystyle A_n$ part? Any help is appreciated.

Thanks,
Rachael

 

[stapel]

Alright, so I know that the equation holds for n=1. I must now prove that it holds for n+1....

Are you perhaps skipping a step...? Don't you need to assume something for "n = k", before moving on to proving the formula for "n = k + 1"...?

There is the assumption step:

. . . . .$\displaystyle I_k\, =\, A_k\, +\, eB_k\, =\, (-1)^{k+1} k!\, +\, e\,\sum_{i=0}^k\, (-1)^i\, \frac{k!}{(k\,-\,i)!}$

Then there is the proving step, in which you (usually) use the assumption step. In this case, you would have:

. . . . .$\displaystyle I_{k+1}\, =\, e\, -\, (k\, +\, 1)I_k\, =\, e\, -\, (k\, +\, 1)\, \left[(-1)^{k+1} k!\, +\, e\,\sum_{i=0}^k\, (-1)^i\, \frac{k!}{(k\,-\,i)!}\right]$

Simplifying and rearranging a bit, we can get:

. . . . .$\displaystyle e\, +\, (-1)(-1)^{k+1}(k\, +\, 1)\,k! + \,(-1)(k\, +\, 1)\, e\,\sum_{i=0}^k\, (-1)^{i}\, \frac{k!}{(k\,-\,i)!}$

. . . . .$\displaystyle e\, +\, (-1)^{k+2}(k\, +\, 1)! + \, (-1)\,e\,\sum_{i=0}^k\, (-1)^{i}\, \frac{(k\, +\, 1)\, k!}{(k\,-\,i)!}$

. . . . .$\displaystyle e\, +\, A_{k+1} + \,(-1)\, e\,\sum_{i=0}^k\, (-1)^{i}\, \frac{(k\, +\, 1)!}{(k\,-\,i)!}$

Somehow, we need to convert the sum of e and the summation above into the expression for eB [sub:468wocu2]k+1[/sub:468wocu2], which should be:

. . . . .$\displaystyle eB_{k+1}\, =\,e\,\sum_{i=0}^{k+1}\, (-1)^i\, \frac{(k\, +\,1)!}{(k\,+\,1\,-\,i)!}$

Working backwards from the last line above, I start with:

. . . . .$\displaystyle e\,\sum_{i=0}^{k+1}\, (-1)^i\, \frac{(k\, +\,1)!}{(k\,+\,1\,-\,i)!}$

Break off the zero-th term:

. . . . .$\displaystyle e\,(-1)^0\,\frac{(k\,+\,1)!}{((k\, +\, 1)\, -\, 0)!}\, +\, e\,\sum_{i=1}^{k+1}\, (-1)^i\, \frac{(k\, +\,1)!}{(k\,+\,1\,-\,i)!}$

Reset the summation counter to 0 and rejig the summation terms so the values will be the same as with the previous indexing (and remembering that "k + 1" is here a constant value):

. . . . .$\displaystyle e\,(1)\,\frac{(k\,+\,1)!}{(k\, +\, 1)!}\, +\, e\,\sum_{i=0}^{k}\, (-1)^{i+1}\, \frac{(k\, +\,1)!}{(k\,-\,i)!}$

Then split off the extra factor of -1 from inside the summation:

. . . . .$\displaystyle e\, +\,(-1)\, e\,\sum_{i=0}^{k}\, (-1)^{i}\, \frac{(k\, +\,1)!}{(k\,-\,i)!}$

Can you work with that? :wink:

Eliz.