# Proving $\sum_{k=1}^n k k!=(n+1)!-1$

Prove: $\displaystyle\sum_{k=1}^n k k!=(n+1)!-1$ (preferably combinatorially)

It's pretty easy to think of a story for the RHS: arrange $n+1$ people in a row and remove the the option of everyone arranged to height from shortest to highest, but it doesn't hold up for the LHS.

Alternatively, trying to visualize the LHS, I noticed that it's like a right angle tetrahedra:

1

2!+2!

3!+3!+3!

...

But it doesn't help to see a connection to the RHS.

Note: no integrals or gamma function nor use of other identities without proving them nor generating functions.

• Could you perhaps write it as a telescopic sum? – mickep Mar 20 '15 at 18:35
• Your triangle visual suggests one approach: $$n\sum_{k=1}^n k! - \sum_{i=0}^{n-1}\sum_{j=1}^i j!$$ This, together with the telescopic suggestion, shows how the sum really does collapse very neatly. – abiessu Mar 20 '15 at 18:36
• @mickep but there are no cancellations as far as I can see. – shinzou Mar 20 '15 at 18:37
• $kk!=(k+1)!-k!$ – mickep Mar 20 '15 at 18:37
• @abiessu I see that the telescopic sum is enough actually. Could you explain how you got to that expression please? – shinzou Mar 20 '15 at 18:49

Given an ordered list of $n+1$ items, pick $k$ between $1$ and $n$. Focus attention on the first $k$ items. Pick one of these items ($k$ ways to do this) to swap with item $k+1$. Now permute this modified initial set of $k$ items ($k!$ ways to do this), and leave unchanged the items past position $k+1$. Each choice of $k$ generates a different collection of permutations. Moreover, as $k$ ranges from $1$ to $n$, we'll generate all possible permutations of the list, except the original list, since the algorithm forces at least one item to move to a new position. Conclude: $$\sum_{k=1}^n kk! = (n+1)! - 1$$

• This interpretation is virtually identical to the one in my answer. – Yuval Filmus Mar 21 '15 at 18:16

$\sum_{k=1}^n{kk!}$

$=\sum_{k=1}^n{((k+1)-1)k!}$

$=\sum_{k=1}^n{(k+1)k!-k!}$

$=\sum_{k=1}^n{(k+1)!-k!}$

$=(n+1)!-1!$

$=(n+1)!-1$

• +1. This answer gives a more intuitive look at the problem rather than just blindly using induction – MCT Mar 20 '15 at 21:40

For a permutation $\pi = \pi_1 \ldots \pi_{n+1}$ in $S_{n+1}$, let $m = m(\pi)$ be the maximal index such that $\pi_1 = 1, \pi_2 = 2, \ldots, \pi_m = m$. The number of permutations such that $m(\pi) = m$ for $m < n$ is $(n-m) (n-m)!$: here $n-m$ is the number of choices for $\pi_{m+1} \neq m+1$, and $(n-m)!$ is the number of permutations of the remaining $n-m$ numbers. No permutation satisfies $m(\pi) = n$, and there is a single permutation such that $m(\pi) = n+1$. Altogether, since there are $(n+1)!$ permutations in $S_{n+1}$, $$(n+1)! = \sum_{m=0}^{n-1} (n-m)(n-m)! + 1 = \sum_{k=1}^n k \cdot k! + 1.$$

• Nice. This should have more upvotes since it actually offers a combinatorial approach! – MCT Mar 20 '15 at 21:40

You can show $$\displaystyle\sum_{k=1}^n k k!=(n+1)!-1$$ by induction. It holds for $n=1.$ Assume it is satisfied for a given $n$ and show it for $n+1.$ We assume $$\displaystyle\sum_{k=1}^n k k!=(n+1)!-1$$ and we need to show

$$\displaystyle\sum_{k=1}^{n+1} k k!=(n+2)!-1.$$ Just write

$$\displaystyle\sum_{k=1}^{n+1} k k!=\sum_{k=1}^{n} k k!+(n+1)(n+1)!.$$ Use induction hypothesis and you are done.

Note: I realize you said your desired solution is a combinatorial one, but I thought I would provide a complete induction proof in case you did not get any sort of combinatorial answers.

