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 am attempting to prove a non-trivial upper bound on the following expression.

Let $0 < r \leq 1$, and let $p$ be a positive integer.

My summation is the following:

$$\sum_{k=0}^\left\lfloor \frac{p}{2} \right\rfloor {p \choose 2k}r^{2k} = 1 + {p \choose 2}r^2 + {p \choose 4}r^4 + \ldots$$

Note that when $r = 1$, I think that it is easy to see that this summation is $2^{p-1}$, as we are essentially counting the number of even subsets of a set of size $p$ (right?).

I'm not sure how to bound it as a function of $r$ and $p$, however.

Any help is greatly appreciated.

share|cite|improve this question
Why do you need an upper bound when the sum is given by $\frac{(1+r)^p + (1-r)^p}{2}$? – user17762 Jun 6 '11 at 21:19
@user6312: No problem. Let your answer stay on so that this questions gets an answer – user17762 Jun 6 '11 at 21:41
@user6312: No problem. It doesn't really matter as long as both our answers are the same. – user17762 Jun 6 '11 at 22:03
Thank you for this quick reply. If it's not too much to ask, can you tell why this is true? (I suppose I could probably convince myself by induction?) – Tom Morello Jun 6 '11 at 22:47
You don't even need induction, just the binomial formula. $(1+r)^n=\sum \binom{n}{k}r^k$ and $(1-r)^n=\sum \binom{n}{k}(-r)^k$. If you add them, all the terms where $k$ is even are the same in both sums, and all the terms where $k$ is odd cancel each other out. – Aaron Jun 6 '11 at 23:05

I'll flesh out the details from the comments:

Recall from the binomial theorem that $(1+x)^n = \displaystyle \sum_{k = 0}^{n} {n \choose k}x^k$. Similarly, $(1-x)^n = \displaystyle \sum_{k = 0}^{n} {n \choose k}(-x)^k$. If we add these two together, we get:

$$\begin{align} (1+x)^n + (1-x)^n &= [1 + x {n \choose 1} + x^2 {n \choose 2} + x^3 {n \choose 3} + x^4 {n \choose 4} + ...] + \\ &\; + \, [1 - x {n \choose 1} + x^2 {n \choose 2} - x^3 { n \choose 3 } + x^4 { n \choose 4} + ...] \end{align}$$

So we see that all the odd-powered terms cancel, while the even-powered terms reinforce. So the exact sum is $\dfrac{(1+x)^n + (1-x)^n}{2}$.

But there is one distinction between this solution and the problem you asked: since your question only goes up to $\lfloor \frac{p}{2} \rfloor$, if $p$ is odd then we see that the last term of the expansion is left out. But this is minor - and is easily remedied.

share|cite|improve this answer
Thanks a lot for this explanation! I guess it is quite simple, now that I see the answer. – Tom Morello Jun 7 '11 at 2:25
@Tom: no problem! I didn't really do any of the work, it all came from the comments. – mixedmath Jun 7 '11 at 2:27

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.