# How to prove: $\sum_{k=m+1}^{n} (-1)^{k} \binom{n}{k}\binom{k-1}{m}= (-1)^{m+1}$

Show that if $m$ and $n$ are integers with $0\leq m<n$ then $$\sum_{k=m+1}^{n} (-1)^{k} \binom{n}{k}\binom{k-1}{m}= (-1)^{m+1}$$

Attempts:

• $(-1)^{k}\binom{n}{k}$ is the coefficient of $x^{k}$ in the expansion of $(1-x)^{n}$

• And $\binom{k-1}{m}$ is the coefficient of $x^{m}$ in the expansion of $(1+x)^{k-1}$.

Thats all what I could come up with.

• I keep getting $$\frac{(x-1)^n - (-1)^n}x = \sum_{k = 1}^n(-1)^{n-k}\binom{n}{k}x^{k-1}$$ and differentiating that $m$ times and inserting $x = 1$ should yield your desired result (up to a sign, at least) since $\frac{d^m}{dx^m}x^{k-1} = \binom{k-1}{m}x^{k-m-1}$. But the $m$'th derivative of the left-hand fraction at $x = 1$ seems to be $(-1)^m\cdot m!$, so I must be messing up somewhere. I don't have time to find the mistake, so I'm leaving what I have found here, in the hopes that someone picks it up and corrects it. – Arthur Jul 15 '16 at 17:18
• @Arthur Thanks for the kind attempt :) – crskhr Jul 15 '16 at 17:23
• I found my mistake: the coefficient of $\frac{d^m}{dx^m}x^{k-1}$ was a factor $m!$ too small. – Arthur Jul 15 '16 at 18:40

Following the hint of Arthur, note that $$\frac{1}{m!}\sum_{k=1}^{n}\dbinom{n}{k}\left(-1\right)^{k}x^{k-1}=\frac{\left(1-x\right)^{n}-1}{xm!}$$ and if we differentiate the LHS $m$ times, we get $$\frac{1}{m!}\sum_{k=1}^{n}\dbinom{n}{k}\left(-1\right)^{k}\left(k-1\right)\left(k-2\right)\cdots\left(k-m\right)x^{k-m-1}=\sum_{k=m+1}^{n}\dbinom{n}{k}\left(-1\right)^{k}\frac{\left(k-1\right)!}{m!\left(k-m-1\right)!}x^{k-m-1}$$ so we have $$\sum_{k=m+1}^{n}\dbinom{n}{k}\left(-1\right)^{k}\dbinom{k-1}{m}=\frac{1}{m!}\frac{d^{m}}{dx^{m}}\left(\frac{\left(1-x\right)^{n}-1}{x}\right)_{x=1}$$ now note that $$\frac{d}{dx}\left(\frac{\left(1-x\right)^{n}}{x}-\frac{1}{x}\right)=-\frac{n\left(1-x\right)^{n-1}}{x}-\frac{\left(1-x\right)^{n}}{x^{2}}+\frac{1}{x^{2}}$$ and $$\frac{d}{dx}\left(-\frac{n\left(1-x\right)^{n-1}}{x}-\frac{\left(1-x\right)^{n}}{x^{2}}+\frac{1}{x^{2}}\right)=\frac{2\left(1-x\right)^{n}}{x^{3}}+\frac{2n\left(1-x\right)^{n-1}}{x^{2}}+\frac{n\left(n-1\right)\left(1-x\right)^{n-2}}{x}-\frac{2}{x^{3}}$$ and so on, so you can see that, since $m<n$ we have only one term that doesn't vanish at $x=1$. Hence $$\frac{1}{m!}\frac{d^{m}}{dx^{m}}\left(\frac{\left(1-x\right)^{n}-1}{x}\right)_{x=1}=\frac{1}{m!}\left(-1\right)^{m+1}m!=\left(-1\right)^{m+1}$$ so finally

$$\sum_{k=m+1}^{n}\dbinom{n}{k}\left(-1\right)^{k}\dbinom{k-1}{m}=\color{red}{\left(-1\right)^{m+1}}$$

as wanted.

