Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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


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



$$\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*}$$


$$\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*}$$



by the induction hypothesis, and hence


completing the induction.

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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