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?


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\%$.

  • $\begingroup$ I was also trying similar approach, so I am curious how you treated the cumbersome bound $e^{k^{2}/n}$, especially when $k \approx n$. $\endgroup$ – Sangchul Lee Mar 14 '14 at 19:25
  • $\begingroup$ (-1) for ignoring the $e^{k^2/n}$ (which certainly cannot be treated as a constant) leading to a wrong result, and for ignoring the fact that your asymptotics are off. Just plug in some largish value of $n$ and you will see that what you claim is asymptotically equivalent to the sum is not. (But of course if you had read my answer you would have known.) $\endgroup$ – TMM Mar 14 '14 at 22:04
  • $\begingroup$ @TMM: thanks for your concern. However after sos440's comment, I was looking more closely, and I found a more conservative bounding $c$. However, my numerical investigation with $n=10000$ showed a break close to $e-1/e$, so I tried to see if I could get closer to that. Unfortunately, I am out right now and I can barely post a comment on my phone, much less post any better estimates. $\endgroup$ – robjohn Mar 15 '14 at 1:23
  • $\begingroup$ @sos440: Yes, I see that the error term can not be ignored. I have worked the afternoon on fixing this up. I will post the corrected version in a while. $\endgroup$ – robjohn Mar 15 '14 at 1:33
  • $\begingroup$ If my analysis is correct, the break is at $\approx 2.32$ which is slightly smaller than $e - 1/e \approx 2.35$. $\endgroup$ – TMM Mar 15 '14 at 1:59

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}}, $$


$$ 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. $$

  • $\begingroup$ (+1) for being very precise, and for finding a bound on $c$. In the last equation I think you made a typo though, you probably wanted to write $c < e - \frac{1}{\sqrt e}$. I've also updated my answer with a bound for $c$. $\endgroup$ – TMM Mar 14 '14 at 23:01
  • $\begingroup$ @TMM, Oh, thank you! I fixed that. $\endgroup$ – Sangchul Lee Mar 15 '14 at 5:29

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.$$

  • $\begingroup$ The most elegant form for the constant $-0.26\dots$ I can find is $$\frac{2}{e(1+e) \ln 2} - \log_2\left(\frac{2e}{1+e}\right) = \frac{1}{e c \ln 2} - \log_2\left(\frac{e}{c}\right) = -0.26258\dots$$ $\endgroup$ – TMM Mar 13 '14 at 15:42
  • 1
    $\begingroup$ Thanks! This looks really nice. I am not that familiar with estimates where we identify the center of mass of the sum. In particular, I have no feel for the ''errors'' you are getting with this method. I am currently working on the proof and I will also post it here. It looks like my ''direct'' approach gives a convergence with $2^{-0.204433n}$, which is slightly weaker than your $2^{-0.26258n}$. $\endgroup$ – Timo mue Mar 14 '14 at 15:22
  • $\begingroup$ @Timomue Like I said, for $n = 500$, the estimate is only $10\%$ off on an answer of the order $10^{-40}$, which is quite amazing. (For $n = 500$, your constant gives an estimate of $1.69 \cdot 10^{-31}$, which is almost a factor $10^{10}$ too high...) $\endgroup$ – TMM Mar 14 '14 at 17:12
  • $\begingroup$ @Timomue As for the "errors" you are getting, I've added a bit, showing that the errors are really small if you only focus on the highest mass. On the left hand side you can probably even replace the $o(n)$ in the exponent by $O(1)$ and in the right hand side by $O(\log n)$, if you want to be precise. $\endgroup$ – TMM Mar 14 '14 at 17:32
  • $\begingroup$ @TMM: I think the $10\%$ error might be due to the factor of $1.11655$ that falls out of my second approach using Laplace's Method for $c=\frac{e+1}{2}$. $\endgroup$ – robjohn Mar 16 '14 at 16:31

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}$$

  • $\begingroup$ I see. This is indeed an interesting bound. Unfortunately, it is larger than $(1+c)^n$, which makes it infeasible in my application. $\endgroup$ – Timo mue Mar 12 '14 at 19:27
  • $\begingroup$ How big is $c$ in your application? $\endgroup$ – Hoda Mar 12 '14 at 19:31
  • $\begingroup$ $c = (e+1)/2 = 1.85914...$. I am still trying to reduce it a bit, but this is it so far. $\endgroup$ – Timo mue Mar 12 '14 at 19:37

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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.