• Ahh, I see my mistake now. The coefficient of $\frac{d^m}{dx^m}x^{k-1}$ is $_{k-1}P_m$, not $_{k-1}C_m$. – Arthur Jul 15 '16 at 18:18

For those who enjoy integrals here is another approach using the Egorychev method as presented in many posts by @FelixMarin and also by @MarkusScheuer.

Suppose we seek to verify that

$$\sum_{k=m+1}^n (-1)^k {n\choose k} {k-1\choose m} = (-1)^{m+1}.$$

First proof. Introduce

$${k-1\choose m} = {k-1\choose k-1-m} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k-m}} (1+z)^{k-1} \; dz.$$

Now clearly when $k\le m$ this vanishes so we may lower the limit in the sum to $k=0.$ We obtain

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{z^m}{1+z} \sum_{k=0}^n {n\choose k} (-1)^k \frac{(1+z)^k}{z^k} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{z^m}{1+z} \left(1-\frac{1+z}{z} \right)^n \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{z^m}{1+z} \frac{(-1)^n}{z^n} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(-1)^n}{z^{n-m} (1+z)} \; dz = (-1)^n (-1)^{n-m-1} = (-1)^{m+1}.$$

Second proof. Introduce

$${k-1\choose m} = {k-1\choose k-1-m} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} \frac{1}{(1-z)^{k-m}} \; dz.$$

Now for $1\le k\le m$ this is $[z^m] (1-z)^{m-k} = 0$ so we may again extend the summation back to $k=0$, taking care of the value at $k=0$ which is $(-1)^m.$ We obtain

$$-(-1)^m + \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} (1-z)^m \sum_{k=0}^n {n\choose k} \frac{(-1)^k}{(1-z)^k} \; dz \\ = -(-1)^m + \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} (1-z)^m \left(1-\frac{1}{1-z}\right)^n \; dz \\ = -(-1)^m + \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m-n+1}} \frac{(-1)^n}{(1-z)^{n-m}} \; dz.$$

Note however that we have $m\lt n$ so the contribution from the integral vanishes, once more leaving just $$(-1)^{m+1}.$$

• Regarding your first proof. Is $k=0$ valid? Note, that $\binom{k-1}{m}=0$ for $1\leq k \leq m$. – Markus Scheuer Jul 16 '16 at 22:15
• Observe that I am using ${k-1\choose k-1-m}$ and for $k=0$ this is zero by definition ($k-1-m\lt 0$) and it agrees with ${k-1\choose m}$ on the values being summed. The integral has the correct representation, with the pole at zero disappearing when $k=0$ and $m\ge 0.$ – Marko Riedel Jul 16 '16 at 22:25
• Great! I, see. Thanks, Marko! (+1) justified. – Markus Scheuer Jul 16 '16 at 22:28

Here is a variation based upon OPs attempts. In order to do so it's convenient to use the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ in a series. This way we can write e.g. \begin{align*} (-1)^k\binom{n}{k}=[x^k](1-x)^n \end{align*}

We obtain for $0\leq m < n$

\begin{align*} \sum_{k=m+1}^{n}&(-1)^{k}\binom{n}{k}\binom{k-1}{m}\\ &=\sum_{k=0}^{\infty}(-1)^{k}\binom{n}{k}\binom{k-1}{k-1-m}\tag{1}\\ &=\sum_{k=0}^\infty[x^k](1-x)^n [t^{k-1-m}](1+t)^{k-1}\tag{2}\\ &=[t^{-1-m}]\frac{1}{1+t}\sum_{k=0}^\infty(1+t)^kt^{-k}[x^{k}](1-x)^n \tag{3}\\ &=[t^{-1-m}]\frac{1}{1+t}\left(1-\frac{1+t}{t}\right)^n\tag{4}\\ &=[t^{-1-m}]\frac{1}{1+t}\left(-\frac{1}{t}\right)^n\\ &=(-1)^n[t^{n-m-1}]\sum_{j=0}^\infty(-t)^j\tag{5}\\ &=(-1)^{m+1}\tag{6} \end{align*} and the claim follows.

Comment:

