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.

  • 1
    $\begingroup$ Use backslash ('\') for functions like sum, choose, etc. $\endgroup$ – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.