Asymptotics of $\sum_{i=1}^n {n \choose i}2^i \frac{i+1}{i^{\frac{n + 1}{2}}}$

Question

I have the following formula which appears numerically to be exactly $4n$ asymptotically.

$$\sum_{i=1}^n {n \choose i}2^i \frac{i+1}{i^{\frac{n + 1}{2}}}$$

What can one do to prove this?

Answer 1

This might not be the most elegant proof, but it serves the purpose quite well (the inequalities used elementary, but quite weak). Let's split the sum into three parts:

• The initial term is equal to $4n$ (not a coincidence!)
• Each of the following $15$ terms is a fraction whose numerator is a polynomial of degree $i$ in $n$ and denominator is an exponential (with base greater than $1$) in $n$. Thus, each of them converges to zero.
• The remaining terms (starting with $i\geq 17$) can be bounded from above using the following inequalities: $$\begin{eqnarray}\binom{n}{i} & < & 2^n \\ 2^i & \leq & 2^n \\ (i+1) & \leq & (n+1) \\ i^{(n+1)/2} & \geq & (\sqrt{17})^n\end{eqnarray}$$ Thus, each term can be bounded by $\frac{4^n(n+1)}{(\sqrt{17})^n}$ and their sum does not exceed $\frac{n(n+1)}{(\sqrt{17}/4)^n}$. Again, we have a polynomial divided by an exponential with base greater than $1$, so this expression converges to zero too.

All in all, apart from the first term, all the remaining ones converge to zero... and they do so pretty quickly.