• In (1) we use the binomial identity $\binom{p}{q}=\binom{p}{p-q}$ and extend the limits of the sum without changing anything since we are adding zeros only.

• In (2) we apply the coefficient of operator twice.

• In (3) we do some rearrangements by using the linearity of the coefficient of operator and we also use the rule \begin{align*} [t^{p+q}]A(t)=[t^p]t^{-q}A(t) \end{align*}

• In (4) we use the substitution rule \begin{align*} A(t)=\sum_{k=0}^\infty a_kt^k=\sum_{k=0}^\infty t^k[x^k]A(x)\\ \end{align*}

• In (5) we write $t^{-n}$ as part of the coefficient of operator (rule from (3)) and use the geometric series expansion of $\frac{1}{1+t}$.

• In (6) we select the coefficient of $t^{n-m-1}$.

• Very nice, and about as elementary as one can get. – Brian M. Scott Jul 16 '16 at 22:52
• @BrianM.Scott: Thanks, Brian! :-) – Markus Scheuer Jul 16 '16 at 22:54

The result can also be proved fairly easily by induction on $n$. First note that there’s no need to specify the limits of summation: if $k>n$ or $k<m+1$, one of the binomial coefficients is $0$ anyway. Suppose that

$$\sum_k(-1)^k\binom{n}k\binom{k-1}m= (-1)^{m+1}$$

whenever $0\le m<n$. Then for $m<n$ we have

\begin{align*} \sum_k(-1)^k\binom{n+1}k\binom{k-1}m&=\sum_k(-1)^k\left(\binom{n}k+\binom{n}{k-1}\right)\binom{k-1}m\\ &=\sum_k(-1)^k\binom{n}k\binom{k-1}m+\sum_k(-1)^k\binom{n}{k-1}\binom{k-1}m\\ &=(-1)^{m+1}+\sum_k(-1)^k\binom{n}{k-1}\binom{k-1}m\\ &=(-1)^{m+1}-\sum_k(-1)^k\binom{n}k\binom{k}m\\ &=(-1)^{m+1}-\sum_k(-1)^k\binom{n}m\binom{n-m}{n-k}\\ &=(-1)^{m+1}-\binom{n}m\sum_k(-1)^k\binom{n-m}k\\ &=(-1)^{m+1}\;, \end{align*}

since $\sum_k(-1)^k\binom{r}k=0$ for $r\in\Bbb Z^+$.

The case $m=n$ is trivial, as the summation has only one non-zero term, the one for $k=n+1$:

$$(-1)^{n+1}\binom{n+1}{n+1}\binom{n}n=(-1)^{n+1}\;.$$

Added: In fact, that suggests a combinatorial proof of the original identity. Suppose that we have $n$ white balls numbered $1$ through $n$. For a given $k$ there are $\binom{n}k\binom{k-1}m$ ways to choose $k$ of these balls, paint them red, set aside the red ball with the largest number, and then choose $m$ of the remaining $k-1$ red balls to paint blue. In the end we have the following as possible outcomes: a set of $m$ blue balls; a set of $k-m$ red balls, one of which has a larger number than any of the blue balls; and $n-k$ white balls. Clearly the possible values of $k$ are the integers $m+1,\ldots,n$.

Alternatively, we can categorize these outcomes by the specific set of blue balls and the number of the largest-numbered red ball. For a fixed set $B$ of $m$ blue balls and largest-numbered red ball $\ell$, the numbers on the remaining red balls can be any subset $R$ of $[\ell-1]\setminus B$, and the total number of red and blue balls (corresponding to $k$ above) is $|R|+m+1$. These outcomes therefore contribute

\begin{align*} \sum_{r=0}^{\ell-1-m}\binom{\ell-1-m}r(-1)^{r+m+1}&=(-1)^{m+1}\sum_r\binom{\ell-1-m}r(-1)^r\\ &=(-1)^{m+1}[\ell=m+1]\;, \end{align*}

where $[\ell=m+1]$ is an Iverson bracket.

That is, only for $B=[m]$ and $\ell=m+1$ do these outcomes have a non-zero contribution, and in that case the contribution is $(-1)^{m+1}$.