# Proving a binomial sum with simple result

In deriving a formula I've come up with an expression that I need to prove, specifically:

$$(-1)^n = \sum_{j=1}^n (-1)^j \binom{n+1}{j+1} j^n$$

This seems remarkably simple to me, and considering that I'd never seen it before I didn't believe it, but upon checking numerically it seems true.

If this is true, why is it true?

-
See "Trick 2: Higher-order differences" in Concrete Mathematics, page 187. –  wj32 Oct 23 '12 at 8:37

This sum looks a bit strange, and a strategy of shaping up the formula, then generalizing it to obtain a proof works.

First note that the sum is missing the term for $j=0$; adding it in makes no difference because $j^n$ becomes $0^n=0$ unless $n=0$; however for $n=0$ you are saying $1=0$ which suggests the term really should be there. Indeed adding it you get $1=1$ for $n=0$, which is better. So we're now trying to prove $$(-1)^n=\sum_{j=0}^n(-1)^j\binom{n+1}{j+1}j^n\qquad\text{for all }n\in\mathbf N.$$ The sum still looks strange in that you are taking a complete row of Pascal's triangle, except column $0$. So maybe we should add in a term for $j=-1$ as well. The value of that term would be $(-1)^{-1}\binom{n+1}0(-1)^n=-(-1)^n$, the opposite of the LHS, so adding it in we have a sum that should vanish; better still. Let's take the occasion to change that ugly $j$ replacing it by $k=j+1$, which now runs from $0$ to $n+1$. But then we can also substitute $m=n+1$, so we are now faced with proving $$\sum_{k=0}^m(-1)^k\binom mk(k-1)^{m-1}=0\qquad\text{for all }m>0$$ (I've flipped the sign, which shouldn't matter if it is going to be $0$). The $(k-1)^{m-1}$ doesn't look very promising; it could be expanded by the binomial formula, but those terms don't seem to mesh particularly well. However, you can easily see the contribution to the sum obtained from the constant term $(-1)^{m-1}$ will be $0$, as (with a bit of effort) will be that of the linear term $ck$ (the value of $c=(-1)^{m-2}(m-1)$ is of no importance) provided $m>1$, and this suggests that maybe all terms contribute $0$. This would mean that all that matters about $(k-1)^{m-1}$ is that it is a polynomial in $k$ of degree less than $m$: $$\sum_{k=0}^m(-1)^k\binom mkP(k)=0\qquad\text{for all polynomial functions }P\text{ of degree less than }m.$$ Aha, but now it's clear, the summation multiplied by an alternating-sign row of Pascal's triangle is just the $m$-the power of the backward finite-difference operator $-\Delta:f\mapsto(k\mapsto f(k)-f(k+1))$, so we are asking for $$(-\Delta)^m(P)(0)=0\qquad\text{for all polynomial functions }P\text{ of degree less than }m.$$ But this is obvious since $-\Delta$ lowers the degree by $1$ and kills constant functions, so in fact $(-\Delta)^m(P)=0$ identically.

-

