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.

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

share|improve this question
    
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 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 at 22:40
    
Could be.... I've never used MathType. –  Michael Hardy Mar 22 at 22:41
    
You just type manually? Sometimes the expression is too complicated. –  AndrePoole Mar 22 at 22:44
1  
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 at 22:55

3 Answers 3

up vote 3 down vote accepted

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.

share|improve this answer

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

share|improve this answer
    
You should not make the proof more complicated than it needs to be. –  glebovg Mar 22 at 23:16
    
Either way can't use integration. thanks though –  AndrePoole Mar 22 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 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 at 0:25
    
@glebovg The other answers just use the sum result without any derivation of it. –  Felix Marin Mar 23 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.

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.