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

-

## migrated from meta.math.stackexchange.comMar 15 '12 at 18:09

This question came from our discussion, support, and feature requests site for people studying math at any level and professionals in related fields.

## marked as duplicate by Rudy the Reindeer, anon, Asaf Karagila, Sivaram Ambikasaran, Kannappan Sampath Mar 15 '12 at 21:20

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

@MattN. It's not a dup since the OP asks for ways other than induction, whereas the linked question asks for proofs by induction. – Bill Dubuque Mar 15 '12 at 18:20
@Matt: It’s definitely not a duplicate, since that one wanted an inductive argument, and this one explicitly doesn’t. – Brian M. Scott Mar 15 '12 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. – André Nicolas Mar 15 '12 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 – Rudy the Reindeer Mar 16 '12 at 22:42
@tendua Here's a follow up question to BD's answer. Someone just pointed it out to me in chat. – Rudy the Reindeer Mar 16 '12 at 22:52

## 5 Answers

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 Mar 15 '12 at 18:57
It happens all the time for me too ;-| But I can upvote you in some form of redress ^^ – dtldarek Mar 15 '12 at 19:00
See, it worked! Cheers! – dtldarek Mar 15 '12 at 20:03
Yes, well done! All is forgiven! – user21467 Mar 15 '12 at 20:06
This too uses induction, e.g. to prove both of the RHS and LHS statements (and look at all those ellipses!) – Bill Dubuque Mar 15 '12 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. – Bill Dubuque Mar 15 '12 at 18:30
Moreover, using ellipses instead of a rigorous formal induction does nothing to eliminate the induction. See my answer. – Bill Dubuque Mar 15 '12 at 19:00

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.

-

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. – Bill Dubuque Mar 15 '12 at 18:31