Asymptotic behavior of $\sum_{k=1}^n \binom{n}{k} \left(\frac{ck}{n}\right)^k$

Question

I am looking to show that $$\lim_{n \rightarrow \infty}\frac{1}{e^n}\sum_{k=1}^n \binom{n}{k} \left(\frac{ck}{n}\right)^k = 0. $$ In my application, $c = (e+1)/2 \approx 1.85914\ldots$. I have been looking all over the place, but I can't seem to find a closed form expression or good upper bound for the sum.

The obvious estimation $$\sum_{k=1}^n \binom{n}{k} \left(c\frac{k}{n}\right)^k \leq \sum_{k=0}^n \binom{n}{k} \left(c\right)^k \leq \left(1+c\right)^n $$ won't do the trick, since $1+c=1+(1+e)/2 > e$.

Any ideas?

Answer 1

Simple Approximation with Bernoulli's Inequalty

Using Bernoulli's Inequality, we see that $$ e^{-k}\le\left(1-\frac{k}{n}\right)^{n-k}\le e^{-k(1-k/n)}\tag{1} $$ Thus, $$ \begin{align} \lim_{n\to\infty}\frac1{e^n}\sum_{k=1}^n\binom{n}{k}\left(\frac{ck}{n}\right)^k &=\lim_{n\to\infty}\frac1{e^n}\sum_{k=0}^n\binom{n}{k}\left(\frac{c(n-k)}{n}\right)^{n-k}\\ &=\lim_{n\to\infty}\frac1{e^n}\sum_{k=0}^n\binom{n}{k}c^{n-k}\left(1-\frac{k}{n}\right)^{n-k}\\ &=\lim_{n\to\infty}\sum_{k=0}^n\binom{n}{k}\left(\frac ce\right)^{n-k}\left[\frac1{e^2},\frac1{e^{2-k/n}}\right]^k\tag{2} \end{align} $$ $(2)$ says that the limit is infinity if $c\gt e-\frac1e=2.3504023872876029138$.

The Central Limit Theorem says that as $n\to\infty$, the main contribution to $$ \sum_{k=0}^n\binom{n}{k}x^{n-k}y^k\tag{3} $$ occurs within a $O\left(n^{-\frac12+\epsilon}\right)$ neighborhood of $\frac kn=\frac{y}{x+y}$. If we abbreviate $\frac kn=\alpha$, we get that the limit is $0$ if $c\lt e-\frac1{e^{1-\alpha}}$ where the Central Limit Theorem gives $\frac1\alpha-1=ce^{1-\alpha}$. Solving for $\alpha$, we get $$ \begin{align} \left(\frac1\alpha-1\right)e^{\alpha-1} &=e-e^{\alpha-1}\\ &\Downarrow\\ \alpha &=-\mathrm{W}\left(-e^{-2}\right)\\ &=0.15859433956303936215\tag{4} \end{align} $$ $(4)$ yields that the limit is $0$ if $c\lt2.287177717128371900838$.

Since $\frac{e+1}2\lt2.287177717128371900838$, when $c$ is close to $\frac{e+1}{2}$, the limit is $0$.

This simple argument cannot tell what happens for $$ 2.287177717128371900838\lt c\lt2.3504023872876029138\tag{5} $$

---

More Precision with Laplace's Method

For more precision, Laplace's Method can be adapted to handle the sum $$ e^{-n}\sum_{k=0}^n\binom{n}{k}\left(\frac{ck}{n}\right)^k\tag{6} $$ In Laplace's Method, the integral is $$ \sqrt{\frac{2\pi}{s(x_\text{max})}}f(x_\text{max})\tag{7} $$ where $s(x)=-\frac{\mathrm{d}^2}{\mathrm{d}x^2}\log(f(x))$ and $f'(x_\text{max})=0$.

---

