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

Question

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.

Answer 1

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

Answer 2

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. $$

Answer 3

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

Answer 4

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.

Answer 5

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$

Answer 6

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[3]|=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[2]|=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[1]|=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[3]| + |S[2]|$
$= n.n! + (n-1).(n-1)! + (n-2).(n-2)! + ... + 2.(2!) +1.(1!)$. QED

Answer 7

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.

Answer 8

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.

Answer 9

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