2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Patrick Stevens Apr 14 '17 at 16:51
  • $\begingroup$ Thanks for the input. I will keep this in mind. $\endgroup$ – Max Apr 14 '17 at 16:54
  • $\begingroup$ This looks to be a duplicate or at any rate a very close match of the following MSE link. $\endgroup$ – Marko Riedel Apr 14 '17 at 21:46
  • $\begingroup$ 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. $\endgroup$ – Max Apr 14 '17 at 23:10
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ You have an extra $2$ in the denominator of your first expression, which the OP didn't have. Are you sure you're right? $\endgroup$ – Patrick Stevens Apr 14 '17 at 17:00
  • $\begingroup$ 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)$? $\endgroup$ – Max Apr 14 '17 at 21:19
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

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