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

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.

• @MattN. It's not a dup since the OP asks for ways other than induction, whereas the linked question asks for proofs by induction. Commented Mar 15, 2012 at 18:20
• @Matt: It’s definitely not a duplicate, since that one wanted an inductive argument, and this one explicitly doesn’t. Commented Mar 15, 2012 at 18:20
• There cannot be a non-inductive proof, since the sum is defined recursively. As a rough guide, if it has "$\dots$" it requires induction, unless it is a consequence of a prior result that required induction. But many inductive proofs are so transparent that we do not make the induction explicit. Commented Mar 15, 2012 at 18:51
• @tendua No one got pinged by your "@All" ping, you need to ping using names. Sorry for the late reply. I voted to close your question because I thought the question I linked to answered your question. Now if you think your question is not answered and you'd like it to be reopened let us know. We can always vote to reopen it. Hope this helps. If you'd like to discuss any of the answers or anything else feel free to drop by the main chat room. Cheers Commented Mar 16, 2012 at 22:42
• @tendua Here's a follow up question to BD's answer. Someone just pointed it out to me in chat. Commented Mar 16, 2012 at 22:52

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.

• @dtldarek beat me to the punch, I see.
– user21467
Commented Mar 15, 2012 at 18:57
• It happens all the time for me too ;-| But I can upvote you in some form of redress ^^ Commented Mar 15, 2012 at 19:00
• See, it worked! Cheers! Commented Mar 15, 2012 at 20:03
• Yes, well done! All is forgiven!
– user21467
Commented Mar 15, 2012 at 20:06
• This too uses induction, e.g. to prove both of the RHS and LHS statements (and look at all those ellipses!) Commented Mar 15, 2012 at 22:57

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

• That's just the usual inductive proof expressed in telescopic form, so it does use induction. Commented Mar 15, 2012 at 18:30
• Moreover, using ellipses instead of a rigorous formal induction does nothing to eliminate the induction. See my answer. Commented Mar 15, 2012 at 19:00

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.

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 ;-)

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

• That's just the usual inductive proof expressed in telescopic form, so it does use induction. Commented Mar 15, 2012 at 18:31