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.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.