What is the asymptotic order of ${2n \choose 0}\sqrt{n}+ {2n \choose 1}\sqrt{n-1} +...+{2n \choose n}\sqrt{0}$?

Question

Binomial expansion gives ${2n \choose 0}\cdot2+ {2n \choose 1}\cdot 2 +...+{2n \choose n-1}\cdot2+{2n \choose n}=2^{2n}$. My question is to find the asymptotic order of $$F(n):={2n \choose 0}\sqrt{n}+ {2n \choose 1}\sqrt{n-1} +...+{2n \choose n}\sqrt{0}$$ as $n\rightarrow \infty$. In particular, is it true that for all $n$, $F(n)\le C\cdot 2^{2n}$ for some constant $C$?

Answer 1

In particular, is it true that for all $n$, $F(n)\le C\cdot 2^{2n}$ for some constant $C$?

No.

Let's parameterise the sum slightly non-intuitively (it's in the reverse order to the way you've written it): $$\sum_{i=0}^n \binom{2n}{n-i} \sqrt i$$

Then by Stirling's approximation the $i$th term is approximately $$\frac{1}{\sqrt {2\pi}} \frac{(2n)^{2n+1/2}}{(n-i)^{n-i+1/2}(n+i)^{n+i+1/2}} \sqrt i$$ and when $i = o(n)$ that in turn approximates to $$\frac{2^{2n}}{\sqrt\pi} \sqrt\frac{i}{n}$$

Since there are $\sqrt{n}$ values of $i$ in the range $[\frac12\sqrt n, \frac32\sqrt n)$ you should not expect an upper bound which is asymptotically better than $$2^{2n} n^{1/4}$$

This may not be tight, but it's enough to answer the direct question.

Answer 2

Here is a first-term asymptotic analysis that gets the same result as Peter Taylor above, but with an explicit constant. Numerically, about 3 digits agreement are obtained for n ~ 1000.

$$\sum_{k=0}^n \binom{2n}{n-k}\sqrt{k} \sim \binom{2n}{n}\sum_{k=0}^n\exp{(-k^2/n)}\sqrt{k}=\binom{2n}{n}n^{3/2}\,\frac{1}{n}\sum_{k=0}^n\exp{(-n\big(\frac{k}{n}\big)^2)}\sqrt{\frac{k}{n}}.$$

In the 1st step the well-known expansion for the central binomial coefficients have been used and the 2nd I'm setting up for the interpretation of the sum as a Riemann integral as n $\to \infty$, i.e.,

$$\sum_{k=0}^n \binom{2n}{n-k}\sqrt{k} \sim \binom{2n}{n}n^{3/2}\, \int_0^1\exp{(-n\,x^2)}\sqrt{x}\,dx .$$ The standard asymptotic trick of increasing the upper integral limit go to $\infty$ allows us to explicitly calculate the integral with the gamma function. Using the Stirling approximation for the binomial and collecting results the answer so obtained is

$$ \sum_{k=0}^n \binom{2n}{n-k}\sqrt{k} \sim \frac{\Gamma(3/4)}{2\sqrt{\pi}} n^{1/4}2^{2n}$$

Answer 3

Too long for a comment.

Having fun playing with small numbers, I computed the values of

$$S_n=\sum_{i=0}^n \binom{2n}{n-i} \sqrt i$$ for $100 \leq n \leq 10000$ (step size $= 100$). For $n=1000$, the value is almost $1.375\times 10^{6021}$ (!!).

Performing a linear regression $$\log(S_n)=a+ b n + c \log(n)$$ $$\begin{array}{clclclclc} \text{} & \text{Estimate} & \text{Standard Error} & \text{Confidence Interval} \\ a & -1.08076 & 0.00069 & \{-1.08213,-1.07939\} \\ b & +1.38629 & \approx 0 & \{+1.38629,+1.38629\} \\ c & +0.25239 & 0.00010 & \{+0.25219,+0.25259\} \\ \end{array}$$ while using skbmoore's answer, the coefficients would be $ \{-1.06223,1.38629,0.25000\}$.