# Binomial Coefficient Identity, Double Series, Floor Function

I came across this (supposed) identity for natural numbers $m$ and $n$: $$\sum_{i=0}^{n}{ \sum_{j=0}^{m}{ \left(-1 \right)^{\lfloor \frac{i}{2} \rfloor+j}2^{n-i}\binom{n-i+\lfloor \frac{i}{2} \rfloor}{j}\binom{n-i+\lfloor \frac{i}{2} \rfloor-j}{\lfloor \frac{i}{2} \rfloor}\binom{i}{m-j}}}= \left(-1 \right)^{m} \binom{2n+1}{2m+1}$$ and would like to prove it.

Cross posting from MSE after getting no replies.

I am trying to keep a certain tone to my work so I am looking for a human, non-analytic, combinatorial or algebraic proof to the above. To be more specific, I'd like to avoid using generating functions, calculus, complex numbers, trigonometric functions, chabyshev polynomials and induction; every other technique would do.

Update #1: tested to be true for $n,m \leq100$

Update #2: I would like to give the reason as to why I would like to avoid using the above techniques. I am trying to generlize this identity (12): $$\left(\sin \left(nx \right) \right)^{2}= \left(\sin \left(x \right) \right)^{2} \left(\sum_{m=0}^{\frac{n-1}{2}}{\left(-1 \right)^{m} \binom{n}{2m+1}} \left( \cos^{2}x\right)^{\frac{n-1}{2}-m} \left( \sin^{2}x\right)^{m}\right)^{2}$$ for an odd natural number $n$ and a number $x$ to a general field, using the framework of Rational Trigonometry and its Spread Polynomials. I want to show that the latter identity is essentially a polynomial or an "arithmetical" identity, meaning that it is independent of the framework of the classical trigonometric functions and the framework of complex numbers, and that the problem of proving said identity is essentially a (rather complicated) problem of arithmetic or of counting. In this endeavor, I would like to keep a "theme" of not invoking techniques which regard the classical trigonometric functions, complex numbers or calculus. The binomial coefficient identity I wanted to prove came up in the process of this work.

• "I'd like to avoid using generating functions, calculus, complex numbers, trigonometric functions, chabyshev polynomials and induction" -- what is left then? Abacus? – Max Alekseyev Apr 11 '17 at 15:19
• "...Abacus?" -- I wish! Please see the update to the OP which I'll post shortly. But seriously, I would like to use any binomial identities that can be proven with "counting arguments", recurrence, inclusion-exclusion, bijective arguments, coefficient extraction, Riordan arrays etc... – Hellbound Apr 11 '17 at 17:47
• What's wrong with induction (and how is it different from recurrence)? That would be my first choice when faced with a trigonometric identity involving multiples of angles. – darij grinberg Apr 11 '17 at 19:36
• What is your rational formula for $\left(\sin\left(x+y\right)\right)^2$ ? Are tangents and cotangents (not squared) rational in your theory? – darij grinberg Apr 11 '17 at 19:39
• @darijgrinberg I guess that choosing recurrence over induction is a more "artistic" position. I found that avoiding using induction leads to more insight into the subject, which is important to me because Rational Trigonometry and its Spread Polynomials are new theories. The book Divine Proportions by Norman Wildberger is distibuted for free at researchgate.net: Rational Trigonometry – Hellbound Apr 11 '17 at 21:12

Notice that $$\binom{n-i+\lfloor \frac{i}{2} \rfloor}{j}\binom{n-i+\lfloor \frac{i}{2} \rfloor-j}{\lfloor \frac{i}{2} \rfloor} = \binom{n-i}{j}\binom{n-i+\lfloor \frac{i}{2} \rfloor}{\lfloor \frac{i}{2} \rfloor}.$$ This lets us easily sum up the terms depending on $j$: $$\sum_{j=0}^m (-1)^j \binom{n-i}{j} \binom{i}{m-j} = [x^m]\ (1-x)^{n-i}(1+x)^i = [x^{2m}]\ (1-x^2)^{n-i}(1+x^2)^i.$$ (We will see later why dealing with squares of $x$ is preferable.)

