Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
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

4 Answers 4

up vote 1 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.