Big-O of the log of sum of binomial coefficient Let $n\in \mathbb{N}$, $k\in \mathbb{N}$, $k<n$, I want to prove $\log{\left(\sum_{i=0}^k \binom{n}{i}\right)} = O\left(k\log(\frac{n}{k})\right)$.
I tried to use the approximation for the logarithm of a binomial coefficient, but I was not able to get $k\log(\frac{n}{k})$...
 A: Using
$$\binom{n}{i}<\frac {n^i}{i!}$$
$$\log{\left(\sum_{i=0}^k \binom{n}{i}\right)} <\log \left(e^n\frac{ \Gamma (k+1,n)}{\Gamma (k+1)}-1\right)<\log \left(e^n\frac{ \Gamma (k+1,n)}{\Gamma (k+1)}\right)$$ If $n$ is large
$$e^n\frac{ \Gamma (k+1,n)}{\Gamma (k+1)}=n^k \left(\frac{1}{\Gamma (k+1)}+O\left(\frac{1}{n}\right)\right)$$
$$log \left(e^n\frac{ \Gamma (k+1,n)}{\Gamma (k+1)}\right)\sim k\log(n)-\log(\Gamma (k+1))$$ what you can rewrite as
$$k \log \left(\frac{n}{k}\right)+\log \left(\frac{k^k}{k!}\right)$$
and
$$\log \left(\frac{k^k}{k!}\right)\sim k-\frac 12\log(2k\pi)$$
and
A: A probabilistic approach would give the following. Let $Z\sim Binomial(n,1/2)$ random variable, then $P(Z=i)={n\choose i} 2^{-n}$, $i=0,1,...,n$. Hence $P(Z\le k)=2^{-n}\sum_{i=0}^k {n\choose i} $. Therefore,
$$
(*)=\log\left(\sum_{i=0}^k {n\choose i}\right)=n\log(2)+\log P(Z\le k).
$$
Assuming $n\to\infty$, we can apply Central Limit Theorem to $Z$, which is a sum of i.i.d. Bernoulli(1/2) random variables, so $Z\asymp {\cal N}(n/2,n) $ so
$$
(*)= n\log 2+\log P\left(\frac{Z-n/2}{\sqrt{n}}\le \frac{k-n/2}{\sqrt{n}}\right)
\approx  n\log 2+\log \Phi\left( \frac{k-n/2}{\sqrt{n}}\right)
$$
where $\Phi(a)=\int_{-\infty}^a \frac{e^{-x^2/2}}{\sqrt{2\pi}}dx$ is the CDF of the standard normal random variable.
Since for $a\ll 0$ we have $\Phi(a)\approx \frac{e^{-a^2/2}}{a\sqrt{2\pi}}$, if $k=cn$ where $c<1/2$, we get
$$
(*)\approx n\log 2 -\frac{(1/2-c)^2}2 n+o(n)=\left[\ln 2-\frac{(c-0.5)^2}2\right] n+o(n)
$$
Conversly, if $k=cn$ where $c>1/2$, then sin, we getce $\Phi(x)\to 1$ as $x\to+\infty$ we get
$$
(*)\approx n\log 2.
$$