The first difference of $\log\binom{n}{k}$ is $\log\left(\frac{n-k}{k+1}\right)$. The derivative of $k\log\left(\frac{ck}{n}\right)$ is $1+\log\left(\frac{ck}{n}\right)$. Thus, we will approximate the first derivative of the log of the summand by $$ \log\left(\frac{ce(n-k)}{n}\right)=\log(ce(1-\alpha))\tag{8} $$ where $\alpha=\frac kn$. Thus, the maximum of the integrand is when $$ ce(1-\alpha)=1\tag{9} $$ The negative of the second derivative of the log of the summand at the maximum is then $$ \frac1{n-k}=\frac1{n(1-\alpha)}=\frac{ce}{n}\tag{10} $$ Computing the value of the summand at its maximum using Stirling's formula: $$ \begin{align} &\frac1{\sqrt{2\pi n}}\sqrt{\frac{n^2}{k(n-k)}}\frac{n^n}{k^k(n-k)^{n-k}}\frac{c^kk^k}{n^ke^n}\tag{11}\\ &=\frac1{\sqrt{2\pi n\alpha(1-\alpha)}}\left(\frac{c^\alpha}{e(1-\alpha)^{1-\alpha}}\right)^n\tag{12}\\ &=\frac1{\sqrt{2\pi n\alpha(1-\alpha)}}\left(ce^{-\alpha}\right)^n\tag{13}\\ &=\frac{ce}{\sqrt{2\pi n(ce-1)}}\left(\frac cee^{\large\frac1{ce}}\right)^n\tag{14} \end{align} $$ Using $(7)$, $(10)$, and $(14)$, we get the sum in $(6)$ to be asymptotic to $$ \begin{align} \sqrt{\frac{ce}{ce-1}}\left(\frac cee^{\large\frac1{ce}}\right)^n\tag{15} \end{align} $$ Formula $(15)$ indicates that the breakpoint in $c$ between the limit being $0$ and being $\infty$ is when $\frac cee^{\large\frac1{ce}}=1$; that is, $$ \begin{align} c &=-\frac1{e\mathrm{W}\left(-e^{-2}\right)}\\[6pt] &\doteq2.3196252917035202431\tag{16} \end{align} $$ Note that the $c$ given in $(16)$ is almost in the middle of the range given in $(5)$. When $c$ is equal to the value in $(16)$, we get $$ \sqrt{\frac{ce}{ce-1}}=1.0901776779197391224\tag{17} $$ Using Mathematica 8, computing the sum in $(6)$ for the $c$ given in $(16)$ and $n=100000$ yields $1.090178422502261$; very close to $(17)$.

---

For $c=\frac{e+1}{2}$, approximation $(15)$ says that the sum is asymptotic to $$ 1.1165527750632721\times0.8335934600537050^n\tag{18} $$ For $n=500$, $(18)$ gives $3.34987509422\times10^{-40}$, whereas actual computation yields $3.35051202913\times10^{-40}$, an error of less than $0.02\%$.

Answer 2

We know that $\dbinom{n}{k} \le \left(\dfrac{e\,n}{k}\right)^k$. Therefore, $$\sum_{k=1}^n \binom{n}{k} \left(c\frac{k}{n}\right)^k \le \sum_{k=1}^n \left(\dfrac{e\,n}{k}\right)^k \left(c\frac{k}{n}\right)^k = \sum_{k=1}^n (e\,c)^k = \frac{(e\,c)^{n+1}-1}{e\,c-1}$$

Answer 3

To get an idea of the asymptotics, try using Stirling's approximation on the binomial coefficients:

$$\begin{align}\ln \left[{n \choose k} \left(\frac{c k}{n}\right)^k\right] &\sim \left[n \ln n - k \ln k - (n - k) \ln(n - k)\right] + \left[k \ln c + k \ln k - k \ln n\right] \\ &\sim (n-k) \ln\left(\frac{n}{n - k}\right) + k \ln c. \tag{1}\end{align}$$

Now, to see where the main "weight" of the summation is, i.e., for which values of $k$ the summands are the biggest, we just take the derivative with respect to $k$, set it equal to $0$, and solve for $k$:

$$1 + \ln \left(\frac{n-k}{n}\right) + \ln c = 0 \implies k = \left(1 - \frac{1}{ce}\right)n$$

Plugging this value of $k$ into $(1)$, we get that for this value of $k$ the summand becomes

$${n \choose k} \left(\frac{c k}{n}\right)^k \sim \exp\left(\left(\ln c + \frac{1}{e c}\right)n\right).$$

So for large $n$, the whole argument of the limit (including the term $e^n$) scales as

$$\exp\left(\left(\ln c + \frac{1}{e c} - 1\right) n\right).$$

