4
$\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.

$\endgroup$
3
  • $\begingroup$ Your last equality is plainly false... $\endgroup$
    – Mariano Suárez-Álvarez
    Commented Mar 10, 2011 at 3:47
  • $\begingroup$ I think that's why he says "This is where I get stuck"! $\endgroup$
    – The Chaz 2.0
    Commented Mar 10, 2011 at 4:29
  • 2
    $\begingroup$ possible duplicate of Summation of a factorial $\endgroup$
    – t.b.
    Commented Sep 16, 2011 at 12:25

3 Answers 3

Reset to default
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ (n+1)*(n+1)! is the part that I don't "see" where it comes from $\endgroup$
    – lampShade
    Commented Mar 10, 2011 at 3:52
  • $\begingroup$ @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?) $\endgroup$
    – Arturo Magidin
    Commented Mar 10, 2011 at 3:54
  • $\begingroup$ @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$ $\endgroup$
    – user17762
    Commented Mar 10, 2011 at 3:54
  • $\begingroup$ I need to review what the factorial means again. $\endgroup$
    – lampShade
    Commented Mar 10, 2011 at 3:58
  • 1
    $\begingroup$ @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. $\endgroup$
    – Arturo Magidin
    Commented Mar 10, 2011 at 4:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .