3

How would you prove the following using induction. n is a non negative integer

$$1+\sum_{i=1}^n i i!=(n+1)!$$

This be what I did

base case let $n=3$

$$1+1+4+18=(3+1)!$$

$24=24$

Hypothesis step let $n=k$

$$1+\sum_{i=1}^k i (i!)=(k+1)!$$

Induction step let $n=k+1$

$$1+\sum_{i=1}^{k+1} i (i!)=(k+1+1)!$$

so start on the left hand side and get

$$1+\sum_{i=1}^k i (i!)+(k+1(k+1)!)=(k+1)!+(k+1(k+1)!$$

and I am stuck.

Aaron Maroja
  • 17,571
Fernando Martinez
  • 6,698
  • 19
  • 74
  • 108
  • Your final line should be $$1+\sum_{i=1}^k i (i!)+(k+1)(k+1)!=(k+1)!+(k+1)(k+1)!$$ and that is $(k+1)!(1+(k+1))=(k+2)!$ – Henry Jan 24 '15 at 21:05

2 Answers2

3

$$\begin{align}1 + \sum_{i=1}^{k+1} ii!& = \color{green}{1 + \sum_{i=1}^{k} ii!} + (k+1)(k+1)! \\&=\color{green}{(k+1)!} + (k+1)(k+1)! \\&= (k+1 +1 )(k+1)! \\&= (k+2)(k+1)! \\&= (k+ 2)! \end{align}$$

Aaron Maroja
  • 17,571
0

First, show that this is true for $n=1$:

  • $1+\sum\limits_{i=1}^{1}i\cdot{i!}=(1+1)!$

Second, assume that this is true for $n$:

  • $1+\sum\limits_{i=1}^{n}i\cdot{i!}=(n+1)!$

Third, prove that this is true for $n+1$:

  • $1+\sum\limits_{i=1}^{n+1}i\cdot{i!}=1+\sum\limits_{i=1}^{n}i\cdot{i!}+(n+1)\cdot(n+1)!$

  • $1+\sum\limits_{i=1}^{n}i\cdot{i!}+(n+1)\cdot(n+1)!=(n+1)!+(n+1)\cdot(n+1)!$ assumption used here

  • $(n+1)!+(n+1)\cdot(n+1)!=(n+1)!\cdot(1+n+1)$

  • $(n+1)!\cdot(1+n+1)=(n+1)!\cdot(n+2)$

  • $(n+1)!\cdot(n+2)=(n+2)!$

barak manos
  • 43,109