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

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

• Is there a missing sum sign somewhere in your first equation? – Connor Harris Nov 30 '18 at 17:15
• Yes, I made some typos with the indices and summations – Wesley Strik Nov 30 '18 at 22:52

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.

• I'm impressed by how you were able to answer my question so well with me doing a horrible job with the notation. Thank you. – Wesley Strik Nov 30 '18 at 23:10

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.

• I appreciate your combinatorial proof :) – Wesley Strik Nov 30 '18 at 22:59
• You're the unappreciated maths hero that nobody asked for, but, I'm glad you're around ^^ – Wesley Strik Nov 30 '18 at 23:16
• I like the general approach of counting something in two different ways and both methods require some creativity and 'coefficient yoga'. – Wesley Strik Nov 30 '18 at 23:18

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