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

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$

-
I like the name Mathematica Induciton. – GEdgar Feb 12 '13 at 22:29
my mistake . . . – rbtLong Feb 12 '13 at 22:51
Under this section, how do you get the 2nd line? In particular the (1 +(k+1)). 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 – user108455 Nov 13 '13 at 3:33

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?

-
ah! thanks i figured it out! – rbtLong Feb 12 '13 at 22:21
It looks odd now that you edited the question, so that my answer looks like I didn't see the whole thing or something. But anyway, the main thing is, you figured it out. =] – Tara B Feb 12 '13 at 22:22

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.

-
thanks for the insight. i will study this more. – rbtLong Feb 14 '13 at 22:56

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

-
wow thanks! . . . this looks like a much shorter solution, but i wonder if i will get in trouble for not using k and not invoking the inductive hypothesis step. anyway i will practice this as an alternative. – rbtLong Feb 12 '13 at 22:38

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

-
thanks for the catch – rbtLong Feb 12 '13 at 22:31