# Combinatorial proofs of the following identities

I've been trying to find combinatorial proofs of the following two identities:

1: $\displaystyle\sum_{i=0}^{k} \binom{n}{i} = \sum_{i=0}^{k} \binom{n-1-i}{k-i} 2^i$ with $0 \le k \le n-1$

2: $\displaystyle\binom{2m}{2n} = \sum_{k=0}^{n} \binom{2n+1}{2k+1} \binom{m+k}{2n}$

For 1: The LHS is counting the number of subsets of size at most k from a set of size n. The $2^i$ in the RHS makes me think of partitioning based on what elements can be considered from the full set then either including them or not, but I can't think of a way of doing this partition without overcounting and trying to interpret the binomial term hasn't helped.

For 2: Again, the LHS is simple enough but I'm lost on how to interpret the RHS. Just from looking at it I feel like I should be considering some parity argument but haven't come up with anything else.

Any suggestions on how to proceed? Should I be looking for a more formal bijection?

• I have an interesting algebraic proof of the second identity which however I will post only if requested so as not to be in conflict with the intent of the question, which is purely combinatorial. – Marko Riedel Aug 23 '16 at 2:15
• @MarkoRiedel Although it's not exactly what I'm looking for I would still be interested in seeing the algebraic proof as well – waterman butterfly Aug 23 '16 at 20:24
• Done. As I am not the only user doing these types of proofs you can expect interesting mathematics to appear on this page in addition to combinatorics which is frequently the most successful and straightforward approach to these types of sums. – Marko Riedel Aug 23 '16 at 21:04
• I can prove the second one if somebody can prove that $$\sum_{b=k}^n\,(-1)^{b-k}\,\binom{b}{k}\,\binom{2n-b}{b}\,2^{2(n-b)}\,=\,\binom{2n+1}{2k+1}\,.$$ – Batominovski Aug 23 '16 at 22:50
• I saw your comment only just now (working) and I encourage you to continue using either formal power series or Egorychev. – Marko Riedel Aug 23 '16 at 23:36

Suppose we seek to show that

$${2m\choose 2n} = \sum_{k=0}^n {2n+1\choose 2k+1} {m+k\choose 2n}.$$

where $m\ge n.$ We introduce

$${2n+1\choose 2k+1} = {2n+1\choose 2n-2k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2n-2k+1}} (1+z)^{2n+1} \; dz.$$

Observe that this vanishes when $k\gt n$ so that we may use it to control the range and extend $k$ to infinity. We also use

$${m+k\choose 2n} = \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{2n+1}} (1+w)^{m+k} \; dw.$$

We thus obtain

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n+1}}{z^{2n+1}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^{m}}{w^{2n+1}} \sum_{k\ge 0} z^{2k} (1+w)^k \; dw\; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n+1} }{z^{2n+1}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^{m}}{w^{2n+1}} \frac{1}{1-(1+w)z^2} \; dw\; dz.$$

Evalute the inner integral using the negative of the residue at the pole at $$w=\frac{1-z^2}{z^2}$$ (residues sum to zero) as in

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n+1} }{z^{2n+1}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^{m}}{w^{2n+1}} \frac{1}{1-z^2 - wz^2} \; dw\; dz \\ = - \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n+1} }{z^{2n+3}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^{m}}{w^{2n+1}} \frac{1}{w-(1-z^2)/z^2} \; dw\; dz.$$

The negative of the residue is

$$\frac{1}{z^{2m}} \frac{z^{4n+2}}{(1-z^2)^{2n+1}} = \frac{1}{z^{2m-4n-2}} \frac{1}{(1-z^2)^{2n+1}}$$

and we obtain from the outer integral

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n+1} }{z^{2n+3}} \frac{1}{z^{2m-4n-2}} \frac{1}{(1-z^2)^{2n+1}} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2m-2n+1}} \frac{1}{(1-z)^{2n+1}} \; dz \\ = {2m-2n+2n\choose 2n} = {2m\choose 2n}.$$

This is the claim.

Remark. We also need to show that the contribution from the residue at infinity of the inner integral is zero. We get

$$\mathrm{Res}_{w=\infty} \frac{(1+w)^{m}}{w^{2n+1}} \frac{1}{1-(1+w)z^2} \\ = - \mathrm{Res}_{w=0} \frac{1}{w^2} (1+1/w)^{m} w^{2n+1} \frac{1}{1-z^2-z^2/w} \\ = - \mathrm{Res}_{w=0} (1+w)^{m} w^{2n-m} \frac{1}{w(1-z^2)-z^2}.$$

No contribution when $2n\ge m.$ Otherwise,

$$\frac{1}{z^2} \mathrm{Res}_{w=0} (1+w)^{m} \frac{1}{w^{m-2n}} \frac{1}{1-w(1-z^2)/z^2} \\ = \frac{1}{z^2} \sum_{q=0}^{m-2n-1} {m\choose m-2n-1-q} \frac{(1-z^2)^q}{z^{2q}} \\ = \frac{1}{z^2} \sum_{q=0}^{m-2n-1} {m\choose 2n+1+q} \left(\frac{1}{z^2}-1\right)^q$$

