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.

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.

• Very nice. (+1). This completes the page and the reader should have no trouble following the proof by studying and contrasting the two versions. There is a reason why you are at 34K. Jan 8, 2017 at 18:27
• @MarkoRiedel: Thanks a lot, Marko! :-) Jan 8, 2017 at 18:32
• Very nice. I love how your suggested notation made things much easier. Jan 9, 2017 at 10:04
• @BoazK.: You're welcome! Good to see the answer is useful! :-) Jan 9, 2017 at 10:08

Here is a combinatorial proof. The right hand side counts the number of ways to choose $2k+1$ elements from a set with $2n+1$ elements. Fix a partition of the latter set into $n+1$ disjoint subsets, namely a singleton and $n$ two-element subsets.

In order to choose such $2k+1$ elements, first we choose the number $m$ of two-element subsets from which we will select exactly one element. Now we choose such subsets, which can be made in $\binom nm$ ways. Finally, from each one of these $m$ subsets we choose exactly one element; this can be made in $2^m$ ways.

It remains to choose the remaining $2k+1-m$ elements among the elements of the singleton and the remaining $n-m$ two-element members of the partition. Because of the previous step, picking an element of one of these two-element subsets forces us to pick the other element as well. Thus, by choosing $\ell$ of these $n-m$ two-element subsets (which can be made in $\binom{n-m}\ell$ ways) we are adding $2\ell$ elements to our $m$ already chosen elements. In other words, at this point we already chose $2\ell+m$ elements.

The important thing to note is that at this point the value of $\ell$ is determined, that is, we cannot "choose" such value. In fact: if $m$ is even, then we necessarily must pick up the element from the singleton subset, and equality $2\ell+m+1=2k+1$ implies $\ell=\frac{2k-m}2=\bigl\lfloor\frac{2k+1-m}2\bigr\rfloor$; if $m$ is odd then we cannot choose the element from the singleton, and in this case $2\ell+m=2k+1$ implies $\ell=\frac{2k+1-m}2=\bigl\lfloor\frac{2k+1-m}2\bigr\rfloor$.

• Very nice and easy to follow. Jan 9, 2017 at 10:06

Suppose we seek to prove that

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

Observe that from first principles we have that

$${n\choose \lfloor q/2 \rfloor} = {n\choose n-\lfloor q/2 \rfloor} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{q+1}} \\ \times \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^n}{w^{n+1}} \left(1+z +wz^2+wz^3 +w^2z^4+w^2z^5+\cdots\right) \; dw \; dz.$$

This simplifies to

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{q+1}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^n}{w^{n+1}} \left(\frac{1}{1-wz^2}+z\frac{1}{1-wz^2}\right) \; dw \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1+z}{z^{q+1}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^n}{w^{n+1}} \frac{1}{1-wz^2} \; dw \; dz.$$

This correctly enforces the range as the reader is invited to verify and we may extend $k$ beyond $2m+1,$ getting for the sum

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1+z}{z^{2m+2}} \\ \times \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^n}{w^{n+1}} \frac{1}{1-wz^2} \sum_{k\ge 0} {n\choose k} 2^k z^k \frac{w^k}{(1+w)^k} \; dw \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1+z}{z^{2m+2}} \\ \times \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^n}{w^{n+1}} \frac{1}{1-wz^2} \left(1+\frac{2wz}{1+w}\right)^n \; dw \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1+z}{z^{2m+2}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w+2wz)^n}{w^{n+1}} \frac{1}{1-wz^2} \; dw \; dz.$$

Extracting the inner coefficient now yields

$$\sum_{q=0}^n {n\choose q} (1+2z)^q z^{2n-2q} = z^{2n} \sum_{q=0}^n {n\choose q} (1+2z)^q z^{-2q} \\= z^{2n} \left(1+\frac{1+2z}{z^2}\right)^n = (1+z)^{2n}.$$

We thus get from the outer coefficient

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n+1}}{z^{2m+2}} \; dz$$

which is

$$\bbox[5px,border:2px solid #00A000]{ {2n+1\choose 2m+1}}$$

as claimed. I do believe this is an instructive exercise.

• Thank you very much. The eureka effect on radical simplification / cancellation was remarkable. Jan 8, 2017 at 11:18
• @MarkoRiedel: Very nice! Great, Marko! (+1) Jan 8, 2017 at 11:51
• @MarkoRiedel This wasn't the solution I was looking for but I'm happy and grateful as it motivated the solution of Markus Scheuer and that you seem to have taken some pleasure in solving the problem. Jan 9, 2017 at 10:02