# Even and Odd proof

I'm trying to prove for every positive even number, $$x = 2y$$ that

$$\sum_{i=0}^y {x \choose 2i} 2^{2i} = \sum_{i=0}^{y-1} {x \choose 2i + 1}2^{2i+1} + 1$$

Also to find and prove a similar equation for odd positive numbers $$x = 2y+1$$

-
Please spell out positive-it is only four extra keystrokes and more common ones at that. Also, int as opposed to integer looks like a C data format to me. – Ross Millikan Sep 18 '12 at 23:33
sorry i'll fix that – Thatdude1 Sep 18 '12 at 23:37

Let me rewrite the equation slightly:

$$\sum_{i=0}^y {2y \choose 2i} 2^{2i} = \sum_{i=0}^{y-1} {2y \choose 2i + 1}2^{2i+1} + 1\;.$$

Suppose that we bring the summations together on one side:

$$1=\sum_{i=0}^y {2y \choose 2i} 2^{2i}-\sum_{i=0}^{y-1} {2y \choose 2i + 1}2^{2i+1}\;.$$

As $i$ runs from $0$ to $y$ in the first sum, $2i$ hits every even number from $0$ through $2y=x$. As $i$ runs from $0$ to $y-1$ in the second sum, $2i+1$ hits every odd number from $1$ through $2y-1=x-1$. We can combine the sums into a single sum in which the lower number in the binomial coefficient and the exponent on the $2$ run from $0$ through $x$; we just have to make the signs alternate, negative when the exponent is odd, and positive when it’s even. That’s easy: that’s exactly what $(-1)^i$ does. Thus, what you want to prove is that

$$1=\sum_{i=0}^x(-1)^i\binom{x}i2^i=\sum_{i=0}^x\binom{x}i(-2)^i\;.$$

HINT: Binomial theorem.

Once you see how this one works, figuring out what the corresponding result is for odd $x$ should be pretty straightforward.

Added: By the way, it can also be proved by induction if you don’t mind a bit of computation. Assume as induction hypothesis that

$$\sum_{i=0}^{y-1}\binom{2y-2}{2i}2^{2i}=\sum_{i=0}^{y-2}\binom{2y-2}{2i+1}2^{2i+1}+1\;.$$

Then

\begin{align*} \sum_{i=0}^y\binom{2y}{2i}2^{2i}&=\sum_{i=0}^y\left(\binom{2y-1}{2i}+\binom{2y-1}{2i-1}\right)2^{2i}\\ &=\sum_{i=0}^y\left(\binom{2y-2}{2i}+2\binom{2y-2}{2i-1}+\binom{2y-2}{2i-2}\right)2^{2i}\\ &=\sum_{i=0}^y\binom{2y-2}{2i}2^{2i}+2\sum_{i=0}^y\binom{2y-2}{2i-1}2^{2i}+\sum_{i=0}^y\binom{2y-2}{2i-2}2^{2i}\\ &=\sum_{i=0}^{y-1}\binom{2y-2}{2i}2^{2i}+4\sum_{i=1}^{y-1}\binom{2y-2}{2i-1}2^{2i-1}+\sum_{i=1}^y\binom{2y-2}{2i-2}2^{2i}\\ &=\sum_{i=0}^{y-1}\binom{2y-2}{2i}2^{2i}+4\sum_{i=0}^{y-2}\binom{2y-2}{2i+1}2^{2i+1}+4\sum_{i=0}^{y-1}\binom{2y-2}{2i}2^{2i}\;, \end{align*}

and

\begin{align*} \sum_{i=0}^{y-1}\binom{2y}{2i+1}2^{2i+1}&=\sum_{i=0}^{y-1}\left(\binom{2y-1}{2i+1}+\binom{2y-1}{2i}\right)2^{2i+1}\\ &=\sum_{i=0}^{y-1}\left(\binom{2y-2}{2i+1}+2\binom{2y-2}{2i}+\binom{2y-2}{2i-1}\right)2^{2i+1}\\ &=\sum_{i=0}^{y-1}\binom{2y-2}{2i+1}2^{2i+1}+2\sum_{i=0}^{y-1}\binom{2y-2}{2i}2^{2i+1}+\sum_{i=0}^{y-1}\binom{2y-2}{2i-1}2^{2i+1}\\ &=\sum_{i=0}^{y-2}\binom{2y-2}{2i+1}2^{2i+1}+2\sum_{i=0}^{y-1}\binom{2y-2}{2i}2^{2i+1}+\sum_{i=1}^{y-1}\binom{2y-2}{2i-1}2^{2i+1}\\ &=\sum_{i=0}^{y-2}\binom{2y-2}{2i+1}2^{2i+1}+4\sum_{i=0}^{y-1}\binom{2y-2}{2i}2^{2i}+\sum_{i=1}^{y-1}\binom{2y-2}{2i-1}2^{2i+1}\\ &=\sum_{i=0}^{y-2}\binom{2y-2}{2i+1}2^{2i+1}+4\sum_{i=0}^{y-1}\binom{2y-2}{2i}2^{2i}+4\sum_{i=0}^{y-2}\binom{2y-2}{2i+1}2^{2i+1}\;, \end{align*}

so

$$\sum_{i=0}^y\binom{2y}{2i}2^{2i}-\sum_{i=0}^{y-1}\binom{2y}{2i+1}2^{2i+1}=\sum_{i=0}^{y-1}\binom{2y-2}{2i}2^{2i}-\sum_{i=0}^{y-2}\binom{2y-2}{2i+1}2^{2i+1}=1$$

by the induction hypothesis, and hence

$$\sum_{i=0}^y\binom{2y}{2i}2^{2i}=\sum_{i=0}^{y-1}\binom{2y}{2i+1}2^{2i+1}+1\;,$$

completing the induction.

-
For the odd case, won't i end up having (-1)^(2y+1) but that will always be negative so 1 doesnt equal -1 ? – Thatdude1 Sep 20 '12 at 16:30
@Beginnernato: The only difference will be that instead of $\sum_{i=0}^y\binom{x}{2i}2^{2i}=\sum_{i=0}^{y-1}\binom{x}{2i+1}2^{2i+1}+1$, you’ll have $\sum_{i=0}^y\binom{x}{2i}2^{2i}=\sum_{i=0}^{y-1}\binom{x}{2i+1}2^{2i+1}-1$. – Brian M. Scott Sep 21 '12 at 11:05

Your identity, for $x=2y$ is equivalent to $$\sum_{i=0}^y\binom{x}{2i}2^{2i} - \sum_{i=0}^{y-1}\binom{x}{2i+1}2^{2i+1} = 1$$ If you look at a few examples you'll see that the left hand side is $$\sum_{i=0}^y\binom{x}{2i}2^{2i} - \sum_{i=0}^{y-1}\binom{x}{2i+1}2^{2i+1}=\sum_{k=0}^x\binom{x}{k}(-2)^k$$ but by the binomial theorem we have $$\sum_{k=0}^x\binom{x}{k}(-2)^k = (1+(-2))^x = (-1)^x$$ which is equal to 1, since $x$ was assumed to be even. The proof for $x$ odd is almost identical.

-