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.

  • 8
    Why do you need an upper bound when the sum is given by $\frac{(1+r)^p + (1-r)^p}{2}$?2011-06-06
  • 2
    @user6312: No problem. Let your answer stay on so that this questions gets an answer2011-06-06
  • 1
    @user6312: No problem. It doesn't really matter as long as both our answers are the same.2011-06-06
  • 0
    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?)2011-06-06
  • 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