A combinatorial identity with binomial coefficients and floor function.

Question

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 1

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.

Answer 2

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.

Answer 3

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