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

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 2

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 3

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

Answer 4

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 5

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

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