Probability of more than ${3\over 4}N$ heads in $N$ flips of a coin? What is the probability of getting more than $ \frac { 3 N } 4 $ heads in $ N $ flips of coins?
I know we need to use binomial distribution formula for this and sum it from $ N = \frac { 3 N } 4 $ to $ N $.
I can solve this when numbers are given but I'm struggling to solve because a general case is given. Any help appreciated.
 A: Consider each coin toss as the outcome for a random variable $X_k$ which is equally distributed over $\{0,1\}$. Assuming that $X_1,\ldots,X_n$ are independent, we are looking for
$$\mathbb{P}[S_n=X_1+X_2+\ldots+X_n > 3n/4] $$
where the central limit theorem ensures the convergence of $S_n$ to a normal variable with mean $n/2$ and variance $n/4$. For any moderately large $n$ ($n\geq 5$) the previous probability is very well approximated (see the Berry-Esseen theorem for understanding how well) by
$$ \int_{3n/4}^{+\infty}\sqrt{\frac{2}{\pi n}} e^{-\frac{2(x-n/2)^2}n^2}\,dx =\frac{1}{2}\,\operatorname{Erfc}\left(\sqrt{\frac{n}{8}}\right)\approx e^{-n/8}\sqrt{\frac{2}{\pi n}},$$
due to the continued fraction representation for the complementary error function.
In a weak sense (see the first comment) we have
$$ \mathbb{P}[S_n > n/2] \approx \frac{e^{-n/8}}{2\sqrt{\pi}}\sqrt{\frac{8}{n}} = e^{-n/8}\sqrt{\frac{2}{\pi n}}.$$
There is an arithmetic perturbation given by the residue class $n\pmod{4}$, such that the ratio between $\mathbb{P}[S_n > 3n/4]$ and the RHS does not converge as $n\to +\infty$. In any case Hoeffding's inequality ensures
$$\mathbb{P}\left[S_n \geq \frac{3n}{4}\right]\leq e^{-n/8}.$$
A: This isn't an answer, simply a long comment. If you don't care about polynomial terms (and you shouldn't when they are overwhelmed with exponential terms) you can use Stirling's approximation formula to get that for large $n\choose k$ looks likes $\frac{n^n}{k^k(n-k)^{n-k}}=2^{nh_2(k/n)}$ with $h_2(p)=-p\log_2(p)-(1-p)\log_2(1-p)$. There is a formal definition of "looks like" which I won't go over, this is only for intuition and not a proof. Observe that on $[1/2,1]$, $h_2$ is decreasing and so for $3/4n\leq k\leq n$, $h_2(k/n)\leq h_2(3/4)$. Writing the sum you get
\begin{align*}
S&=\sum_{k=3/4n}^n{n\choose k}\frac{1}{2^n}\\
&\sim\sum_{k=3/4n}^n2^{n(h_2(k/n)-1)}\\
&\leq 2^{n(h_2(3/4)-1)}\cdot \frac{n}{4}\\
&\sim 2^{n(h_2(3/4)-1)}
\end{align*}
Now as $h_{2}(3/4)<1$, we get some exponential decrease.
