Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

5 Answers 5

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

share|improve this answer
    
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$. –  sos440 Mar 14 at 19:25
    
(-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.) –  TMM Mar 14 at 22:04
    
@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. –  robjohn Mar 15 at 1:23
    
@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. –  robjohn Mar 15 at 1:33
    
If my analysis is correct, the break is at $\approx 2.32$ which is slightly smaller than $e - 1/e \approx 2.35$. –  TMM Mar 15 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}}, $$

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

share|improve this answer
    
(+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$. –  TMM Mar 14 at 23:01
    
@TMM, Oh, thank you! I fixed that. –  sos440 Mar 15 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.$$

share|improve this answer
    
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$$ –  TMM Mar 13 at 15:42
1  
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}$. –  Timo mue Mar 14 at 15:22
    
@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...) –  TMM Mar 14 at 17:12
    
@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. –  TMM Mar 14 at 17:32
    
+1 for a sharp bound. –  sos440 Mar 14 at 22:49

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

share|improve this answer
    
I see. This is indeed an interesting bound. Unfortunately, it is larger than $(1+c)^n$, which makes it infeasible in my application. –  Timo mue Mar 12 at 19:27
    
How big is $c$ in your application? –  Hoda Mar 12 at 19:31
    
$c = (e+1)/2 = 1.85914...$. I am still trying to reduce it a bit, but this is it so far. –  Timo mue Mar 12 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)$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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