# Sum of terms involving binomial coefficients and floor functions

I would like to know how to prove the following identity. Let m be a positive integer. Then

$$\sum_{i=0}^{m+1} (-1)^i \Bigl\lfloor \frac{i}{2} \Bigr\rfloor {2m+1 \choose m+i}=2^{2m-2}$$

Here $\Bigl\lfloor \frac{i}{2} \Bigr\rfloor$ denotes the floor function.

A computational proof is welcome. On the other hand, is it possible to give a combinatorial proof? For example, we interpret the left-hand side as coefficients of a variable in a polynomial.

• Use backslash ('\') for functions like sum, choose, etc. – user_194421 Feb 5 '18 at 3:05

For $i\in\mathbb{Z}$, $$\left\lfloor\frac i2\right\rfloor=\frac i2-\frac14+\frac{(-1)^i}4\tag1$$ Furthermore, $$(-1)^i\binom{i}{1}=(-1)^i\binom{i}{i-1}=-\binom{-2}{i-1}\tag2$$ and $$(-1)^i=\binom{-1}{i}\tag3$$ Thus, \begin{align} &\sum_{i=0}^{m+1}(-1)^i\left\lfloor\frac i2\right\rfloor\binom{2m+1}{m+i}\tag4\\ &=\sum_{i=0}^{m+1}(-1)^i\left(\frac i2-\frac14+\frac{(-1)^i}4\right)\binom{2m+1}{m+i}\tag5\\ &=\color{#C00}{-\frac12\sum_{i=0}^{m+1}\binom{-2}{i-1}\binom{2m+1}{m-i+1}}\color{#090}{-\frac14\sum_{i=0}^{m+1}\binom{-1}{i}\binom{2m+1}{m-i+1}}\\ &\color{#00F}{+\frac14\sum_{i=0}^{m+1}\binom{2m+1}{m+i}}\tag6\\ &=\color{#C00}{-\frac12\binom{2m-1}{m}}\color{#090}{-\frac14\binom{2m}{m+1}}\color{#00F}{+\frac14\binom{2m+1}{m}}\vphantom{\sum_{i=1}^{m+1}}\color{#00F}{+\frac14\sum_{i=1}^{m+1}\binom{2m+1}{m+i}}\tag7\\ &=\color{#C00}{-\frac14\binom{2m}{m}}\color{#090}{-\frac14\binom{2m}{m-1}}\color{#00F}{+\frac14\binom{2m+1}{m}}\vphantom{\sum_{i=1}^{m+1}}\color{#00F}{+\frac18\sum_{i=0}^{2m+1}\binom{2m+1}{i}}\tag8\\[9pt] &=2^{2m-2}\tag{9} \end{align} Explanation:
$(5)$: apply $(1)$
$(6)$: apply $(2)$ and $(3)$
$(7)$: apply Vandermonde's Identity
$(8)$: $\overbrace{\binom{2m-1}{m-1}+\binom{2m-1}{m}}^{\text{equal by symmetry}}=\binom{2m}{m}$ and symmetry yields $\sum\limits_{i=1}^{m+1}\binom{2m+1}{m+i}=\frac12\sum\limits_{i=0}^{2m+1}\binom{2m+1}{i}$
$(9)$: $\binom{2m}{m}+\binom{2m}{m-1}=\binom{2m+1}{m}$ and $\sum\limits_{i=0}^{2m+1}\binom{2m+1}{i}=2^{2m+1}$

We seek to evaluate

$$\sum_{q=0}^{m+1} (-1)^q \Big{\lfloor} \frac{q}{2} \Big{\rfloor} {2m+1\choose m+q} = \sum_{q=0}^{m+1} (-1)^q \Big{\lfloor} \frac{q}{2} \Big{\rfloor} {2m+1\choose m+1-q}.$$

Observe that

$$\Big{\lfloor} \frac{q}{2} \Big{\rfloor} = [z^q] \left(\sum_{p\ge 0} p z^{2p} + \sum_{p\ge 0} p z^{2p+1}\right) = [z^q] (1+z) \frac{z^2}{(1-z^2)^2} \\ = [z^q] \frac{z^2}{(1-z)^2 (1+z)}.$$

We thus have for the sum

$$\sum_{q=0}^{m+1} (-1)^q [z^q] \frac{z^2}{(1-z)^2 (1+z)} [w^{m+1-q}] (1+w)^{2m+1} \\ = [w^{m+1}] (1+w)^{2m+1} \sum_{q=0}^{m+1} w^q (-1)^q [z^q] \frac{z^2}{(1-z)^2 (1+z)}.$$

Now when $q\gt m+1$ the sum term does not contribute to the coefficient extractor $[w^{m+1}]$ and hence we may extend $q$ to infinity, getting

$$[w^{m+1}] (1+w)^{2m+1} \sum_{q\ge 0} w^q (-1)^q [z^q] \frac{z^2}{(1-z)^2 (1+z)}.$$

Here we may apply the substitution rule or alternatively, an annihilated coefficient extractor (ACE) to obtain

$$[w^{m+1}] (1+w)^{2m+1} \frac{w^2}{(1+w)^2 (1-w)} = [w^{m-1}]\frac{1}{1-w} (1+w)^{2m-1}.$$

This is

$$\sum_{q=0}^{m-1} {2m-1\choose q} = \frac{1}{2} 2^{2m-1} = 2^{2m-2}$$

as claimed.

• Very nice. (+1) – Markus Scheuer Feb 6 '18 at 6:06
• Thank you for the kind remark. – Marko Riedel Feb 6 '18 at 13:47
• @MarkusScheuer There is a user at this MSE link who is asking for documentation concerning how generating functions work, maybe you could help here. – Marko Riedel Feb 21 '18 at 0:10
• I've added an answer which might be helpful. Thanks for the hint and best regards, – Markus Scheuer Feb 24 '18 at 20:10