Filling in $c = (e + 1)/2$ we get a negative exponent guaranteeing convergence of the order $e^{-0.182009 n} = 2^{-0.26258\dots n}$. We can verify these results numerically, e.g., for $n = 500$ the exact value is $3.35051\ldots \cdot 10^{-40}$ while the asymptotic approximation gives us $3.00019\ldots \cdot 10^{-40}$. The order of magnitute is exactly right, and only the constant is slightly off by about $10\%$.

---

If you would also like to know for which values of $c$ you get convergence, you just have to find out when the exponent is negative:

$$\ln c + \frac{1}{e c} - 1 < 0 \iff c(1 - \ln c) < \frac{1}{e}.$$

Substituting $c = e \cdot d$ will make the $1$ on the left hand side disappear:

$$d \ln d > \frac{-1}{e^2}.$$

This cannot be solved with elementary functions, but using the Lambert W function we get

$$d < e^{W(-1/e^2)} \implies c < e^{1 + W(-1/e^2)} = 2.31963\ldots.$$

Answer 4

To estimate the sum , we first consider even $n$ and note the following:

• $c = \frac{(1+e)}{2} \approx 1.85914\dots < e$, and therefore, the last term of the sum for $k=n$ can be ignored as $\binom{n}{n}\left(\frac{c}{e}\right)^n \rightarrow 0$ for $n \rightarrow \infty$.
• $\binom{n}{k} = \binom{n}{n-k}$, and therefore, both terms $\binom{n}{k}\left(c \frac{k}{n}\right)^k$ and $\binom{n}{k}\left(c \frac{n-k}{n}\right)^{n-k}$ have the same binomial coefficient in the sum.
• The idea is to estimate the sum of both terms by an exponential function of the form $c \mapsto e^{m k + b}$, where $m$ and $b$ depend only on $n$ and $c$.
• Indeed, the log of the sum, the function $k \mapsto \log\left( \left(c\frac{k}{n}\right)^k + \left(c\frac{n-k}{n}\right)^{n-k} \right)$, is strictly convex and on the interval $\left[1,\frac{n}{2}\right]$ it is upper-bounded by the linear function $$ f(k) = \left(\frac{\log(4)}{n}-\log(2c)\right) k + n \log(c).$$
• Thus, $$\binom{n}{k}\left(c\frac{k}{n}\right)^k + \binom{n}{n-k}\left(c\frac{n-k}{n}\right)^{n-k} \leq \binom{n}{k} e^{f(k)}.$$

We can bound the sum by \begin{eqnarray} \frac{1}{e^n} \sum_{k=1}^{ \frac{n}{2} } \binom{n}{k} e^{f(k)} & = & \frac{1}{e^n} \sum_{k=1}^{\frac{n}{2}} \binom{n}{k} 4^{\frac{k}{n}} c^n \left(\frac{1}{2c}\right)^k \\ & \leq & 4\frac{c^n \left(1+ \frac{1}{2c}\right)^n}{e^n} \\ & = & 4\left(\frac{\frac{1}{2} + c}{e}\right)^n \approx 4\left(\frac{2.35914}{e}\right)^n. \end{eqnarray} Since $2.35914 < e$, we get exponential convergence to $0$.

For odd $n$ the argument is essentially the same, except that we need to also consider the central term (for $k = \frac{n}{2}+1$) separately. \begin{eqnarray} \binom{n}{\frac{n}{2}+1} \left(c \frac{\frac{n}{2}+1}{2}\right)^{\frac{n}{2}+1} & \leq & 2^n \left( \sqrt{c \left(\frac{1}{2} + \frac{1}{n}\right)}\right)^n \cdot c \left(\frac{1}{2} + \frac{1}{n}\right) \\ & = & \left( \sqrt{c \left(2 + \frac{4}{n}\right)}\right)^n \cdot c \left(\frac{1}{2} + \frac{1}{n}\right). \end{eqnarray} With $\sqrt{c \left(2 + \frac{4}{n}\right)} \approx 1.92828 < e$, the result follows for odd $n$ as well.

Note on generality:

So basically, if you want to estimate the asymptotics of $$ \frac{1}{x^n} \sum_{k=1}^n \binom{n}{k} \left(c\frac{k}{n}\right)^k, $$ the limit is guaranteed to be $0$ as long as $c \in [0,x-0.5)$.

Answer 5

I was also working with the inequality

$$ \left(1 - \frac{k}{n}\right)^{n-k} \leq \exp \left( -k + \tfrac{k^{2}}{n} \right) = \exp\left\{ -n \cdot \tfrac{k}{n} \left( 1 - \tfrac{k}{n} \right) \right\}.$$

