# Prove sum is bounded

I have the following sum:

$$\sum\limits_{i=1}^n \binom{i}{i/2}p^\frac{i}{2}(1-p)^\frac{i}{2}$$

where $p<\frac{1}{2}$

I need to prove that this sum is bounded. i.e. it doesn't go to infinity as n goes to infinity.

-
Does $i$ run over the even numbers? –  espen180 Nov 14 '12 at 21:38
Yes.It does. sorry. –  user844541 Nov 14 '12 at 21:51

This is actually about the convergence of $$\tag1 \sum_{k=1}^\infty {2k\choose k}r^k$$ where $r=p(1-p) \in[0,\frac14[$. Note that ${2k\choose k}\le4^k$ because it appears as a summand in $$4^k=(1+1)^{2k}=\sum_{i=0}^{2k}{2k\choose i}.$$ Therefore ${2k\choose k}r^k\le q^k$ with $q:=4r\in[0,1[$ and (1) converges by comparison test against the geometric series $\sum_{k=1}^\infty q^k=\frac1{1-q}$.

-
How can I prove that $p(1-p)<\frac{1}{4}$? –  user844541 Nov 14 '12 at 22:15
$p(1-p)=\frac14-(\frac12-p)^2$ –  Hagen von Eitzen Nov 14 '12 at 22:17
Nice! thank you! –  user844541 Nov 14 '12 at 22:31

You can use the bound ${i \choose i/2} \lt \frac {2^n}{\sqrt {\pi \frac i2}}$ found in Wikipedia (where your $i$ is $2n$) and I have ignored a multiplier less than $1$. Then show that $p^{\frac 12}(1-p)^{\frac 12} \lt \frac 12$ for $p \ne \frac 12$. Then you get a geometric series that converges.

-

And instead of an explicit bound, you may use Stirling's formula, which yields

$\displaystyle {n \choose n/2} \sim \sqrt{2 / \pi} \cdot n^{-1/2} 2^n$ as $n \to \infty$.

-

Since, by Stirling's approximation, $n! \approx c n^{n+1/2}e^{-n}$ (where $c = \sqrt{\pi}$) and $\binom{i}{i/2} = \frac{i!}{(i/2)!^2}$, $\binom{i}{i/2} \approx \frac{ci^{i+1/2}e^{-i}}{(c(i/2)^{i/2+1/2}e^{-i/2})^2} = \frac{i^{i+1/2}e^{-i}}{c(i/2)^{i+1}e^{-i}} =2^{i+1}/(c\sqrt{i})$.

Since $0 < p < 1/2$, $p(1-p) = p-p^2 = 1/4 - 1/4+p-p^2 = 1/4-(1/2-p)^2$, so $p^{i/2}(1-p)^{i/2} = (p(1-p))^{i/2} = (1/4-d)^{i/2}$ where $d = (1/2-p)^2$.

So $\binom{i}{i/2}p^{i/2}(1-p)^{i/2} \approx 2^{i+1}/(c\sqrt{i})(1/4-d)^{i/2} = \frac{2}{c\sqrt{i}}(1-4d)^{i/2}$, and since $d < 1/4$, letting $r = \sqrt{1-4d}$, $\binom{i}{i/2}p^{i/2}(1-p)^{i/2} \approx \frac{2}{c\sqrt{i}}r^i$ where $r < 1$, and the sum of these is less than a geometric series with ratio less than $1$ and so converges.

-