combinatorics - A combinatorial identity with binomial coefficients and floor function.

Show that $$\sum_{m=0}^{2k+1}{2^{m}\binom{n}{m}\binom{n-m}{\bigl\lfloor \frac{2k+1-m}{2} \bigr\rfloor}}=\binom{2n+1}{2k+1}$$
I tried expending the sum and using induction, but could not complete the induction step; I tried using Pascal's identity to obtain $$\binom{n-m}{\bigl\lfloor \frac{2k+3-m}{2} \bigr\rfloor}=\binom{n-m+1}{\bigl\lfloor \frac{2k+3-m}{2} \bigr\rfloor}-\binom{n-m}{\bigl\lfloor \frac{2k+1-m}{2} \bigr\rfloor}$$ but couldn't find other identities to complete the induction step. Searching Gould's Combinatorial Identities brought up nothing, though I could easily had missed something useful there.

I'm looking to complete the induction step, but would also like to find an algebraic or a combinatorial proof. I would like to avoid using trigonometric and root functions, but would like to use complex numbers in cartesian form.

Answer

Note: This answer is the result of an analysis of the highly instructive and elegant answer by Marko Riedel. One highlight is the useful representation of $\binom{n}{\left\lfloor \frac{q}{2}\right\rfloor}$ which is the introductory part of this answer.

We use the coefficient of operator $[z^q]$ to denote the coefficient of $z^q$ in a series. This way we can write e.g.
$$\begin{align*} \binom{n}{q}=[z^q](1+z)^n\tag{1} \end{align*}$$
and to ease comparison with Markos answer I will use his notation.

Preliminary:

The following is valid
$$\begin{align*} \binom{n}{\left\lfloor \frac{q}{2}\right\rfloor}=[z^qw^n]\frac{(1+z)(1+w)^n}{1-wz^2}\tag{2} \end{align*}$$

With $q$ even, $q\rightarrow 2q$ we obtain
$$\begin{align*} [z^{2q}w^n]\frac{(1+z)(1+w)^n}{1-wz^2}&=[w^n](1+w)^n[z^{2q}](1+z)\sum_{j=0}^\infty w^j z^{2j}\tag{3}\\ &=[w^n](1+w)^nw^q\tag{4}\\ &=[w^{n-q}](1+w)^n\tag{5}\\ &=\binom{n}{n-q}=\binom{n}{q} \end{align*}$$
With $q$ odd, $q\rightarrow 2q+1$ we obtain
$$\begin{align*} [z^{2q+1}w^n]\frac{(1+z)(1+w)^n}{1-wz^2}&=[w^n](1+w)^n[z^{2q+1}](1+z)\sum_{j=0}^\infty w^j z^{2j}\\ &=[w^n](1+w)^nw^q\\ &=[w^{n-q}](1+w)^n\\ &=\binom{n}{n-q}=\binom{n}{q} \end{align*}$$

Comment:

• Additionally to (1) we use a second variable $z$ which is used as marker to select via $1+z$ even and odd exponent of $w^j$.




• In (3) we use the geometric series expansion and the linearity of the coefficient of operator.




• In (4) we select the coefficient of $z^{2q}$ which is $w^q$.





• In (5) we apply the rule $[z^p]z^qA(z)=[z^{p-q}]A(z)$.

We now apply (2) to OPs formula and obtain
$$\begin{align*} \sum_{k=0}^{2m+1}&\binom{n}{k}2^k\binom{n-k}{\left\lfloor\frac{2m+1-k}{2}\right\rfloor}\\ &=\sum_{k=0}^n\binom{n}{k}2^k[z^{2m+1-k}w^{n-k}]\frac{(1+z)(1+w)^{n-k}}{1-wz^2}\tag{6}\\ &=[z^{2m+1}](1+z)[w^n]\frac{(1+w)^n}{1-wz^2}\sum_{k=0}^n\binom{n}{k}\left(\frac{2wz}{1+w}\right)^k\tag{7}\\ &=[z^{2m+1}](1+z)[w^n]\frac{(1+w)^n}{1-wz^2}\left(1+\frac{2wz}{1+w}\right)^n\\ &=[z^{2m+1}](1+z)[w^n]\frac{(1+w(1+2z))^n}{1-wz^2}\tag{8}\\ &=[z^{2m+1}](1+z)[w^n]\sum_{q=0}^n\binom{n}{q}w^q(1+2z)^q\sum_{j=0}^\infty w^jz^{2j}\\ &=[z^{2m+1}](1+z)\sum_{q=0}^n\binom{n}{q}[w^{n-q}](1+2z)^q\sum_{j=0}^\infty w^jz^{2j}\\ &=[z^{2m+1}](1+z)\sum_{q=0}^n\binom{n}{q}(1+2z)^q\left(z^2\right)^{n-q}\\ &=[z^{2m+1}](1+z)(1+2z+z^2)^n\\ &=[z^{2m+1}](1+z)^{2n+1}\\ &=\binom{2n+1}{2m+1} \end{align*}$$

and the claim follows.

Comment:

• In (6) we apply the formula (2) and we change the upper limit of the sum to $n$ without changing anything, since the formula (2) selects the proper range.




• In (7) we collect all factors with exponent $k$.




• In (8) observe the factor $(1+w)^n$ cancels nicely.