Asymptotics of sum involving square roots

Question

For an integer $n\geq 1$, consider the following sum: $$S_n=\sum_{k=1}^{n-1}\sqrt{\frac{n^n}{k^k(n-k)^{n-k}}}.$$ I was originally trying to find a closed formula for $S_n$, but didn't manage to. Since I require $S_n$ to bound another value for large $n$, I would be equally happy to describe $S_n$ asymptotically.

Long story short, I computed some values of $S_n$ for large $n$, and ended up with the following table:

$n$	$\approx\frac{\log_2(S_n)}{n}$
$100$	$0.5414$
$1000$	$0.5058$
$2000$	$0.5032$
$3000$	$0.5022$
$4000$	$0.5017$

This leads me to believe that $$\lim_{n\to\infty}\frac{\log_2(S_n)}{n}=\frac 12,$$ or equivalently, that $S_n=\sqrt{2}^{n+o(n)}$. Do you believe that this conjecture holds true? If so, any suggestion on how to prove it?

Answer 1

Too long for a comment

We can use the Euler-Maclaurin summation formula to get the asymptotics. $$n^{-\frac n2}S_n=\sum_{k=1}^{n-1}\sqrt{\frac1{k^k(n-k)^{n-k}}}\sim \int_1^{n-1}\frac{dx}{x^\frac x2(n-x)^\frac{n-x}2}+(n-1)^{-\frac{n-1}2}+\text{higher derivatives}$$ As we take higher derivatives at the bounds, all these terms are exponentially small compared to the integral. The asymptotics of the integral, in turn, can be found by means of Laplace' method.

Making the substitution $x=\frac n2(1+t)$ $$I(n)=\int_1^{n-1}\frac{dx}{x^\frac x2(n-x)^\frac{n-x}2}=\frac n2\left(\frac2n\right)^\frac n2\int_{-1+\frac 2n}^{1-\frac 2n}e^{-\frac n4\big((1+t)\ln(1+t)+(1-t)\ln(1-t)\big)}dt$$ The function $f(t)=(1+t)\ln(1+t)+(1-t)\ln(1-t)$ has one minimum at $t=0;\,f(0)=0;\,f^{''}(0)=2$

Therefore, $$I(n)\sim \frac n2\left(\frac2n\right)^\frac n2\int_{-\infty}^\infty e^{-\frac n4t^2}dt=\sqrt{\pi n}\,2^\frac n2n^{-\frac n2}$$ In the same way we can evaluate next asymptotic terms; for example, $$S_n= \sqrt{\pi n}\,2^\frac n2\left(1-\frac1{2n}+O\Big(\frac1{n^2}\Big)\right)$$ etc.

Answer 2

Greg Martin's approach in the comments works; the term under the square roots is just $2^{n H_2 \left( \frac{k}{n} \right)}$ where $H_2$ is the binary entropy. The binary entropy attains its maximum value when $k = \frac{n}{2}$ (when $n$ is odd we need to use either the floor or the ceiling) and in any case is at most $1$, so $S_n$ can be bounded in terms of the largest term of the sum as

$$S_n \le n\, 2^{\frac{n}{2}}$$

which, together with the lower bound $S_n \ge 2^{\lfloor \frac{n}{2} \rfloor}$, gives the desired result.

The general idea here is that a sum $S_n$ of $n$ non-negative terms is bounded on both sides by its largest term $L_n$, namely we have $L_n \le S_n \le n L_n$. If $L_n$ grows fast enough this pins down the growth rate of $S_n$ up to a factor of $n$, so pins down the growth rate of $\log S_n$ up to an additive error of $\log n$.

Without explicitly discussing the binary entropy, the needed upper bound follows in an elementary way from the AM-GM inequality applied to the numbers $\frac{n}{k}$ repeated $k$ times and $\frac{n}{n-k}$ repeated $n-k$ times, which gives

$$\frac{n^n}{k^k (n-k)^{n-k}} \le \left( \frac{\frac{n}{k} k + \frac{n}{n-k}(n-k)}{n} \right)^n = 2^n.$$