# Proof by induction: $\sum\limits_{i=0}^n i \cdot i! = (n+1)!-1$

Let n be a positive natural number , $n\ge 0$, then. $\displaystyle\sum_{i=0}^n i \cdot i!= (n+1)!-1$

Here is my attempt.I'm not going to write the base case because I understand that part.

Assuming $\displaystyle\sum_{i=0}^n i \cdot i!= (n+1)!-1$ is true. We wish to show.

$\displaystyle \sum_{i=0}^{n+1} i \cdot i!= (n+2)!-1$. Thus.

$\displaystyle\sum_{i=0}^{n+1} i \cdot i!= (\sum_{i=0}^n i \cdot i!)$ This is where I get stuck.

-
Your last equality is plainly false... –  Mariano Suárez-Alvarez Mar 10 '11 at 3:47
I think that's why he says "This is where I get stuck"! –  The Chaz 2.0 Mar 10 '11 at 4:29
possible duplicate of Summation of a factorial –  t.b. Sep 16 '11 at 12:25

Your last step should read $$\sum_{i=0}^{k+1} \left( i \cdot i! \right)= \sum_{i=0}^k \left(i \cdot i!\right) + (k+1)(k+1)!$$ Now use your induction assumption to get $$\sum_{i=0}^{k+1} \left(i \cdot i! \right)= (k+1)! - 1 + (k+1)(k+1)! = (k+1)! (k+2) -1 = (k+2)! - 1$$

-

HINT $\:$ First trivially inductively prove the Fundamental Theorem of Difference Calculus

$$\rm\ F(n)\ =\ \sum_{i\:=\:0}^n\ f(i)\ \ \iff\ \ \ F(n) - F(n-1)\ =\ f(n),\quad\ F(0) =\: f(0)$$

Yours is $\rm\ F(n)-F(n-1)\ =\ (n+1)! - n!\ =\ (n+1 -1)\ n!\ =\ n\ n!\ =\ f(n)\:,\:$ $\rm\ F(0) = 0 = f(0)\:.$

Note that by employing the Fundamental Theorem we have reduced the proof to the trivial verification of an equation. No ingenuity is required. In fact for hyperrational functions like factorials it is so trivial that there are algorithms that can mechanically verify such equalities.

Note that the proof of the Fundamental Theorem is much more obvious than that for your special case because the telescopic cancellation is obvious at this level of generality, whereas it is usually obfuscated in most specific instances. For further discussion see my many posts on telescopy.

-

Well, your last equality isn't true! The left hand side has $n+2$ summands, and you dropped the biggest one on the right. What happened to $(n+1)*(n+1)!$? No wonder you got stuck...

Everything is correct until "Thus". Now, write the $n+1$ case as "the $n$ case and a little extra", so you can apply the induction hypothesis to the $n$ case. Then see if you can manipulate what you obtain into the formula you want.

Here you have $$\sum_{i=0}^{n+1}(i*i!) = \left(\sum_{i=0}^n(i*i!)\right) + \Biggl((n+1)*(n+1)!\Biggr).$$ Now apply the induction hypothesis to the first summand, and see what you can get.

-
(n+1)*(n+1)! is the part that I don't "see" where it comes from –  lampShade Mar 10 '11 at 3:52
@lampShade: The sum has to go from $i=0$ all the way to $i=n+1$. If you only add the terms up to $i=n$, then you are still missing the term you get when $i$ is $n+1$. So you have to add it in to make sure the right hand side is identical to the left hand side of that equal sign. What does $i*i!$ equal when $i=n+1$? (Perhaps a simpler question is: do you understand what the $\sigma$ symbol means?) –  Arturo Magidin Mar 10 '11 at 3:54
@lampshade: Your summation on the left side of the last step runs from $0$ to $n+1$ whereas the summation on the right side of the last step runs from $0$ to $n$ –  user17762 Mar 10 '11 at 3:54
I need to review what the factorial means again. –  lampShade Mar 10 '11 at 3:58
@lampShade: This is not even about the factorial: it's about the summation. (The factorial will come up at the next step). Simply put:$$\sum_{i=0}^kf(i) = f(0)+f(1)+f(2)+\cdots+f(k),$$where $f$ is any function; so $$\sum_{i=0}^{n+1}f(i)=f(0)+f(1)+\cdots+f(n)+f(n+1) = \Bigl(f(0)+f(1)+\cdots+f(n)\Bigr)+f(n+1)$$ $$= \Bigl(\sum_{i=0}^nf(i)\Bigr) +f(n+1).$$Nothing to do with the factorial, everything to do with the sum. –  Arturo Magidin Mar 10 '11 at 4:02