Proving $\sum_{k=1}^n k\cdot k! = (n+1)!-1$ without using mathematical Induction.

Question

Possible Duplicate:
Summation of a factorial

This equation is given:
$$ 1\cdot1! + 2\cdot2! + 3\cdot3! + \ldots + n\cdot n! = (n+1)! - 1 $$

I've solved it using mathematical induction but I'm curious what could be the other possible ways to prove it.

Answer 1

$$\begin{align*}1\cdot 1! &+ 2\cdot 2! + 3\cdot 3! + \dots + n\cdot n! \\ &=(2-1)\cdot 1! + (3-1)\cdot2! + (4-1)\cdot 3! + \dots + (n+1-1)\cdot n! \\ &=2! - 1! + 3! - 2! + 4! - 3! + \dots + (n+1)! - n! \\ &=(n+1)! - 1 \end{align*}$$

Answer 2

Both sides are solutions of $\,f(n\!+\!1)-f(n) = (n\!+\!1)(n\!+\!1)!,\ f(0) = 0,\:$ so they are equal by the uniqueness theorem for first-order recurrences (fundamental theorem of difference calculus), which has a trivial one-line inductive proof (expressed in the language of sums vs. recurrences it boils down to telescopic cancellation of sums of differences).

As I often emphasize, uniqueness theorems provide powerful tools for proving equalities.

Generally, for functions defined by mathematical induction ("inductive or recursive definition"), see the award-winning Monthly exposition by Leon Henkin, On mathematical induction, AMM, 1960.

Remark $\ $ Note that some of the other answers simply give the standard inductive proof, using ellipses rather than a formal inductive argument. This is most certainly not a "proof without using mathematical induction". These proofs are all standard mechanical applications of telescopy.

A proof that a statement is true for all integers must - at some point or another - employ mathematical induction. The use of induction may not be obvious - it may be hidden (far) down the inference chain in some other theorem or lemma invoked, as in said uniqueness theorem for recurrences (difference equations).

The idea of using uniqueness theorems certainly does differ from the standard inductive proof. Indeed, the uniqueness theorem for higher-order recurrences may be viewed as a generalization of the vivid telescopic cancellation that occurs in the first-order case. One can find some examples in the linked posts.

Answer 3

First we notice that $m\cdot m!=m!\cdot m=m!\cdot(m+1-1)=m!\cdot(m+1)-m!\cdot1=(m+1)!-m!$, so after plugging this, we get:

$\begin{align*} \sum_{i=1}^{n}{\left(i\cdot i!\right)}&=1\cdot 1!+2\cdot 2!+3\cdot 3!+\cdots+(n-1)\cdot(n-1)!+n\cdot n!\\ &=(1+1)!-1!+(2+1)!-2!+(3+1)!-3!+\cdots+(n-1+1)!-(n-1)!+(n+1)!-n! \\ &=2!-1!+3!-2!+4!-3!+\cdots+(n+1)!-n!\\ &=(n+1)!-1. \end{align*}$

Answer 4

You could also prove it by "story" or interpretation. Right side means: how can you order $n+1$ people such that there are not sorted ascending by height. The left side means, you could do one of:

• pick anybody but the smallest person (you have $n$ options) for the first place, and order the rest in $(n+1-1)!$ ways, total $n\cdot n!$,
• put the shortest one at the first place and then anybody but the second smallest person (you have $n-1$ options here) for the second place, then order the rest in $(n+1-2)!$ ways, total $(n-1)\cdot (n-1)!$,
• $\ldots$ (you can argue this is a form of induction, but you have to make the leap somewhere, unless your proof contains infinite number of symbols),
• put $n-2$ shortest people to fill first $n-2$ places, and then pick the tallest person (i.e. any, but not the smallest of those who left, you have $n+1-n$ ways of doing that) and order the rest in $(n+1-n)!$ ways.

Hope that helps ;-)

Answer 5

Both sides count the number of nontrivial permutations of $n+1$ objects. By "nontrivial" I mean "not the identity".

RHS: The total number of permutations is $(n+1)!$, of which 1 is trivial.

LHS: Let the objects be $0,1,\dotsc,n$. Every nontrivial permutation moves at least one number. Let $k$ be the greatest number which is moved. Since the greater numbers are not moved, the permutation must move $k$ into one of the $k$ spots to its left. The $k$ numbers $0,1,\dotsc,k-1$ can then be arranged in the remaining spots in $k!$ ways. So that's $k\cdot k!$ permutations in which $k$ is the greatest number moved; sum over $k$ to get the LHS.