# Combinatorial Identity with powers of 2

The following problem is from MOP 2007.

Prove that $$\sum_{i=0}^n\binom{n}{2i+1}\binom{i}{m}=2^{n-2m-1}\binom{n-m-1}{m}$$

I tried to approach this using generating functions:

Let $f(X),g(X)$ be defined as: $$f(X)=\sum_{n\geq 0}\left[\sum_{i=0}^n\binom{n}{2i+1}\binom{i}{m}\right]X^n$$ $$g(X)=\sum_{n\geq 0}\left[2^{n-2m-1}\binom{n-m-1}{m}\right]X^n$$

To evaluate $f$, we can swap the order of summation and separate the binomials to get: $$f(X)=\sum_{i\geq 0}\sum_{n\geq i}\binom{n}{2i+1}\binom{i}{m}X^n=\sum_{i\geq 0}\binom{i}{m}\sum_{n\geq i}\binom{n}{2i+1}X^n$$

However, using the well known generating function $$\sum_{k\geq 0}\binom{k}{m}X^k=\frac{X^m}{(1-X)^{m+1}}$$ we get by evaluating the inner summation that$$f(X)=\sum_{i\geq 0}\binom{i}{m}\frac{x^{2i+1}}{(1-X)^{2i+2}}$$

At this point, I'm not sure how to evaluate this sum in closed form (or, if this is even possible). But fortunately we don't need to evaluate it, we just need to show it is equivalent to $g(X)$.

However, I wasn't able to get anywhere with this. I was wondering if we could use the generating function I mentioned earlier to do so. We can write $$g(X)=X^{2m+1}\left(\binom{m}{m}+2^1\binom{m+1}{m}X+2^2\binom{m+2}{m}X^2+2^3\binom{m+3}{m}X^3+\dots\right)$$

Using that generating function I mentioned earlier, this can be written as $$g(X)=\frac{1}{(1-X)^{m+1}}+\left(\frac{X}{(1-X)^{m+1}}-X\right)+\left(\frac{2X^2}{(1-X)^{m+1}}-X^2-\binom{m+1}{m}X^2\right)+\dots$$

Which happens to resemble a geometric series, but with some left over terms being subtracted off. Not sure if there is a clever way to evaluate this.

Or maybe I'm just going the wrong way, any thoughts?

(Also, ideas of a combinatorial proof would be nice to see as well!)

Update (due to Lord Shark):

Using the above generating function again, we can write $f$ in closed form as $$f(x)=\frac{X^{2m+1}}{(1-2X)^{m+1}}$$

Looks like it remains to investigate $g(x)$.

• I would consider summing over $m$ as well, and adding another variable $y^m$. I don't have time to try it myself at the moment, though. Apr 14, 2017 at 16:51
• Thanks for the input. I will keep this in mind.
– Max
Apr 14, 2017 at 16:54
• This looks to be a duplicate or at any rate a very close match of the following MSE link. Apr 14, 2017 at 21:46
• Yeah, it's pretty much the same question (slightly different question, though can be solved mucht he same way). Anyways, I found an elementary solution to this problem which I figured I'd post.
– Max
Apr 14, 2017 at 23:10

Your $f(X)$ is $$\sum_{i=m}^\infty{i\choose m}\frac{X^{2i+1}}{(1-X)^{2i+2}} =\frac{X}{(1-X)^2}\frac{(X^2/(1-X)^2)^m}{(1-X^2/(1-X)^2)^{m+1}}$$ (using the principle in your previous line). This simplifies to $$\frac{X^{2m+1}}{(1-2X)^{m+1}}.$$

• You have an extra $2$ in the denominator of your first expression, which the OP didn't have. Are you sure you're right? Apr 14, 2017 at 17:00
• Awesome! I wonder how I didnt see that it was the same generating function, just with $X$ replaced by $\left(\frac{X}{1-X^2}\right)^2$ (after pulling out a $\frac{X}{(1-X)^2}$). I'll update the original post and try the problem some more when I have the time. Any thoughts on $g(X)$?
– Max
Apr 14, 2017 at 21:19

Okay so it's not actually hard to get either $f(X)$ or $g(X)$, you just need to keep on using the well known generating function which I mentioned earlier.

Above, we have already shown that the generating function for $f$ is $$f(X)=\frac{X^{2m+1}}{(1-2X)^{m+1}}$$ We will show that the generating function for $g$ is the same. Rewrite $g$ as

$$g(X)=\frac{X^{m+1}}{2^m}\sum_{n\geq 0}\binom{n-m-1}{m}(2X)^{n-m-1}=\frac{X^{m+1}}{2^m}\sum_{j\geq 0}\binom{j}{m}X^j$$

Now we can use that generating function to get $$g(X)=\frac{X^{m+1}}{2^m}\frac{(2X)^m}{(1-2X)^{m+1}}=\frac{X^{2m+1}}{(1-2X)^{m+1}}$$

Equating coefficiants of the generating functions tells us the left hand side and right hand side of the original equaion are indeed equal for all $n$.

Here is a variation which transforms the left-hand side into the right-hand side. In order to do so we use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ in a series. This way we can write e.g. \begin{align*} [z^k](1+z)^n=\binom{n}{k} \end{align*}

We obtain for $0\leq m\leq n$:

