3
$\begingroup$

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.

  • 1
    possible duplicate of [Summation of a factorial](http://math.stackexchange.com/questions/18576/summation-of-a-factorial)2011-09-16

3 Answers 3

1

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$

4

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.

1

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.

  • 0
    @The Chaz: My comments don't contain line breaks: they contain displayed formulas (with the usual `$$`). If you go to my user page in this site, you'll find how to contact me through regular e-mail.2011-03-10