2
$\begingroup$

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.

  • 0
    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.2011-06-06

1 Answers 1

2

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.

  • 0
    @Tom: no problem! I didn't really do any of the work, it all came from the comments.2011-06-07