Combinatorial proof of $\sum_{k=0}^n k \cdot k! = (n+1)! -1$

Question

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.

Answer 1

$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.

Answer 2

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!