3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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)!$ $\endgroup$
    – Henry
    Jan 24, 2015 at 21:05

2 Answers 2

Reset to default
3
$\begingroup$

$$\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}$$

$\endgroup$
2
  • $\begingroup$ How do yo go from $(k+1)!+(k+1)(k+1)!$ to $(k+1+1)(k+1)!$ $\endgroup$
    – Fernando Martinez
    Jan 24, 2015 at 20:28
  • 1
    $\begingroup$ factor $(k+1)!$ out $\endgroup$
    – Aaron Maroja
    Jan 24, 2015 at 20:29
0
$\begingroup$

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)!$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .