# Permutation Identity and Sum

Show that $\displaystyle 1+ \sum\limits_{k=1}^{n} k \cdot k! = (n+1)!$

RHS: This is the number of permutations of an $n+1$ element set. We can rewrite this as $n!(n+1)$.

LHS: It seems that the $k \cdot k!$ has a similar form to $(n+1)! = (n+1)n!$ Also we can write $1 = 0!$ I think you use the mulitplication principle is being used here (e.g. the permutations of a $k$ element set multiplied by $k$).

Note that a combinatorial proof is wanted (not an algebraic one).

-
Are you going through a book? Can we please have the name of the book? –  Aryabhata Dec 26 '10 at 18:53
@Moron: No I am not. –  PEV Dec 26 '10 at 18:58
What is the source of these problems then? I am curious (and I suppose other folks are too). Thanks. –  Aryabhata Dec 26 '10 at 19:08
@Moron: They are old homework from about a year ago. –  PEV Dec 26 '10 at 19:44

Here is a brief description of one combinatorial way to approach this. Suppose we are permuting $\{1,2,3,\ldots,n+1\}$. One permutation is $P=(1,2,3,\ldots,n+1)$. Any other permutation has a first position from the left which differs from $P$.
Let $S_1$ be the set of permutations that first differs from $P$ in position $n$. Let $S_2$ be the set of permutations that first differs from $P$ in position $n-1$. Continue this until we get to $S_n$, which is the set of permutations that first differs from $P$ in position $1$.
When we count the size of $S_i$, we can convince ourselves that it is $(i+1)!-i! = i \cdot i!$. This is the part I'm skipping over. Also counting $P$ then gives us the left hand side.