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