Prove by Mathematical Induction: $1(1!) + 2(2!) + \cdot \cdot \cdot +n(n!) = (n+1)!-1$

Question

Prove by Mathematical Induction . . .

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

I tried solving it, but I got stuck near the end . . .

a. Basis Step:

$(1)(1!) = (1+1)!-1$

$1 = (2\cdot1)-1$

$1 = 1 \checkmark$

b. Inductive Hypothesis

$1(1!) + 2(2!) + \cdot \cdot \cdot +k(k!) = (k+1)!-1$

Prove k+1 is true.

$1(1!) + 2(2!) + \cdot \cdot \cdot +(k+1)(k+1)! = (k+2)!-1$

$\big[RHS\big]$

$(k+2)!-1 = (k+2)(k+1)k!-1$

$\big[LHS\big]$

$=\underbrace{1(1!) + 2(2!) + \cdot \cdot \cdot + k(k+1)!} + (k+1)(k+1)!$ (Explicit Last Step)

$= \underbrace{(k+1)!-1}+(k+1)(k+1)!$ (Inductive Hypothesis Substitution)

$= (k+1)!-1 + (k+1)(k+1)k!$

$= (k+1)k!-1 + (k+1)^{2}k!$

My [LHS] looks nothing like my [RHS] did I do something wrong?

EDIT:

$ = (k+1)k! + (k+1)^2k! -1 $

$ = (k+1)(k!)(1 + (k+1))-1$

$ = (k+1)(k!)(k+2)-1 = (k+2)(k+1)k!-1$

Answer 1

Your LHS may not look much like your RHS yet, but that's because you haven't finished getting it into the simplest possible form. You have $(k+1)k! - 1 + (k+1)^2 k!$. You're looking to get something minus $1$, so that's somewhat promising. Now what factors do the other two terms (the ones involving $k$) have in common?

Answer 2

There is a mistake in the [LHS], it should look like this:

$$ \underbrace{1(1!) + \ldots + k(k!)}_{=(k+1)! - 1} + (k+1)(k+1)! = \ldots $$

Answer 3

$$1(1!) + 2(2!) + \cdot \cdot \cdot +n(n!) = (n+1)!-1$$ then $$1(1!) + 2(2!) + \cdot \cdot \cdot +n(n!)+(n+1)(n+1)! =(n+1)!-1+(n+1)(n+1)!=$$ $$(n+1)!(n+1+1)-1=(n+2)!-1=((n+1)+1)!-1$$

Answer 4

It's a special case of telescopic induction. This post has a very short and simple inductive proof of

Theorem $\rm\displaystyle\,\ \sum_{i\,=\,1}^n f(i) = g(n)\iff g(1) = f(1)\ {\rm and}\ g(n\!+\!1)-g(n) = f(n\!+\!1)\ $ for $\,n \ge 1.$

Applied to your case, where $\rm\,f(n) = n n!\:$ and $\rm\:g(n) = (n+1)!-1,\,$ we have $\rm\: g(1)=1 = f(1),\:$ and

$$\begin{eqnarray}\rm g(n\!+\!1)-g(n) &=&\rm (n\!+\!2)!-1-((n\!+\!1)!-1) \\ &=&\rm (n\!+\!2)!\,-\,(n\!+\!1)! \\ &=&\rm (n\!+\!2 -1)(n\!+\!1)! \\ &=&\rm (n\!+\!1)(n\!+\!1)! \\ &=&\rm f(n\!+\!1) \end{eqnarray}$$

That completes the proof using the theorem. This method works quite widely for inductive proofs involving sums and products. You can find many more examples of telescopy and related results in other answers here.