Combining this with the integral in $z$ yields

$$\sum_{q=0}^{m-2n-1} {m\choose 2n+1+q} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n+1} }{z^{2n+1}} \frac{1}{z^2} \sum_{p=0}^q {q\choose p} (-1)^{q-p} \frac{1}{z^{2p}} \; dz.$$

The contribution from the residue is

$$[z^{2n+2+2p}] (1+z)^{2n+1} = 0.$$

We can express this verbally by saying that the term from the integral is $[z^{2n}] (1+z)^{2n+1} = 0$ and the sum only contributes negative powers of $z$ with exponent starting at two.

Remark, II. From the convergence we require that $|z^2(1+w)| < 1$ in the double integral and must choose our contours appropriately. We must also verify that $(1-z^2)/z^2$ is outside the contour $|w|=\gamma.$ This is $1/z^2-1$ i.e. a circle of radius $1/\epsilon^2$ shifted by one to the left. Therefore when $\epsilon < 1/\sqrt{2}$ the pole is outside the contour.

To get you started, here’s a HINT for the first identity:

• Show that $\binom{n-1-i}{k-i}2^i$ is the number of subsets $A$ of $[n]=\{1,\ldots,n\}$ of cardinality at most $k$ such that $i+1\notin A$, and $|A\setminus[i]|=k-i$. That is $i+1$ is not in $A$, and $A$ has $k-i$ elements bigger than $i$.

• Suppose that $A\subseteq[n]$ has at most $k$ elements, and let $d=k-|A|$. Let $i$ be the largest integer such that $|[i]\setminus A|=d$. If $d=0$, for example, this means that $i+1$ is the smallest member of $[n]$ not in $A$. If $d=1$, $i+1$ is the second-smallest member of $[n]$ not in $A$. Show that such $i$ always exists. (Clearly it’s uniquely determined by $A$ if it does exist.)

I’ll have to think further about the second one.

• I'm not sure I follow this. Say n=5, k=3, and i=2. Then this says there should be $\binom{2}{1}2^2=8$ subsets that contain 1 and 2 but not 3, but there are only 3 subsets of this form ({1,2}, {1,2,4}, {1,2,5}). Further, if k=i then there should only be one set of this form ({1,...,k}) but the formula suggests there would be $2^k$. Am I missing something? – waterman butterfly Aug 23 '16 at 19:35
• @watermanbutterfly: You’re right: I was mentally converting from one representation to another when I wrote that, and I loused it up. I’ve now corrected it. However, it still needs a bit of work in order to be useful, so I’m probably going to delete it in a bit. – Brian M. Scott Aug 23 '16 at 19:47
• As is, this would be choosing the $k-i$ elements larger than i in $\binom{n-1-i}{k-i}$ ways, then there are $2^i$ choices for the whether the subset contains each number in $[i]$, right? This is close to what I was initially thinking but wouldn't this over count some subsets? – waterman butterfly Aug 23 '16 at 19:56
• @watermanbutterfly: It won’t overcount if you choose $i$ correctly for each $A$. That’s what I was just now verifying, and I’ve added a pointer for it. (Always assuming that I’ve not had another mental hiccup, of course.) – Brian M. Scott Aug 23 '16 at 20:02

Since a proof of my identity has been given, I shall give a proof which is partly combinatorial. The combinatorial part is as follows. For integers $a,b$ such that $a\leq b$, write $$[a,b]:=\{a,a+1,\ldots,b-1,b\}\,.$$ Consider a subset $S\subseteq [1,2m]$ of size $2n$. There are $\dbinom{2m}{2n}$ ways to choose such subsets. Write $S_1:=S\cap[1,m]$ and $$S_2:=\big(S\cap[m+1,2m]\big)-m=\big\{s-m\,\big|\,s\in S\cap[m+1,2m]\big\}\,.$$ We are counting the number of subsets $S$ of $[1,2m]$ of size $2n$ with $\left|S_1\cap S_2\right|=j$ for each $j=0,1,2,\ldots,n$.

First, there are $\dbinom{m}{2n-j}$ ways to choose $S_1\cup S_2$. Amongst the $2n-j$ chosen numbers, we can choose $S_1\cap S_2$ in $\dbinom{2n-j}{j}$ ways. That leaves $2(n-j)$ elements each of which can either belong only in $S_1$ or only in $S_2$. Thus, $$\binom{2m}{2n}=\sum_{j=0}^n\,\binom{m}{2n-j}\,\binom{2n-j}{j}\,2^{2(n-j)}\,.\tag{1}$$

We shall now prove that, for integers $M,N,K$ with $0\leq K\leq N\leq M$, we have $$\binom{M}{N-K}=\sum_{i=0}^K\,(-1)^i\,\binom{K}{i}\,\binom{M+K-i}{N}\,.\tag{2}$$ The left-hand side is the number of ways to choose $N$ elements from $[1,M+K]$ such that every number in $[M+1,M+K]$ is selected. The right-hand side is a direct result of the Principle of Inclusion and Exclusion, noting that $\dbinom{K}{i}$ is the number of ways to select $i$-subsets $T$ of $[M+1,M+K]$ and $\dbinom{M+K-i}{N}$ is precisely the number of ways to choose an $N$-subset of $[1,M+K]\setminus T$.

