Evaluate limit $\lim_{n \to \infty } {1 \over n^{k + 1}}\left( {k! + {(k + 1)! \over 1!} + \cdots + {(k + n)! \over n!}} \right),k \in \mathbb{N}$

Evaluate the limit:
$$\lim_{n \to \infty } {1 \over n^{k + 1}}\left( {k! + {(k + 1)! \over 1!} + \cdots + {(k + n)! \over n!}} \right),k \in \mathbb{N}$$

It looks like a classic Cesaro-Stolz problem, but applying it didn't bring me any useful result.

I've been told the following equality might be helpful: $(1 - q)(1 + q + \cdots + q^N) = (1 - q^{N + 1})$

-
To write\mathop {\lim }\limits_{n \to \infty} instead of \lim_{n \to \infty} in displayed MathJax is bizarre. If it were inline, it could make sense to write \lim\limits_{n \to \infty}, but why write \mathop{\lim} when it's already a standard thing? It seems like being complicated for the sake of being complicated. – Michael Hardy Mar 22 '14 at 22:38
I'm sorry, I'm using MathType and didn't actually check the output it gives. Maybe changing the preferences will help? – AndrePoole Mar 22 '14 at 22:40
Could be.... I've never used MathType. – Michael Hardy Mar 22 '14 at 22:41
You just type manually? Sometimes the expression is too complicated. – AndrePoole Mar 22 '14 at 22:44
Stolz-Cesàro seems to work fine. First show that $(k+n)!/n! \sim n^k$ using Stirling's formula, then show that $\sum_{m=0}^{n} m^k \sim \frac{1}{k+1} n^{k+1}$ by comparing the sum to $\int_0^n x^k\,dx$. – Antonio Vargas Mar 22 '14 at 22:55

Hint: It can be shown that $$\sum_{m = 0}^n \frac{(k + m)!}{m!} = \frac{(n + 1)(k + n + 1)!}{(k + 1)(n + 1)!}.$$

You may find this formula useful.

If you then divide by $n^{k + 1}$ and take the limit as $n \to \infty$, you should get $$\frac{1}{1 + k}.$$

Edit: Using Stirling's asymptotic formula $N! \sim N^N e^{-N}\sqrt{2\pi N}$, where $\sim$ denotes asymptotic equality, we have $$\frac{(n + 1)(k + n + 1)!}{(n + 1)!} = \frac{(k + n + 1)!}{k^{k + 1}n!} \sim \frac{1}{n^{k + 1}} \frac{(k + n + 1)^{k + n + 1}e^{-(k + n + 1)}\sqrt{2\pi (k + n + 1)}}{n^n e^{-n}\sqrt{2\pi n}}.$$ If we simplify the right-hand side, we find that \begin{align*} \frac{1}{n^{k + n + 3/2}(k + n + 1)^{k + n + 3/2}e^{k + 1}} &= \left(1 + \frac{k + 1}{n}\right)^{-(k + n + 3/2)} e^{-(k + 1)}\\ &= \left(1 - \frac{-(k + 1)}{n}\right)^{-(k + n + 3/2)} e^{-(k + 1)}\\ &= \left[\left(1 - \frac{-(k + 1)}{n}\right)^{(k + n + 3/2)}\right]^{-1} e^{-(k + 1)}\\ &\to e^{k + 1}e^{-(k + 1)} \quad (\text{as } n \to \infty)\\ &= 1 \end{align*} because $$e^{-x} = \lim_{n \to \infty}\left(1 - \frac{x}{n}\right)^n$$ and $k + n + 3/2 \sim n$ as $n \to \infty$ since $k \in \mathbb{N}$ is fixed.

-

