# Combinatorial Identity Proof

What is a combinatorial proof for this identity:

$1 \times 1! + 2 \times 2! + ... + n \times n! = (n + 1)! - 1$

I am trying to figure out what are both sides trying to count.

• The induction proof is pretty straight forward, but I cannot get an idea of the combinatorial meaning of $\sum_{k=1}^nk\times k!$. – Carlos Eugenio Thompson Pinzón Dec 8 '13 at 15:43
• You could also observe a telescoping sum i.e. $n.n! = (n+1)! - n!$. But the count on LHS is tricky... – Gautam Shenoy Dec 8 '13 at 15:47

The $k$-th term on the left hand side counts the number of permutations of $\{1,\ldots,n+1\}$ whose last non-fixed-point is $k+1$. We choose one of the first $k$ to put in position $k+1$, then order the rest of the first $k+1$ in the first $k$ positions in any way we like.
The right hand side counts all nonidentity permutations of $\{1,\ldots,n+1\}$ (those with at least one non-fixed-point).