Hint: There is a trick for these kinds of formulas: Try expanding something like $(x+1)^n$ by the binomial theorem and then repeatedly derive by $x$ and multiply by $x$ on both sides to get that $j^n$ term. Finally plug in $x=0$. If this formula is correct you should be able to prove it that way. Otherwise you can always try induction (though that doesn't give you any information on how to get such a formula).

-
This isn’t likely to work, on account of the factor of $j^n$, where $j$ is the index of summation. –  Brian M. Scott Oct 22 '12 at 19:32
Why? You derive by $x$ that gives you a $j$, then multiply by $x$ and derive again, there is your $j^2$, etc. Of course you need to invest some work to evaluate the left side in the end, but it should be possible. –  Your Ad Here Oct 22 '12 at 19:47
Sorry: I misread it. Yes, it works in principle, but it looks pretty ugly. –  Brian M. Scott Oct 22 '12 at 20:06
In principle it works, but I can't see how to apply it for general n. That is, figuring out the left hand side for a given n now seems really difficult, unless I'm misunderstanding. I wouldn't know how to calculate $(x * d/dx)^n (1+x)^n$. –  VolatileStorm Oct 22 '12 at 20:11
Actually in this case it's possible since you only have to evaluate it at one point. I'll post the solution below. –  Your Ad Here Oct 23 '12 at 7:13

In the following we denote by $\left(x\frac{d}{dx}\right)^n f(x)$ the expression $$x\frac{d}{dx}\left(x\frac{d}{dx}\left(\cdots x\frac{d}{dx}f(x)\right)\right)$$ where the $x\frac{d}{dx}$ appears $n$ times. Also, $n,m,j$ always denote non-negative integers. By $\left|_{x=t}\right.$ we denote evaluation of an expression in the indeterminate $x$ (possibly involving derivatives) at $x=t$.

Claim 1. $$\left(x\frac{d}{dx}\right)^n x^m(1+x)^j\left.\right|_{x=-1}=0$$ for $j>n.$

Proof. We proceed by induction on $n$. For $n=0$ the claim is clear. Note \begin{align*} \left(x\frac{d}{dx}\right)^n x^m(1+x)^j &=\left(x\frac{d}{dx}\right)^{n-1}x\frac{d}{dx} x^m (1+x)^j \\ &= m\left(x\frac{d}{dx}\right)^{n-1}x^m(1+x)^j+j\left(x\frac{d}{dx}\right)^{n-1}x^{m+1}(1+x)^{j-1} \end{align*} for $n\ge 1$. Evaluating at $x=-1$ and using the induction hypothesis gives the claim.

Claim 2. $$(-1)^n=\sum^n_{j=1}(-1)^j{n+1\choose j+1}j^n$$

Proof. By the binomial theorem we have $$(t+1)^n=\sum^n_{j=0}{n\choose j}t^j$$ for all $t\in\mathbb{R}$. Integrating on both sides with respect to $t$ from $0$ to $x\in\mathbb{R}\backslash\{0\}$ and dividing by $x$ gives

$$x^{-1}F(x)=\sum^n_{j=1}{n\choose j}\frac{1}{j+1}x^j.$$

where $F(x)=\int_0^x (t+1)^n dt$. Applying $\left(x\frac{d}{dx}\right)^n$ on both sides and noting that $\left(x\frac{d}{dx}\right)^n x^k=k^n x^k$ we get

$$\left(x\frac{d}{dx}\right)^n x^{-1} F(x)=\sum^n_{j=1}{n\choose j}\frac{j^n}{j+1}x^j\;\;\;\;\;\;\;(*).$$

Now we see by the fundamental theorem of calculus that

\begin{align*} \left(x\frac{d}{dx}\right)^n x^{-1} F(x) &= \left(x\frac{d}{dx}\right)^{n-1} x\left(-x^{-2}F(x)+x^{-1}(1+x)^n\right)\\ &= -\left(x\frac{d}{dx}\right)^{n-1} x^{-1} F(x) + \left(x\frac{d}{dx}\right)^{n-1} (1+x)^n \end{align*} for $n\ge 1$. Evaluating at $x=-1$ gives $$\left(x\frac{d}{dx}\right)^n x^{-1} F(x)\left|_{x=-1}\right.=-\left(x\frac{d}{dx}\right)^{n-1} x^{-1} F(x)\left|_{x=-1}\right.$$ by Claim 1. Thus we have $$\left(x\frac{d}{dx}\right)^n x^{-1} F(x)\left|_{x=-1}\right.=(-1)^{n+1} F(-1)=\frac{(-1)^n}{n+1}\;\;\;\;(**)$$ where the last equality holds because $$F(-1)=\int_0^{-1}(1+t)^ndt=-\int^1_0 t^n dt=\frac{-1}{n+1}.$$ Evaluating $(*)$ at $x=-1$, plugging in $(**)$ and multiplying by $n+1$ gives $$(-1)^n=\sum^n_{j=1}(-1)^j{n\choose j}\frac{n+1}{j+1}j^n=\sum^n_{j=1}(-1)^j{n+1\choose j+1}j^n$$ as required.

-

Observe that the coefficient of $x^{m-1}$ (for $m \ge 1$) in $e^{-x}(1-e^x)^m$ is 0, since $$(1-e^x)^m=(-x-\frac{x^2}{2!}-\cdots)^m.$$ Now \begin{align} e^{-x}(1-e^x)^m &= e^{-x} \sum_{k} (-1)^k \binom{m}{k} e^{kx} \\ &= \sum_{k} (-1)^k \binom{m}{k} e^{(k-1)x} \\ &= \sum_{k} (-1)^k \binom{m}{k} \sum_{j \ge 0} \frac{(k-1)^j}{j!} x^j, \end{align} so the coefficient of $x^{m-1}$ is $$\sum_{k} (-1)^k \binom{m}{k} \frac{(k-1)^{m-1}}{(m-1)!}.$$ This is zero, and your identity follows (see Marc van Leeuwen's answer).

Also note that the coefficient of $x^n/n!$ in $(e^x-1)^m$ counts the number of surjective functions from a set of size $n$ to a set of size $m$. This can give you some nice results regarding Stirling numbers of the second kind.

-