So, it remains to evaluate the following sum: $$\sum_{i=0}^n (-1)^{\lfloor \frac{i}{2} \rfloor} (2-2x^2)^{n-i} (1+x^2)^i \binom{n-i+\lfloor \frac{i}{2} \rfloor}{\lfloor \frac{i}{2} \rfloor}.$$ Let $i=2s+t$ where $s=\lfloor \frac{i}{2} \rfloor$ and $t=i\bmod 2$. Then the sum becomes $$\sum_{s\geq 0} \sum_{t=0}^1 (-1)^{s} (2-2x^2)^{n-2s-t} (1+x^2)^{2s+t} \binom{n-s-t}{s}$$ $$=\sum_{t=0}^1 \frac{(1+x^2)^{2n-t}}{(2-2x^2)^{n-t}} (-1)^{n-t} \sum_{s\geq 0} \binom{n-s-t}{s} \left(-\frac{4(1-x^2)^2}{(1+x^2)^2}\right)^{n-s-t}$$ $$(\star)\quad = \sum_{t=0}^1 \frac{(1+x^2)^{2n-t}}{(2-2x^2)^{n-t}} (-1)^{n-t} \frac{(1+x^2)^2}{4(x-x^3)}\Im\left( \frac{2(1-x^2)}{(I-x)^2}\right)^{n-t+1}$$ $$=\Im \sum_{t=0}^1 \frac{(1+x^2)^{2n-t+2}}{2x} (-1)^{n-t} (I-x)^{-2(n-t+1)}$$ $$=-\Im \sum_{t=0}^1 \frac{(1-Ix)^{2n-t+2}(1+Ix)^t}{2x}$$ $$=-\Im \frac{(1-Ix)^{2n+1}}{x},$$ where $I$ is the imaginary unit ($I^2 = -1$) and $\Im X$ denotes the imaginary part of $X$.

Now we are ready to take the coefficient of $x^{2m}$: $$[x^{2m}]\ -\Im \frac{(1-Ix)^{2n+1}}{x} = -\Im \binom{2n+1}{2m+1} (-I)^{2m+1} = (-1)^m\binom{2n+1}{2m+1}$$ as expected.

UPDATE. To clarify step $(\star)$: $$\sum_{p\geq 0} \binom{p}{r-p} u^p = \sum_{p\geq 0} [z^{r-p}]\ (1+z)^p u^p = [z^r]\ \sum_{p\geq 0} (z(1+z)u)^p$$ $$= [z^r]\ \frac{1}{1-z(1+z)u} =[z^r]\ \frac{1}{(z_1-z_2)z}\left(\frac{1}{1-z_1z}-\frac{1}{1-z_2z}\right) = \frac{z_1^{r+1}-z_2^{r+1}}{z_1-z_2},$$ where $z_{1,2} = \frac{u\pm\sqrt{u^2+4u}}{2}$ are the reciprocals of the zeros of $f(z)=1-z(1+z)u$, so that $f(z)=(1-z_1z)(1-z_2z)$. When $u^2+4u=-v^2$ like in the case $(\star)$, we further have $$\frac{z_1^{r+1}-z_2^{r+1}}{z_1-z_2} = \frac{2}{v}\Im \left(\frac{u+Iv}{2}\right)^{r+1}.$$

• $\mathfrak{I} = ?$ – darij grinberg Apr 11 '17 at 15:20
• @darijgrinberg: I thought it's standard -- en.wikipedia.org/wiki/Complex_number Anyway, I've just added explanation to the text. – Max Alekseyev Apr 11 '17 at 15:21
• Ah! I was used to $\operatorname{Im}$ for imaginary part, but I don't like it that much (as the same notation is being used for images). I have never seen $\mathfrak{I}$. – darij grinberg Apr 11 '17 at 15:34
• I apologize for the delayed response as I wanted to make sure I understood every step. Your answer is very nice, and was made very clear with the update. Thank you. Unfortunately I was looking to avoid using complex numbers, and I'll explain why in an update to the OP and in a response to your comment above. – Hellbound Apr 11 '17 at 17:38
• @Hellbound: Here you may think about complex numbers as $\mathbb{Q}[x]/\langle x^2+1\rangle$, i.e., polynomials over the field of rational numbers modulo the polynomial $x^2+1$. Is that better? – Max Alekseyev Apr 29 '17 at 16:33