From (1) and (2), we get $$\binom{2m}{2n}=\sum_{j=0}^n\,\sum_{i=0}^j\,(-1)^{i}\,\binom{j}{i}\,\binom{m+j-i}{2n}\,\binom{2n-j}{j}\,2^{2(n-j)}\,.$$ Let $k:=j-i$ and, by reindexing, we have $$\binom{2m}{2n}=\sum_{k=0}^n\,\binom{m+k}{2n}\,\sum_{j=k}^n\,(-1)^{j-k}\,\binom{j}{k}\,\binom{2n-j}{j}\,2^{2(n-j)}\,.$$ This is where my identity (now with a combinatorial proof---at least partially) comes in, and we are done with $$\binom{2m}{2n}=\sum_{k=0}^n\,\binom{m+k}{2n}\,\binom{2n+1}{2k+1}\,.$$

Here is another variation based upon the usage of the coefficient of operator $[z^k]$ to denote the coefficient of $z^k$ in a series. This way we can write e.g. \begin{align*} [z^k](1+z)^n=\binom{n}{k} \end{align*}

We start with (2) and obtain for $0\leq n\leq m$ \begin{align*} \sum_{k=2n-m}^m&\binom{2n+1}{2k+1}\binom{m+k}{2n}\tag{1}\\ &=\sum_{k=0}^{2m-2n}\binom{2n+1}{4n-2m+2k+1}\binom{2n+k}{2n}\tag{2}\\ &=\sum_{k=0}^{2m-2n}\binom{2n+1}{2m-2n-2k}\binom{-(2n+1)}{k}(-1)^k\tag{3}\\ &=\sum_{k=0}^{\infty}[z^{2m-2n-2k}](1+z)^{2n+1}[u^{k}](1+u)^{-(2n+1)}(-1)^k\tag{4}\\ &=[z^{2m-2n}](1+z)^{2n+1}\sum_{k=0}^\infty\left(-z^2\right)^k[u^k](1+u)^{-(2n+1)}\tag{5}\\ &=[z^{2m-2n}](1+z)^{2n+1}(1-z^2)^{-(2n+1)}\tag{6}\\ &=[z^{2m-2n}](1-z)^{-(2n+1)}\\ &=[z^{2m-2n}]\sum_{k=0}^\infty\binom{-(2n+1)}{k}(-z)^k\tag{7}\\ &=\binom{-(2n+1)}{2m-2n}\tag{8}\\ &=\binom{2m}{2n}\tag{9} \end{align*} and the claim follows.

Comment:

• In (1) we sum starting from $k=2n-m$, since $\binom{m+k}{2n}=0$ for $0\leq k<2n-m$.

• In (2) we shift the index $k$ to start from zero.

• In (3) we use the binomial identities $\binom{p}{q}=\binom{p}{p-q}$ and $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.

• In (4) we apply the coefficient of operator twice and extend to upper limit of the series to $\infty$ without changing anything since we are adding zeros only.

• In (5) we use the linearity of the coefficient of operator and apply the rule $[z^{p+q}]A(z)=[z^p]z^{-q}A(z)$.

• In (6) we apply the substitution rule with $u=-z^2$ \begin{align*} A(z)=\sum_{k=0}^\infty a_kz^k=\sum_{k=0}^\infty z^k [u^k]A(u) \end{align*}

• In (7) we use the binomial series expansion

• In (8) we select the coefficient of $z^{2m-2n}$.

• In (9) we apply the identity $\binom{-p}{q}=\binom{p+q-1}{p-1}(-1)^q$.

Using the same technique we show (1): \begin{align*} \sum_{i=0}^k\binom{n}{i}=\sum_{i=0}^k\binom{n-1-i}{k-i}2^i \end{align*}

We obtain \begin{align*} \sum_{i=0}^k\binom{n-1-i}{k-i}2^i &=\sum_{i=0}^\infty[z^{k-i}](1+z)^{n-1-i}2^i\\ &=[z^k](1+z)^{n-1}\sum_{i=0}^\infty\left(\frac{2z}{1+z}\right)^i\\ &=[z^k](1+z)^{n-1}\frac{1}{1-\frac{2z}{1+z}}\\ &=[z^k](1+z)^{n}\frac{1}{1-z}\\ &=[z^k]\sum_{i=0}^\infty z^i(1+z)^{n}\\ &=\sum_{i=0}^k [z^{k-i}](1+z)^{n}\\ &=\sum_{i=0}^k \binom{n}{k-i}\\ &=\sum_{i=0}^k \binom{n}{i}\\ \end{align*}

and the claim follows.

• Congratulations! (+1) Nice to know that we can do the difficult one using formal power series without substituting into a complex integral. I am sure potential readers of the page will be happy to see this. (I checked the first one and it appears to be correct.) – Marko Riedel Aug 29 '16 at 20:12
• @MarkoRiedel: Thanks for your nice comment and your review! :-) It's also often a pleasure for me to go through your answers! (+1) – Markus Scheuer Aug 30 '16 at 8:18