# Approximate solution: factorial and exponentials

If z= $$\dbinom{200}{100}/(4^{100})$$, what is the value of z?

The options are:

a. $$z<1/3$$

b. $$1/3

c. $$1/2

d. $$2/3

How should I go about solving these type of problems?

• Option d makes no sense, while none of options a b c are true. Did you make a typo? – Erick Wong May 26 at 3:57
• @ErickWong Ha! yes. Sorry – Souraj Adhikary May 26 at 3:59
• Welcome to Mathematics Stack Exchange! A quick tour will enhance your experience. Here are helpful tips to write a good question and write a good answer. For equations, please use MathJax. – dantopa May 28 at 22:05

Stirling's approximation gives $$\binom{200}{100} \approx \frac{2^{200}}{10\sqrt{\pi}},$$ so $$\frac{1}{4^{100}} \binom{200}{100} \approx \frac{1}{10 \sqrt{\pi}}\approx 0.0564$$ which is quite small, so a) seems appropriate.

Indeed, $$\frac{1}{4^{100}} \binom{200}{100} \approx 0.0563$$, so Stirling's approximation is not bad here.

• @SourajAdhikary If you accept Stirling's approximation, then you do not need a calculator: $\frac{1}{10 \sqrt{\pi}} < \frac{1}{10} \ll \frac{1}{3}$. – angryavian May 26 at 4:15
• you are right........... – Souraj Adhikary May 26 at 4:17

Consider the normal distribution $$N$$ with mean $$100$$ and variance $$50$$, which approximates the binomial distribution $$B$$ on $$200$$ trials with probability $$0.5$$. $$P(B=100)=\binom{200}{100}\frac1{4^{100}}=z$$ $$\approx P(N\in[99.5,100.5])=P\left(|Z|\le\frac{0.5}{\sqrt{50}}\right)\approx \frac1{\sqrt{50}}f_Z(0)\approx\frac{0.4}7=0.05714\dots$$ The actual value is $$0.05634\dots$$, so our approximation is good and (a) is correct.

• I did not realize that this is another way to arrive at the $\frac{1}{2^{2n}}\binom{2n}{n} \approx \frac{1}{\sqrt{n\pi}}$ approximation, nice. +1. – angryavian May 26 at 4:20
• This is surprisingly nice. :-D +1 – trancelocation May 26 at 4:45
• Local limit theorem or berry Essen would be the rigorous justification of the squiggly equals signs. – Shalop May 26 at 13:38

Here is an elementary approach without estimating the value of the expression:

$$\begin{eqnarray*} \frac{1}{4^m}\binom{2m}{m} & = & \frac{1}{4^m}\cdot \frac{\prod_{i=1}^m 2i \cdot \prod_{i=1}^m (2i-1) }{(m!)^2} \\ & = & \frac{1}{4^m}\cdot 4^m\frac{\prod_{i=1}^m i \cdot \prod_{i=1}^m \left(i-\frac{1}{2}\right) }{\prod_{i=1}^m i \cdot \prod_{i=1}^m i} \\ & = & \prod_{i=1}^m \left( 1 - \frac{1}{2i} \right) \\ & = & \prod^m_{i=1} \frac{2i-1}{2i} \\ & \stackrel{m=100}{<} & \frac{1}{2}\cdot\frac{3}{4}\cdot \frac{5}{6} \\ & = & \frac{5}{16}\\ & < & \frac{1}{3}\\ \end{eqnarray*}$$

If we simply want to know that $$z < 1/3$$, then this can be verified by very elementary means. Note that $$C(200,99) = \frac{100}{101} C(200,100) > 0.99\cdot C(200,100),$$ so then $$C(200,99) + C(200,100) + C(200,101) > 2.98 \cdot C(200,100).$$

On the other hand, $$4^{100} = 2^{200} = C(200.0) + C(200,1) + \cdots + C(200,200),$$ which is clearly greater than just the three middle terms. So $$C(200,100)/4^{100}$$ is certainly less than $$1/2.98$$, which is awfully close to $$1/3$$ already. We just need to estimate one more term like $$C(200,98)$$ to bring the bound below $$1/3$$, and the estimate need not be very precise at all.

Using the bounds in $$(10)$$ from this answer: $$\frac{4^n}{\sqrt{\pi\left(n+\frac13\right)}}\le\binom{2n}{n}\le\frac{4^n}{\sqrt{\pi\left(n+\frac14\right)}}$$ This gives $$\frac{\binom{200}{100}}{4^{100}}\lt\frac1{\sqrt{100\pi}}\lt\frac1{17}$$