7
$\begingroup$

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.

$\endgroup$

2 Answers 2

16
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Ah, very nice. I was thinking about partitioning based on some set of elements being fixes, but couldn't come up with the right way to do it. $\endgroup$ Apr 3, 2014 at 0:40
0
$\begingroup$

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!

$\endgroup$
1
  • $\begingroup$ Sorry - I just re-read the original post and realise that this is not what you were looking for. $\endgroup$
    – Paul
    Apr 3, 2014 at 15:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .