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

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 curios what could be the other possible ways to prove it.

Answer 1

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.

Answer 2

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

Both satisfy $\rm\:f(n+1)-f(n) = (n+1)(n+1)!,\ f(0) = 0,\:$ so they are equal by the uniqueness theorem for first-order recurrences, a.k.a. the fundamental theorem of difference calculus (which has a completely trivial inductive proof).

As I often emphasize, uniqueness theorems provide powerful tools for proving equalities. See also my many posts on telescopy.

On the general topic of 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 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

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