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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have the following limit:

$$\lim_{n\rightarrow\infty}e^{-\alpha\sqrt{n}}\sum_{k=0}^{n-1}2^{-n-k} {{n-1+k}\choose k}\sum_{m=0}^{n-1-k}\frac{(\alpha\sqrt{n})^m}{m!}$$

where $\alpha>0$.

Evaluating this in Mathematica suggests that this converges, but I don't know how to evaluate it. Any help would be appreciated.

share|cite|improve this question

Let $A_n$ denote the formula inside the limit. By noting that the double summation is taken for those non-negative integers $k, m$ with $l := k+m \leq n-1$, by changing the order of summation,

$$\begin{align*} A_n &= e^{-\alpha\sqrt{n}} \sum_{m=0}^{n-1}\sum_{k=0}^{n-1-m} \binom{n-1+k}{k} 2^{-n-k}\frac{(\alpha \sqrt{n})^m}{m!} \\ &= \frac{e^{-\alpha\sqrt{n}}}{(n-1)!} \sum_{m=0}^{n-1} \left( \sum_{k=0}^{n-1-m} \frac{1}{k!} \frac{(n-1+k)!}{2^{n+k}} \right) \frac{(\alpha \sqrt{n})^m}{m!} \\ &= \frac{e^{-\alpha\sqrt{n}}}{(n-1)!} \sum_{m=0}^{n-1} \left( \sum_{k=0}^{n-1-m} \frac{1}{k!} \int_{0}^{\infty} x^{n+k-1}e^{-2x}\;dx \right) \frac{(\alpha \sqrt{n})^m}{m!} \\ &= \frac{e^{-\alpha\sqrt{n}}}{(n-1)!} \int_{0}^{\infty} \left( \sum_{m=0}^{n-1} \sum_{k=0}^{n-1-m} \frac{x^k}{k!} \frac{(\alpha \sqrt{n})^m}{m!} \right) x^{n-1} e^{-2x}\;dx \\ &= \frac{e^{-\alpha\sqrt{n}}}{(n-1)!} \int_{0}^{\infty} \left( \sum_{l=0}^{n-1} \sum_{k=0}^{l} \frac{x^k}{k!} \frac{(\alpha \sqrt{n})^{l-k}}{(l-k)!} \right) x^{n-1} e^{-2x}\;dx \\ &= \frac{e^{-\alpha\sqrt{n}}}{(n-1)!} \int_{0}^{\infty} \left( \sum_{l=0}^{n-1} \frac{(x+\alpha\sqrt{n})^l}{l!} \right) x^{n-1} e^{-2x}\;dxdx \\ &= \int_{0}^{\infty} \left( \sum_{l=0}^{n-1} \frac{(x+\alpha\sqrt{n})^l}{l!} e^{-(x+\alpha\sqrt{n})} \right) \frac{x^{n-1} e^{-x}}{(n-1)!}\;dx. \end{align*}$$

Now, observe that

$$ \begin{align*} &\sum_{l=0}^{n-1} \frac{(x+\alpha\sqrt{n})^l}{l!} e^{-(x+\alpha\sqrt{n})} \\ &\hspace{5em}= \frac{1}{(n-1)!}\sum_{l=0}^{n-1} \binom{n-1}{l} (x+\alpha\sqrt{n})^l e^{-(x+\alpha\sqrt{n})} \int_{0}^{\infty} t^{n-1-l}e^{-t} \; dt \\ &\hspace{5em}= \frac{1}{(n-1)!} \int_{0}^{\infty} (t+x+\alpha\sqrt{n})^{n-1} e^{-(t+x+\alpha\sqrt{n})} \; dt \\ &\hspace{5em}= \frac{1}{(n-1)!} \int_{x+\alpha\sqrt{n}}^{\infty} t^{n-1}e^{-t} \; dt = \frac{\Gamma(n,x+\alpha\sqrt{n})}{\Gamma(n)}, \end{align*} $$

where $\Gamma(s,x)$ is the incomplete gamma function. So if we define $G_n(x)$ as

$$G_n(x) = \frac{\Gamma(n,x)}{\Gamma(n)} ,$$

the above calculation shows that we can write

$$ A_n = - \int_{0}^{\infty} G_n(x+\alpha\sqrt{n})G_n'(x)\;dx. \tag{1} $$