$\newcommand{\+}{^{\dagger}} \newcommand{\angles}[1]{\left\langle #1 \right\rangle} \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace} \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil #1 \right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\down}{\downarrow} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\isdiv}{\,\left.\right\vert\,} \newcommand{\ket}[1]{\left\vert #1\right\rangle} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left( #1 \right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert} \newcommand{\wt}[1]{\widetilde{#1}}$ $\ds{\lim_{n \to \infty }{1 \over n^{k + 1}}\bracks{% k! + {\pars{k + 1}! \over 1!} + \cdots + {\pars{k + n}! \over n!}}\,,\quad k \in \mathbb{N}:\ {\large ?}}$

\begin{align} &\lim_{n \to \infty }{1 \over n^{k + 1}}\bracks{% k! + {\pars{k + 1}! \over 1!} + \cdots + {\pars{k + n}! \over n!}} =\lim_{n \to \infty}{1 \over n^{k + 1}} \sum_{\ell = 0}^{n}{\pars{k + \ell}! \over \ell!} \\[3mm]&=k!\,\lim_{n \to \infty}{1 \over n^{k + 1}} \sum_{\ell = 0}^{n}{k + \ell \choose k} =k!\,\lim_{n \to \infty}{1 \over n^{k + 1}} \sum_{\ell = 0}^{n}\int_{\verts{z} = 1}{\pars{1 + z}^{k + \ell} \over z^{k + 1}}\,{\dd z \over 2\pi\ic} \\[3mm]&=k!\,\lim_{n \to \infty}{1 \over n^{k + 1}} \int_{\verts{z} = 1}{\pars{1 + z}^{k} \over z^{k + 1}} \sum_{\ell = 0}^{n}\pars{1 + z}^{\ell}\,{\dd z \over 2\pi\ic} \\[3mm]&=k!\,\lim_{n \to \infty}{1 \over n^{k + 1}} \int_{\verts{z} = 1}{\pars{1 + z}^{k} \over z^{k + 1}}\, {\pars{1 + z}^{n + 1} - 1 \over \pars{1 + z} - 1}\,{\dd z \over 2\pi\ic} \\[3mm]&=k!\,\lim_{n \to \infty}{1 \over n^{k + 1}} \bracks{% \overbrace{% \int_{\verts{z} = 1}{\pars{1 + z}^{k + n + 1} \over z^{k + 2}} \,{\dd z \over 2\pi\ic}}^{\ds{=\ {k + n + 1 \choose k + 1}}}\ -\ \overbrace{% \int_{\verts{z} = 1}{\pars{1 + z}^{k} \over z^{k + 2}} \,{\dd z \over 2\pi\ic}}^{\ds{=\ 0}}} \\[3mm]&=k!\, \lim_{n \to \infty}{1 \over n^{k + 1}}\,{\pars{k + n + 1}! \over \pars{k + 1}!\,n!} \\[3mm]&={k! \over \pars{k + 1}!}\, \lim_{n \to \infty}{1 \over n^{k + 1}}\, {\root{2\pi}\pars{k + n + 1}^{k + n + 3/2}\expo{-n - k - 1} \over \root{2\pi}n^{n + 1/2}\expo{-n}} \\[3mm]&={1 \over k + 1}\, \overbrace{\lim_{n \to \infty}\pars{1 + {k + 1 \over n}}^{k + n + 3/2}\expo{-k - 1}} ^{\ds{=\ 1}} \end{align}

$$\color{#00f}{\large% \lim_{n \to \infty }{1 \over n^{k + 1}}\bracks{% k! + {\pars{k + 1}! \over 1!} + \cdots + {\pars{k + n}! \over n!}} ={1 \over k + 1}}$$

-
You should not make the proof more complicated than it needs to be. – glebovg Mar 22 '14 at 23:16
Either way can't use integration. thanks though – AndrePoole Mar 22 '14 at 23:32
@glebovg It's likely true. However, it's quite general and the technique is quite useful in more complicated situations. Once I saw the result I had the feeling there is a shorter way to do it but it was too late. That expression of the combinatoric in terms of a contour integral is quite useful. Thanks. – Felix Marin Mar 22 '14 at 23:53
@FelixMarin Indeed. Using contour integration is perhaps a bit of overkill, but this general technique is quite useful nonetheless. Nice answer. – glebovg Mar 23 '14 at 0:25
@glebovg The other answers just use the sum result without any derivation of it. – Felix Marin Mar 23 '14 at 0:47

Factor out the k!. Use the identity: 1 + C(k,k) + C(k+1,k) +...+ C(k+n,k) = C(k+n+1,k+1). Thus the expression equals: k!(n+k+1)!/((k+1)!n!n^(k+1)) = (1+1/n)(1+2/n)...(1+(k+1)/n)/(k+1) ---> 1/(k+1) as n --> infinity.

-