# How can I prove, that this formula is related to the binomial series?

I am trying to solve the following formula:

$$\sum^{\lfloor (n-1)/2\rfloor}_{m=k}\binom{m}{k}\binom{n}{2m+1} = \binom{n-k-1}{k}2^{n-2k-1}$$

However, I haven't got a clue. Can anybody shed some light on this?

• very much looks like coefficient of some binomial term, the right hand side $\binom{n-k-1}{n-2k-1} 2 ^{n-2k-1}$ – samjoe Dec 15 '17 at 4:57
• So sorry I'm not on laptop now. Can't really type out the answer. Can you try writing the power of $2$ as a sum of binomial coefficients? Some manipulation should be able to help you reach the LHS. – Karn Watcharasupat Dec 15 '17 at 5:02
• yes, i tried but could not get rid of the 2m+1 term – Liang Zhang Dec 15 '17 at 5:12
• Do you mean $\sum_{m=0}^{n-k-1}\binom{m}{k}\binom{n-k-1}{m} = \binom{n-k-1}{k} 2^{n-2k-1}$? – Liang Zhang Dec 15 '17 at 5:14
• Nope I mean apply $$2^z=\sum_{i=0}^z{\binom{z}{i}}$$ on the LHS. – Karn Watcharasupat Dec 15 '17 at 5:26

## 2 Answers

We seek to verify for $n-k-1\ge k$ the identity

$$\sum_{m=k}^{\lfloor (n-1)/2 \rfloor} {m\choose k} {n\choose 2m+1} = {n-k-1\choose k} 2^{n-2k-1}.$$

The LHS is

$$\sum_{m=k}^{\lfloor (n-1)/2 \rfloor} {m\choose k} {n\choose n-2m-1} = \sum_{m=k}^{\lfloor (n-1)/2 \rfloor} {m\choose k} [z^{n-2m-1}] (1+z)^n \\ = \sum_{m=k}^{\lfloor (n-1)/2 \rfloor} {m\choose k} [z^{n}] z^{2m+1} (1+z)^n.$$

Now observe that when $2m+1\gt n$ we get zero from the coefficient extractor so in fact it encodes the upper limit of the summation, which we may extend to infinity since there is no contribution from those values of $m$. We obtain

$$[z^n] (1+z)^n \sum_{m\ge k} {m\choose k} z^{2m+1} = [z^{n-1}] (1+z)^n \sum_{m\ge k} {m\choose k} z^{2m} \\ = [z^{n-1}] (1+z)^n \sum_{m\ge 0} {m+k\choose k} z^{2m+2k} = [z^{n-2k-1}] (1+z)^n \sum_{m\ge 0} {m+k\choose k} z^{2m} \\ = [z^{n-2k-1}] (1+z)^n \frac{1}{(1-z^2)^{k+1}} = [z^{n-2k-1}] (1+z)^{n-k-1} \frac{1}{(1-z)^{k+1}}.$$

Extracting the coefficient we find

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

The product of binomials is

$$\frac{(n-k-1)!}{q! \times k! \times (n-2k-1-q)!} = {n-k-1\choose k} {n-2k-1\choose q}$$

and we get

$${n-k-1\choose k} \sum_{q=0}^{n-2k-1} {n-2k-1\choose q} = {n-k-1\choose k} 2^{n-2k-1}$$

as claimed.

Here is variation of the theme. It is convenient to use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ in a series. This way we can write for instance \begin{align*} [z^k](1+z)^n=\binom{n}{k} \end{align*}

We obtain for $n\geq 2k+1$: \begin{align*} \color{blue}{\sum_{m=k}^{\left\lfloor\frac{n-1}{2}\right\rfloor}}&\color{blue}{\binom{m}{k}\binom{n}{2m+1}}\\ &=\sum_{m=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}\binom{m+k}{m}\binom{n}{2m+2k+1}\tag{1}\\ &=\sum_{m=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}\binom{-k-1}{m}(-1)^m\binom{n}{n-2m-2k-1}\tag{2}\\ &=\sum_{m=0}^\infty[z^m](1-z)^{-k-1}[u^{n-2m-2k-1}](1+u)^n\tag{3}\\ &=[u^{n-2k-1}](1+u)^n\sum_{m=0}^\infty u^{2m}[z^m](1-z)^{-k-1}\tag{4}\\ &=[u^{n-2k-1}](1+u)^n\left(1-u^2\right)^{-k-1}\tag{5}\\ &=[u^{n-2k-1}](1+u)^{n-k-1}(1-u)^{-k-1}\tag{6}\\ &=\sum_{j=0}^{n-2k-1}\binom{n-k-1}{j}\binom{-k-1}{n-2k-1-j}(-1)^{n-2k-1-j}\tag{7}\\ &\color{blue}{=\sum_{j=0}^{n-2k-1}\binom{n-k-1}{j}\binom{n-k-j-1}{k}}\tag{8}\\ &=\sum_{j=0}^{\infty}[u^j](1+u)^{n-k-1}[z^k](1+z)^{n-k-j-1}\tag{9}\\ &=[z^k](1+z)^{n-k-1}\sum_{j=0}^\infty (1+z)^{-j}[u^j](1+u)^{n-k-1}\tag{10}\\ &=[z^k](1+z)^{n-k-1}\left(1+\frac{1}{1+z}\right)^{n-k-1}\tag{11}\\ &=[z^k](2+z)^{n-k-1}\tag{12}\\ &\color{blue}{=\binom{n-k-1}{k}2^{n-2k-1}}\tag{13} \end{align*} and the claim follows.

Comment:

• In (1) we shift the index $j$ to start from $j=0$.

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

• In (3) we apply the coefficient of operator twice and also set the upper bound to $\infty$ without changing anything since we are adding zeros only.

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

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

• In (6) we rearrange the terms in order to derive another binomial identity from (1) in the next step.

• In (7) we extract the coefficient of $[u^{n-2k-1}]$.

• In (8) we apply the same identity as in (2).

• In (9) we apply the coeffcient of operator twice again.

• In (10) we do a rearrangement similarly as in (4).

• In (11) we apply the substitution rule as we did in (5).

• In (12) we do some simplifications.

• In (13) we select the coefficient of $[z^k]$.

Notes: Two steps might be of special interest.

• (5) to (6): This is the essential twist to derive another binomial identity (8) from (1) which also enables us to finally derive the RHS of OP's claim.

• (11): The transformation \begin{align*} (2+z)^N=\left(1+\frac{1}{1+z}\right)^N(1+z)^N \end{align*} may be helpful sometimes to get rid of the summand $2$.

• Thank you for this explanatory contribution. As an observation, there is a user at this MSE link who is asking for an explanation of the method of formal power series. – Marko Riedel Dec 29 '17 at 0:56
• @MarkoRiedel: You're welcome and many thanks for the hint. I've added an answer. Regards, – Markus Scheuer Dec 29 '17 at 14:21