Now let $$\{ X_1, X_2, \cdots, Y_1, Y_2, \cdots \}$$ be a family of independent random variables each having an exponential distribution of parameter $1$. Then for its partial sums $S_n = X_1 + \cdots + X_n$ and $T_n = Y_1 + \cdots + Y_n$, it is easy to see that

$$ F_{S_n}(x) = \Bbb{P}(S_n \leq x) = 1 - G_n (x) $$

and likewise for $F_{T_n}(x) = \Bbb{P}(T_n \leq x)$. Thus $(1)$ reduces to

$$ \begin{align*} A_n &= \int_{0}^{\infty} \Bbb{P}\left(T_n > x+\alpha\sqrt{n}\right) \; dF_{S_n}(x) \\ & = \Bbb{P}\left(T_n > S_n +\alpha\sqrt{n}\right) = \Bbb{P}\left(\frac{T_n - n}{\sqrt{n}} > \frac{S_n - n}{\sqrt{n}} +\alpha\right). \end{align*}$$

Since $\Bbb{E}S_n = \Bbb{E}S_n = n$ and $\Bbb{V}S_n = \Bbb{V}T_n = n$, central limit theorem yields

$$ \lim_{n\to\infty} A_n = \Bbb{P}\left(Z_2 > Z_1 +\alpha\right), $$

where $Z_i \sim N(0, 1)$ are independent random variables each having a standard normal distribution. Therefore we have

$$ \lim_{n\to\infty} A_n = \frac{1}{2}\left[ 1 - \mathrm{erf}\left(\frac{\alpha}{2}\right)\right] $$

share|cite|improve this answer

Let $X_n$ denote a Poisson random variable with parameter $\alpha\sqrt{n}$ and $Y_n$ a negative binomial random variable with parameters $(n,\frac12)$. Recall that this means that, for every $k\geqslant0$, $$ P[X_n=k]=\mathrm e^{-\alpha\sqrt{n}}\frac{(\alpha\sqrt{n})^k}{k!},\qquad P[Y_n=k]=2^{-n-k} {n-1+k\choose k}. $$ Thus, assuming that $X_n$ and $Y_n$ are independent, the $n$th sum you are considering is $$ S_n=P[X_n+Y_n\leqslant n-1]. $$ First, $Y_n$ can be realized as the sum of $n$ i.i.d. random variables with geometric distribution of parameter $\frac12$, in particular, the central limit theorem states that $Y_n=n+\sqrt{2n}Z_n$ where $Z_n$ converges in distribution to a standard random variable $Z$. Second, the variance of a Poisson random variable being equal to its mean, $X_n=\alpha\sqrt{n}+\sqrt{n}T_n$ where $T_n\to0$ in distribution. Hence, $$ \frac{X_n+Y_n-n+1}{\sqrt{n}}=\alpha+T_n+\sqrt{2}Z_n+\frac1{\sqrt{n}} $$ converges in distribution to $\alpha+\sqrt{2}Z$. Thus, $$ S_n=P\left[\frac{X_n+Y_n-n+1}{\sqrt{n}}\leqslant0\right]\to S=P[\alpha+\sqrt{2}Z\leqslant0], $$ and $$ S=1-\Phi\left(\frac{\alpha}{\sqrt2}\right)=\frac12\left(1-\mathrm{erf}\left(\frac{\alpha}{2}\right)\right). $$

share|cite|improve this answer

Maybe start by doing something along the lines of noting that

$$\sum_{m=0}^{\infty}\frac{(\alpha\sqrt{n})^m}{m!} = e^{\alpha \sqrt{n}}$$

so that the final sum is

$$e^{\alpha \sqrt{n}} - \sum_{m=n-k}^{\infty}\frac{(\alpha\sqrt{n})^m}{m!}$$

share|cite|improve this answer

I would start even more simple-mindedly by replacing the inner sum with its infinite $n$ value of $e^{\alpha \sqrt{n}}$. This cancels out the outer expression, so we are left with

$\lim_{n\rightarrow\infty}\sum_{k=0}^{n-1}2^{-n-k} {{n-1+k}\choose k}$.

Doing some manipulation, $\sum_{k=0}^{n-1}2^{-n-k} {{n-1+k}\choose k} = \sum_{k=0}^{n-1}2^{-n-k} {{n-1+k}\choose {n-1}} = \sum_{k=n-1}^{2n-2}2^{-k-1} {{k}\choose {n-1}} $.

As often happens, it is late and I am tired and not sure exectly what to do next, so I'll leave it at this.

share|cite|improve this answer

Your Answer


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.