\begin{align*} \sum_{i=0}^n\binom{n}{2i+1}\binom{i}{m}&=\sum_{i= m}^\infty\binom{n}{n-2i-1}\binom{i}{m}\tag{1}\\ &=\sum_{i= 0}^\infty\binom{n}{n-2i-2m-1}\binom{i+m}{m}\tag{2}\\ &=\sum_{i= 0}^\infty\binom{n}{n-2i-2m-1}\binom{-m-1}{i}(-1)^i\tag{3}\\ &=\sum_{i= 0}^\infty[z^{n-2i-2m-1}](1+z)^n[u^i](1-u)^{-m-1}\tag{4}\\ &=[z^{n-2m-1}](1+z)^n\sum_{i= 0}^\infty z^{2i}[u^i](1-u)^{-m-1}\tag{5}\\ &=[z^{n-2m-1}](1+z)^n(1-z^2)^{-m-1}\tag{6}\\ &=[z^{n-2m-1}](1+z)^{n-m-1}(1-z)^{-m-1}\tag{7}\\ &=\sum_{i=0}^{n-m-1}\binom{n-m-1}{i}[z^{n-2m-1-i}]\sum_{j= 0}^\infty\binom{j+m}{j}\tag{8}\\ &=\sum_{i=0}^{n-m-1}\binom{n-m-1}{n-m-1-i}\binom{n-m-1-i}{n-2m-1-i}\tag{9}\\ &=\binom{n-m-1}{m}\sum_{i=0}^{n-m-1}\binom{n-2m-1}{i}\tag{10}\\ &=2^{n-2m-1}\binom{n-m-1}{m} \end{align*} and the claim follows.

Comment:

• In (1) we start with index $i=m$ since $\binom{i}{m}=0$ for $0\leq i<m$. We also set the upper limit of the series to $\infty$ without changing anything since we are adding zeros only. We also use the binomial identity $\binom{p}{q}=\binom{p}{p-q}$.

• In (2) we shift the index to start from $i=0$.

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

• In (4) we apply the coefficient of operator twice.

• In (5) we use the linearity of the coefficient of operator and apply the rule \begin{align*} [z^{p-q}]A(z)=[z^p]z^qA(z) \end{align*}

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

• In (7) we use $1-z^2=(1-z)(1+z)$.

• In (8) we do a binomial series expansion of $(1+z)^{n-m-1}$ and select the coefficient of $z^{n-2m-1}$. We restrict the upper limit of the sum with $n-2m-1$ since the exponent of $z$ is non-negative.

• In (9) we select the coeffcient of $z^{n-2m-1-i}$ and use again $\binom{p}{q}=\binom{p}{p-q}$.

• In (10) we apply the binomial identity $\binom{r}{m}\binom{m}{k}=\binom{r}{k}\binom{r-k}{m-k}$ and observe that one factor does not depend on the index $i$.

Note: This answer was inspired by this post from @MarkoRiedel.

$\newcommand{\bbx}{\,\bbox[8px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}{\displaystyle{#1}} \newcommand{\expo}{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}{\mathcal{#1}} \newcommand{\mrm}{\mathrm{#1}} \newcommand{\pars}{\left(\,{#1}\,\right)} \newcommand{\partiald}[]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}{\left\vert\,{#1}\,\right\vert}$

Note that only terms with $\ds{m \leq i \leq {n - 1 \over 2}}$ make a contribution to the sum. Also, it yields $\ds{n \geq 2m + 1}$.

\begin{align} \sum_{i = 0}^{n}{n \choose 2i + 1}{i \choose m} & = \sum_{k = m}^{\infty}{n \choose n - 2k - 1}{k \choose k - m} = \sum_{k = m}^{\infty}{n \choose n - 2k - 1}{-m - 1 \choose k - m} \pars{-1}^{k - m} \\[5mm] & = \sum_{k = 0}^{\infty}{n \choose n - 2m - 1 - 2k}{-m - 1 \choose k} \pars{-1}^{k} \\[5mm] & = \sum_{k = 0}^{\infty}{-m - 1 \choose k}\pars{-1}^{k} \oint_{\verts{z} = 1^{-}}{\pars{1 + z}^{n} \over z^{n - 2m - 2k}} \,{\dd z \over 2\pi\ic} \\[5mm] & = \oint_{\verts{z} = 1^{-}}{\pars{1 + z}^{n} \over z^{n - 2m}} \sum_{k = 0}^{\infty}{-m - 1 \choose k}\pars{-z^{2}}^{k}\,{\dd z \over 2\pi\ic} \\[5mm] & = \oint_{\verts{z} = 1^{-}}{\pars{1 + z}^{n} \over z^{n - 2m}} \pars{1 - z^{2}}^{-m - 1}\,{\dd z \over 2\pi\ic} = \oint_{\verts{z} = 1^{-}} {\pars{1 + z}^{n - m - 1} \over z^{n - 2m}\pars{1 - z}^{m + 1}} \,{\dd z \over 2\pi\ic} \\[5mm] & \stackrel{z\ \mapsto\ 1/z}{=}\,\,\, \oint_{\verts{z} = 1^{+}} {\pars{1 + z}^{n - m - 1} \over \pars{z - 1}^{m + 1}} \,{\dd z \over 2\pi\ic} \\[5mm] & = \oint_{\verts{z} = 1^{+}} {2^{n - m - 1}\bracks{1 + \pars{z - 1}/2}^{n - m - 1} \over \pars{z - 1}^{m + 1}}\,{\dd z \over 2\pi\ic} \\[5mm] & = 2^{n - m - 1}\sum_{k = 0}^{n - m - 1}{n - m - 1 \choose{k}}{1 \over 2^{k}}\ \underbrace{\oint_{\verts{z} = 1^{+}} {1 \over \pars{z - 1}^{m + 1 - k}}\,{\dd z \over 2\pi\ic}}_{\ds{\delta_{km}}} \\[5mm] & = \bbx{\ds{2^{n - 2m - 1}{n - m - 1 \choose m}}} \end{align}