# Proof for $\frac{1}{n}\ln\left[2\sum_{i=0}^{n-1}\binom{\alpha n-1}{i}\right]\leq \alpha \ln(\alpha)-(\alpha-1)\ln(\alpha-1)$

I want to prove the following:

When $n\rightarrow \infty$ and $\alpha >2$, $$\frac{1}{n}\ln\left[2\sum_{i=0}^{n-1}\binom{\alpha n-1}{i}\right]\leq \alpha \ln(\alpha)-(\alpha-1)\ln(\alpha-1)$$ Hint: Use the Stirling approximation

I tried the following: \begin{align} \frac{1}{n}\ln\left[2\sum_{i=0}^{n-1}\binom{\alpha n-1}{i}\right]=\frac{1}{n}\ln\left[2\sum_{i=0}^{n-1}\frac{(\alpha n-1)!}{i!(\alpha n -1-i)!}\right]\\ \approx \frac{1}{n}\ln\left[2\sum_{i=0}^{n-1}\frac{\sqrt{2\pi(\alpha n -1)}(\alpha n-1)^{(\alpha n -1)}e^{-(\alpha n-1)}}{\sqrt{2 \pi i}\,i^ie^{-i} \sqrt{2\pi(\alpha n -1-i)}(\alpha n -1-i)^{(\alpha n -1-i)}e^{-(\alpha n -1-i)}}\right]\\ =\frac{1}{n}\ln\left[2\frac{(\alpha n-1)^{(\alpha n -1/2)}}{\sqrt{2\pi}}\sum_{i=0}^{n-1}\frac{1}{i^{i+1/2}(\alpha n-1-i)^{(\alpha n -i -1/2)}}\right]\\ =\frac{1}{n}\left[\ln(2)+(\alpha n -1/2)\ln(\alpha n -1)-\ln(\sqrt{2 \pi})+\ln(\sum_{i=0}^{n-1}\frac{1}{i^{i+1/2}(\alpha n-1-i)^{(\alpha n -i -1/2)}})\right] \end{align} Where in the aproximation I used the Stirling Approximation.

But now I am stuck.

Could you please help me with the sequence? This is a question in the context of the Cover's Function Counting Theorem.

• Math SE would be appropriate for this question May 12, 2017 at 17:29
• I think if you expand the sum to better examine the individual terms, the relationship with the infinite series for the Sterling approximation will become clearer. Alternatively, exponentiate both sides of the inequality to similar effect.
– Carl
May 13, 2017 at 6:01

Disclaimer: Below is an alternative direction . It is too long for a comment hence posted as a solution, but admittedly is not a complete solution. Also note it does not use Stirling's approximation (so far). I thought this might help give a sense of what you are dealing with, from a different direction.

First, we observe that the sum of the binomial coefficients is $2^m$ by taking $x=y=1$ in the binomial theorem $2^m = (1+1)^m= \sum_{i=0}^{m}\binom{m}{i}$

Then we see that $\sum_{i=0}^{\alpha n-1}\binom{\alpha n-1}{i} = 2^{\alpha n-1}$

Since $\alpha > 2$, the sum $\sum_{i=0}^{n-1}\binom{\alpha n-1}{i}$ is less than $1/\alpha \sum_{i=0}^{\alpha n-1}\binom{\alpha n-1}{i}$.

This last statement needs a confirmation. But it seems reasonable because when you think about the binomial coefficients (a row in Pascal's triangle), the middle set of numbers are bigger than the left end and the right end. The sum is going about $1/\alpha$ way of that row.

Then $$2 \, \sum_{i=0}^{n-1}\binom{\alpha n-1}{i} \leq \frac{2}{\alpha} \sum_{i=0}^{\alpha n-1}\binom{\alpha n-1}{i} = \frac{2^{\alpha n}}{\alpha}$$ So $$\left[2 \, \sum_{i=0}^{n-1}\binom{\alpha n-1}{i} \right]^{1/n} \leq \frac{2^{\alpha}}{\alpha^{1/n}}$$

Natural log of the left side is what you are dealing with.