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

Solution 1:

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.

Solution 2:

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