Htykuut

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

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^iright)^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}^mbinom{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}^mbinom{m}{s}binom{s}{r}(-1)^s=0,$$
as desired.

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 $mneq 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 $mneq 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}0binom{m}r-binom{m}1binom{m-1}r+binom{m}2binom{m-2}r-dots=sum_{sge 0}(-1)^sbinom{m}sbinom{m-s}r
$$
which after some rearranging is $(-1)^m$ times the desired summation.

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 $Ysubseteq Xsubseteq {1,2,...,m},mid Xmid =s, mid Ymid =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)) = (Xoplus x, Y )$.
$Bigg( Xoplus x=begin{cases}
Xsetminus {x} & xin X\
Xcup {x} & xnotin X\
end{cases}Bigg)
$

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

Hence, $$sum_limits {s even}binom{m}{s} binom{s}{r}=sum_limits {s odd}binom{m}{s} binom{s}{r}$$

$blacksquare$