Claim: For all $n\geq 1, \sum_{k=1}^n kk! = (n+1)!-1$.

Proof. Let $S(n)$ denote the statement $$S(n) : \sum_{k=1}^n kk! = (n+1)!-1.$$ Base step ($n=1$): $S(1)$ is true because $1=2!-1$.

Inductive step: For some fixed $\ell\geq 1$, assume the inductive hypothesis $S(\ell)$ to be true where $$S(\ell) : \sum_{k=1}^\ell kk! = (\ell+1)!-1.$$ To be shown is that $S(\ell+1)$ follows, where $$S(\ell+1) : \sum_{k=1}^{\ell+1} kk! = (\ell+2)!-1.$$ Starting with the left-hand side of $S(\ell+1)$, \begin{align} \sum_{k=1}^{\ell+1} kk! &= \sum_{k=1}^\ell kk! + (\ell+1)(\ell+1)!\tag{by definition of $\Sigma$}\\[1em] &= [(\ell+1)!-1]+(\ell+1)(\ell+1)!\tag{by $S(\ell)$}\\[1em] &= (\ell+1)!(1+\ell+1)-1\\[1em] &= (\ell+2)\cdot(\ell+1)!-1\\[1em] &= (\ell+2)!-1, \end{align} we see that the right-hand side of $S(\ell+1)$ follows. This completes the inductive step.

Thus, by mathematical induction, the statement $S(n)$ is true for all $n\geq 1$. $\blacksquare$

Using some expansion and recombining tricks, we can evaluate this sum like so:

$$\sum_{k=1}^n kk! = 1! + (2! + 2!) + (3! + 3! + 3!) + \dots\\ =\sum_{k=1}^n k! + \sum_{k=2}^n k! + \sum_{k=3}^n k!\dots\\ =n\sum_{k=1}^n k! - 1! - (1! + 2!) - (1! + 2! + 3!) - \dots - (1! + 2! + \dots + (n-1)!)\\ =n\sum_{k=1}^n k! - \sum_{k=1}^{n-1}\sum_{j=1}^k j!$$

Reversing the order of things, we have

$$n\sum_{k=1}^n k! - \sum_{k=1}^{n-1}\sum_{j=1}^k j!=nn! + n(n-1)! + n(n-2)!+\dots - (n-1)! - 2(n-2)! - \dots - (n-1)1!\\ =(n+1)n!+(n-2)! + n(n-3)! + n(n-4)! + \dots - 2(n-2)! - 3(n-3)! -\dots -n +1\\ =(n+1)!+2(n-3)!+n(n-4)!+n(n-5)!+\dots -3(n-3)!-4(n-3)!-\dots-n+1\\ \vdots\\ =(n+1)!+(n-2)1!-(n-1)1!=(n+1)!-1$$

This collapse is obviously much messier than the telescoping mentioned elsewhere, but nevertheless works out correctly.

Let $S$ be the set of all permutations f of ${1,2,3,..,, n+1}$ with at least one non-fixed point (i.e., a value k with $f(k)≠k$). Then $|S| = (n+1)!-1$.

Now count the permutations with the highest non-fixed point first, then those with the 2nd highest non-fixed point (which are not already counted), then those with the 3rd highest non-fixed point (which are not already counted), and so on. Below are the details.

Let $S[n+1]$ be the set of permutations with $n+1$ as a non-fixed point. For each $k < n+1$, define $S[k]$ to be the set of all permutations in $S - (S[n+1] ∪ S[n] ∪ ... ∪ S[k+1])$ with $k$ as a non-fixed point. Then

$|S[n+1]|= n.n!$ because there are $n.n!$ permutations with $f(n+1)≠n+1$. [Just take any particular permutation of ${1,2,3,..,n}$ and insert $n+1$ in any of the first $n$ spaces (of the $n+1$ spaces) created by the permutation to get $n$ such permutations from it.]

$|S[n]|=(n-1).(n-1)!$ because there are $(n-1).(n-1)!$ permutations with $f(n+1)=n+1$ and $f(n)≠n$.

$|S[n-1]| = (n-2).(n-2)!$ because there are $(n-2).(n-2)!$ permutations with $f(n+1)=n+1$, $f(n)=n$, and $f(n-1)≠n-1$.

