Combinatorial Identity with powers of 2

Question

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

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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