The well-known identity
1×1! + 2×2! + 3×3! + … + n×n! = (n+1)! − 1
can be proven by applying the principle of the telescoping sum: observe that
(k+1)! − k! = k×k!
and sum over k.
The identity also has a combinatorial interpretation: both sides of the identity count the nontrivial permutations of the sequence 0,1,2,…,n. (A "nontrivial" permutation is one that moves at least one of the elements of the sequence.)
The right-hand side: The sequence has n+1 elements, hence (n+1)! permutations, of which just one — namely the identity permutation — is trivial. So there are (n+1)!−1 nontrivial permutations.
The left-hand side: A nontrivial permutation moves at least one element of the sequence. Consider the permutations in which k is the largest integer that moves. The greater integers k+1,k+2,…,n remain in their original positions. The integer k must move left, into one of k positions. The lesser integers 0,1,…,k−1 may then be arranged in the remaining positions in any of k! ways. Thus there are k×k! permutations in which k is the largest integer that moves. Sum over k. (The term with k=0 is zero, and so may be omitted; indeed, 0 cannot be the largest integer that moves, since it would have nowhere to go.)
2006 August 4