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.

  • 0
    Your last equality is plainly false...2011-03-10
  • 0
    I think that's why he says "This is where I get stuck"!2011-03-10
  • 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
    (n+1)*(n+1)! is the part that I don't "see" where it comes from2011-03-10
  • 0
    @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?)2011-03-10
  • 0
    @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$2011-03-10
  • 0
    I need to review what the factorial means again.2011-03-10
  • 1
    @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.2011-03-10
  • 0
    @lampShade: As for the factorial, $0!=1$, $1!=1$, and $n!=1\times2\times\cdots\times n$, so $(k+1)!=(k!)\times(k+1)$.2011-03-10
  • 0
    @Arturo Magidin: Is there a way to communicate privately with other users? If so, could you PM how your comments contain linebreaks? When I hit "enter", it submits my comment!2011-03-10
  • 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