# Upper bound a binomial-like summation

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.

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

-
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