$|S[n-2]|=(n-3).(n-3)!$ because there are $(n-3).(n-3)!$ permutations with $f(n+1)=n+1$, $f(n)=n$, $f(n-1)=n-1$, and $f(n-2)≠n-2$.
. . . .
$|S|=2.(2!)$ because there are $2.(2!)$ permutations with $f(n+1)=n+1$, $f(n)=n$, $f(n-1)=n-1$, $\cdots$, $f(4)=4$, and $f(3)≠3$.

$|S|=1.(1!)$ because there are $1.(1!)$ permutations with $f(n+1)=n+1$, $f(n)=n$, $f(n-1)=n-1$, $\cdots$, $f(4)=4$, $f(3)=3$, and $f(2)≠2$.

$|S|=0$ because there are $(0).(0!)$ permutations with $f(n+1)=n+1$, $f(n)=n$, $f(n-1)=n-1$, $\cdots$, $f(4)=4$, $f(3)=3$, $f(2)=2$, and $f(1)≠1$.

So we get $(n+1)!-1 = |S|$
$= |S[n+1]| + |S[n]| + |S[n-1]| + ... + |S| + |S|$
$= n.n! + (n-1).(n-1)! + (n-2).(n-2)! + ... + 2.(2!) +1.(1!)$. QED

• @ Watson - Is this how a first-time user is welcomed? By the way, I don't know how to use MathJax. Disculpame. Thanks anyway. – Ram Jul 22 '16 at 10:35
• Sorry for being a bit rude in my previous comment. I should have given you this link for MathJax. This is really useful on this site. Anyway, welcome to Math.SE! – Watson Jul 22 '16 at 11:08

By induction on $n$.

Assume that: $$\sum_{k=1}^{n}kk! = (n+1)! - 1$$

We have:

$$\sum_{k=1}^{n+1}kk! = \sum_{k=1}^{n}kk! + (n+1)(n+1)! = (n+1)! - 1 + (n+1)(n+1)! = \cdots$$

The factorial function is defined recursively by

$$\tag 1 (n+1)! = (n+1)\, n!$$

We know that the number of permutations of a set $$X$$ with $$n$$ elements is equal to $$n!$$. Moreover, a simple combinatorial [fixed point or not fixed point]-argument (see next section) can be used to alternatively confirm $$\text{(1)}$$ by counting permutations,

$$\tag 2 (n+1)! = n \, n! + n!$$

You can repeat/descend on this combinatorial argument and for $$n \ge 1$$ write

$$\tag 3 \displaystyle (n+1)! = \big [\sum_{k=m}^n k \, k! \, \big ] + m!, \text{ with } 1 \le m \le n$$

and letting $$m = 1$$,

$$\tag 3 \displaystyle (n+1)! = \big [ \sum_{k=1}^n k \, k! \, \big ] + 1!, \text{ with } 1 \le m \le n$$

Let $$\mathtt S$$ denote the set of all bijections $$\sigma$$ of the set of integers $$\{1,2,\dots,n\}$$.

Let $$\mathtt T$$ denote the bijections $$\tau$$ of the set of integers $$\{1,2,\dots,n+1\}$$ such that $$\tau(n+1) \ne n+1$$.

Let $$\mathtt U = \{1,2,\dots,n\} \times \mathtt S$$.

We can put $$\mathtt U$$ in bijective correspondence with $$\mathtt T$$ by the mapping

$$\tag 4 (k, \sigma) \mapsto \sigma' \circ \big(k \; t\big), \; \text{ with } t = n+1 \text{ and transposition } \big(k \; t\big)$$

Note that in $$\text{(4)}$$ we extend the domain of $$\sigma$$ by defining $$\sigma'(t) = t$$.

This mapping is injective. If $$\tau \in \mathtt T$$ and $$k = \tau^{-1}(t)$$ then $$t$$ is a fixed point of $$\tau \circ \big(k \; t\big)$$ so the mapping is also surjective.

The set of permutations of $$\{1,2,\dots,n+1\}$$ leaving $$n+1$$ fixed can be identified with the set $$\mathtt S$$.

Thus by partitioning the bijections into two blocks, we conclude that $$\text{(2)}$$ is true.