Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
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 –  leetmaschine Nov 13 '13 at 3:33
add comment

4 Answers

up vote 4 down vote accepted

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?

share|improve this answer
    
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
add comment

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
thanks for the insight. i will study this more. –  rbtLong Feb 14 '13 at 22:56
add comment

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

share|improve this answer
    
thanks for the catch –  rbtLong Feb 12 '13 at 22:31
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.