Derive $\sum_{s=r}^{\infty} \binom{m}{s} \binom{s}{r}(-1)^s=0 $ using an identity $(1 + x)^ m (1 + x)^{ -(r+1)} = (1 + x)^{ m-r-1}$

Question

To prove: $$\sum_{s=r}^{\infty}\binom{m}{s} \binom{s}{r}(-1)^s=0 $$

Use the identity: $$(1 + x)^ m (1 + x)^{ -(r+1)} = (1 + x)^{ m-r-1}$$

I have trouble understanding the hint, could somebody help me understand what is meant?

Hint: use the generating function for negative powers of $1+x$ to determine the coefficient of $x^{ m−r}$ in left and right hand side of this identity, this coefficient is $0$. Why? Then derive the result by suitable substitutions of the summation variables.

I specifically don't understand what is meant with "using the generating function for negative powers of $1+x$ " and determining the coefficient related to $x^{m-r}$

The formula for negative powers would give me:

$$(1+x)^{-n} = \sum_{k=0} ^{\infty} \binom{-n}{k}x^k$$

If I would write this out for both sides I get: $$ \sum_{k=0} ^{\infty} \binom{m}{k}x^k \sum_{k=0} ^{\infty} \binom{-(r+1)}{k}x^k = \sum_{k=0} ^{\infty} \binom{m-r-1}{k}x^k$$

I know I can determine the coefficient of $x^n$ by writing $\sum a_k b_{n-k}=c_n$.

Answer 1

First of all, your formula for negative powers makes no sense. Your variables are all messed up. The power you're raising stuff to is $n$, which is also the index for your sum and $k$ is undefined. The formula on the RHS appears to be the expansion of $(1+x)^{-k}$, but I find its easiest to just recompute these things and doing so will give us a more convenient form of the formula anyway.

The correct approach is the following.

Start with the geometric series: $$\frac{1}{1-x} = \sum_{i=0}^\infty x^i.$$ Then raise both sides to the $k$th power, to get $$(1-x)^{-k} = \left(\sum_{i=0}^\infty x^i\right)^k.$$ The coefficient of $x^\ell$ in the right hand side is the number of ways to choose $k$ distinct, ordered nonnegative integers that sum to $\ell$. This is the stars and bars problem, and has the well known solution $\binom{\ell+k-1}{k-1}$. Thus we have $$(1-x)^{-k} = \sum_{i=0}^\infty \binom{i+k-1}{k-1} x^i.$$ Finally, substitute $-x$ for $x$ to get $$(1+x)^{-k} = \sum_{i=0}^\infty \binom{i+k-1}{k-1} (-1)^i x^i.$$

I think this might be equivalent to the formula you've given, but nonetheless, I believe they want you to use this form of it, since it has the appropriate $(-1)^i$ that your formula is missing.

Now, if we multiply $(1+x)^m(1+x)^{-(r+1)}$, apply the formula and then take the coefficient of $m-r$, we get $$\sum_{s=0}^{m-r} \binom{m}{s}\binom{(m-r-s) + (r+1) -1}{(r+1)-1}(-1)^{m-s}$$ $$=\sum_{s=0}^{m-r} \binom{m}{s}\binom{m-s}{r}(-1)^{m-s}.$$

Now if we reindex, with the new $s$ being $m-s$, we find that the sum runs from $r$ to $m$, and we have $$=\sum_{s=r}^m \binom{m}{m-s}\binom{s}{r}(-1)^s=\sum_{s=r}^m\binom{m}{s}\binom{s}{r}(-1)^s.$$

The coefficient of $x^{m-r}$ on the right hand side is obviously zero, since the rhs has degree $m-r-1$, so we get $$\sum_{s=r}^m\binom{m}{s}\binom{s}{r}(-1)^s=0,$$ as desired.

Answer 2

Here is the combinatorial solution no one asked for.

First of all, when $m=r$ the actual value of the LHS is $(-1)^m$, so from now on assume $m\neq r$. We will answer the following question in two ways:

How many of the size $r$ subsets of an $m$ element set have size equal to $m$?

Answer 1: Obviously zero, since $m\neq r$, so there are no sets with sizes equal to both $m$ and $r$! (Note when $m=r$, this answer would instead be $1$).

Answer 2: We will answer this using inclusion exclusion. First, the total number of subsets of size $r$ is $\binom{m}r$. For each element $i$ of the set, we must subtract the "bad" size $r$ subsets which do not contain $i$ (if a set has size unequal to $m$, it must be missing some element). There are $\binom{m-1}r$ subsets of size $r$ which do not contain $i$, and $\binom{m}1$ ways to choose $i$. But then we must add back in the double intersections, then subtract the triple intersections, and so on. The result is $$ \binom{m}0\binom{m}r-\binom{m}1\binom{m-1}r+\binom{m}2\binom{m-2}r-\dots=\sum_{s\ge 0}(-1)^s\binom{m}s\binom{m-s}r $$ which after some rearranging is $(-1)^m$ times the desired summation.

Answer 3

Here is another combinatorial solution to the problem which no one asked for.

Assume, $m>r$. For a given $s$, $\binom{m}{s} \binom{s}{r}$ counts the number of ordered pairs $(X,Y)$ such that $Y\subseteq X\subseteq \{1,2,...,m\},\mid X\mid =s, \mid Y\mid =r$.

Given $(X,Y)$, let $x$ be the smallest element of $\{1,2,...,m\}$ such that $x$ is not in $Y$. Then define the involution $f((X,Y)) = (X\oplus x, Y )$. $\Bigg( X\oplus x=\begin{cases} X\setminus \{x\} & x\in X\\ X\cup \{x\} & x\notin X\\ \end{cases}\Bigg) $

Therefore, $f((X,Y))$ is a bijection from the ordered pairs $(X,Y)$ such that $Y\subseteq X\subseteq \{1,2,...,m\} $ with $\mid X\mid $ even to ordered pairs $(X,Y)$ such that $Y\subseteq X\subseteq \{1,2,...,m\} $ with $\mid X\mid $ odd.

Hence, $$\sum_\limits {s\ even}\binom{m}{s} \binom{s}{r}=\sum_\limits {s\ odd}\binom{m}{s} \binom{s}{r}$$

$\blacksquare$