Now note that $q(x) = x(1-x)$ satisfies $q(1-x) = q(x)$ and $q(x) \geq \frac{1}{2}x $ on $[0, \frac{1}{2}]$. Then we get

$$ 0 \leq k \leq \tfrac{1}{2}n \quad \Longrightarrow \quad \exp\left\{ -n \cdot \tfrac{k}{n} \left( 1 - \tfrac{k}{n} \right) \right\} = e^{-nq(k/n)} \leq e^{-k/2}. \tag{*} $$

To utilize this bound, we divide the sum into two part:

\begin{align*} S_{n} := e^{-n} \sum_{k=0}^{n} \binom{n}{k} \left( \frac{k}{n} \right)^{k} c^{k} &= e^{-n} \sum_{k=0}^{n} \binom{n}{k} \left( 1 - \frac{k}{n} \right)^{n-k} c^{n-k} \\ &\leq e^{-n} \sum_{k=0}^{n} \binom{n}{k} c^{n-k} e^{-nq(k/n)} \\ &\leq e^{-n} \sum_{k \leq \frac{n}{2}} \binom{n}{k} c^{n-k} e^{-nq(k/n)} + e^{-n} \sum_{\frac{n}{2} \leq k \leq n} \binom{n}{k} c^{n-k} e^{-nq(k/n)} \\ &= (c/e)^{n} \sum_{k \leq \frac{n}{2}} \binom{n}{k} c^{-k} e^{-nq(k/n)} + e^{-n} \sum_{k \leq \frac{n}{2}} \binom{n}{k} c^{k} e^{-nq(k/n)}. \end{align*}

Here, in the last line, we applied the change of index $k \mapsto n-k$. Then we can use $\text{(*)}$ and we get the following crude bound:

\begin{align*} S_{n} &\leq (c/e)^{n} \sum_{k \leq \frac{n}{2}} \binom{n}{k} \left( \frac{1}{c\sqrt{e}} \right)^{k} + e^{-n} \sum_{k \leq \frac{n}{2}} \binom{n}{k} \left( \frac{c}{\sqrt{e}} \right)^{k} \\ &\leq \left\{ \frac{c}{e} \left( 1 + \frac{1}{c\sqrt{e}} \right) \right\}^{n} + \left\{ \frac{1}{e} \left( 1 + \frac{c}{\sqrt{e}} \right) \right\}^{n}. \end{align*}

Now note that $c > 0$ satisfies the following condition

$$ \frac{c}{e} \left( 1 + \frac{1}{c\sqrt{e}} \right) < 1 \quad \text{and} \quad \frac{1}{e} \left( 1 + \frac{c}{\sqrt{e}} \right) < 1 \quad \Longleftrightarrow \quad c < e - \frac{1}{\sqrt{e}} \simeq 2.111751169. $$

Since your $c$ is less than $2$, the claim follows.

---

A slightly generally, you can introduce a parameter $\delta \in (0, 1)$. Then

\begin{align*} \begin{array}{cl} 0 \leq k \leq \delta n & \quad \Longrightarrow \quad \left( 1 - \tfrac{k}{n} \right)^{n-k} \leq e^{-(1-\delta)k}, \\ 0 \leq k \leq (1-\delta) n & \quad \Longrightarrow \quad \left( 1 - \tfrac{k}{n} \right)^{n-k} \leq e^{-\delta k} \end{array} \end{align*}

and our estimation is refined as

$$ S_{n} \leq \left( \frac{c}{e} + \frac{1}{e^{2-\delta}} \right)^{n} + \left( \frac{1}{e} + \frac{c}{e^{1+\delta}} \right)^{n}. $$

For both ratios to be less than 1, we must have $c < \min\{ e - e^{\delta-1}. e^{\delta}(e - 1) \}$. Maximizing this bound gives

$$ e^{\delta} = \frac{1 + e^{-1}}{1 + e^{-3}}, $$

Therefore

$$ c < \frac{e^{2}(e^{2} - 1)}{e^{3} + 1} \quad \Longrightarrow \quad S_{n} \leq \left( \frac{c}{e} + \frac{1}{e^{2}-e+1} \right)^{n} + \left( \frac{1}{e} + \frac{e^{2}-e+1}{e^{3}} c \right)^{n} \xrightarrow[n\to\infty]{} 0. $$