2
$\begingroup$

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

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

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Wesley Strik Nov 30 '18 at 23:10
2
$\begingroup$

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.

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

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$

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