Combinatorial proof of $\sum_{k=0}^n k \cdot k! = (n+1)! -1$ Is there a nice combinatorial proof of the following identity?  (That is, by showing that both sides count the same thing.)
$$\sum_{k=0}^n k \cdot k! = (n+1)! -1 $$
I was searching Wikipedia for nice identities to assign to my students for a homework on combinatorial proof, and thought this one looked innocent enough, but then realized I couldn't solve it myself.
Perhaps we should take the set of permutations of $n+1$ letters and partition it in some clever way (maybe the $-1$ suggests that the identity should be set aside), but I can't see what that might be.
Of course it is very easy to prove by induction; that's not what I'm looking for.
 A: $k\cdot k!$ is the number of permutations of the $(n+1)$ symbols $0,\,1,\,\dotsc,\, n$ such that $k$ is the largest symbol that is not kept fixed. (Symbol $k$ can be mapped to the $k$ places $0,\,\dotsc,\,k-1$, the $k$ smaller symbols then can be placed arbitrarily in the $k$ left free places.) So
$$\sum_{k=0}^n k\cdot k!$$
is the number of non-identity permutations of the $(n+1)$ symbols. On the other hand, that number is of course the total number of permutations of $(n+1)$ symbols minus one.
Not the best combinatorial proof ever, but meh.
A: I'm not sure this constitutes a 'combinatorial proof', but have you tried proof by induction? 
We hope to find that if the statement is true for some n, then it will also be true for n+1. 
S[k=0 to n+1] k.k! = S[k=0 to n]k.k!  +  (n+1)(n+1)! = (n+1)! - 1 + (n+1)(n+1)! = (n+2)! - 1
and this is indeed what you get if you replace n with n+1  on the RHS of your original equaton.
It is trivial to see that the statement is true for n=0, therefore it is true for all the natural numbers.
The above is only an outline proof, but do you get the idea?
p.s. sorry I don't know how do do the equations nicely! 
