Another binomial sum

Came across an interesting problem Brent Yorgey from his blog The Math Less Traveled. In this post he tried to explain what is meant by a combinatorial proof to prepare his readers for a proof of this identity
[tex] \displaystyle n! = \sum_{i=0}^n (-1)^{n-i} (k+i)^n.[/tex]
Note that the k in the sum does nothing.
The problem which lead to this is also interesting but for now I’m concentrating on the identity.
In the right hand side, we expand using the binomial theorem and interchange summation
(Matt Gardner Spencer also posted a comment with I guess more or less the same solution.)
[tex] \displaystyle
\sum_{i=0}^n (-1)^{n-i} \binom{n}{i} \sum_{j=0}^n \binom{n}{j} k^{n-j}i^j
= \sum_{j=0}^n \binom{n}{j} k^{n-j} (-1)^n \sum_{i=0}^n (-1)^{i} \binom{n}{i} i^j
[/tex]
At this point we need a lemma that says that
[tex] \left. (x\frac{d}{dx})^j (1+x)^n \right|_{x=-1} =
\begin{cases} 0 & \text{ if } j < n ; \\ n!(-1)^n &\text{ if } j=n.
\end{cases}
[/tex]

On the other hand, using the binomial theorem again,
[tex] \displaystyle
(x\frac{d}{dx})^j \left( \sum_{i=0}^n \binom{n}{i} x^i \right) = \sum_{i=0}^n \binom{n}{i} i^j x^i.
[/tex]
So our identity is
[tex] \displaystyle
\sum_{j=0}^n \binom{n}{j} k^{n-j} (-1)^n \left. (x\frac{d}{dx})^j (1+x)^n \right|_{x=-1}
[/tex]
and the only term that does not vanish is the [tex]j=n [/tex] term which simplifies to [tex]n![/tex].
In full disclosure, Mathematica evaluates the sum as [tex](-1)^{2n}n![/tex] instantly.

This entry was posted in Combinatorics. Bookmark the permalink.

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>