4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Arthur Jul 15 '16 at 17:18
  • $\begingroup$ @Arthur Thanks for the kind attempt :) $\endgroup$ – crskhr Jul 15 '16 at 17:23
  • $\begingroup$ I found my mistake: the coefficient of $\frac{d^m}{dx^m}x^{k-1}$ was a factor $m!$ too small. $\endgroup$ – Arthur Jul 15 '16 at 18:40
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Arthur Jul 15 '16 at 18:18
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Regarding your first proof. Is $k=0$ valid? Note, that $\binom{k-1}{m}=0$ for $1\leq k \leq m$. $\endgroup$ – Markus Scheuer Jul 16 '16 at 22:15
  • 1
    $\begingroup$ 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.$ $\endgroup$ – Marko Riedel Jul 16 '16 at 22:25
  • $\begingroup$ Great! I, see. Thanks, Marko! (+1) justified. $\endgroup$ – Markus Scheuer Jul 16 '16 at 22:28
2
$\begingroup$

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.