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.