# Can we prove that $\lim_{n\to\infty} \frac{1^{n_0}+2^{n_0}+\cdots+n^{n_0}}{n^{n_0+1}}$ is finite for any $n_0\in\Bbb N$ without a direct computation?

Can we prove without direct calculation that this limit is finite for any natural number $n_0 \in \mathbb{N}$?

$$\lim_{n \to \infty} \frac{1^{n_0}+2^{n_0}+\cdots+n^{n_0}}{n^{n_0+1}}$$

• Of course, without direct calculation of the sum Aug 13 '18 at 17:56
– xbh
Aug 13 '18 at 17:57
• I assume your denominator was typed wrong, it should be $n^{n_0+1}$, I think.
– xbh
Aug 13 '18 at 17:58
• I changed the condition a little, now it's kind of true Aug 13 '18 at 17:58
• The numerator do not exceed $n \times n^{n_0}$.
– xbh
Aug 13 '18 at 18:00

The numerator can be expressed as a polynomial $P(n)$ of degree $n_0+1$, because $P(n)-P(n-1)=n^{n_0}$ is a polynomial of degree $n_0$.

So the limit of $$\dfrac{P(n)}{n^{n_0+1}}$$ is finite.

By the Faulhaber's formulas, the limit is $\dfrac1{n_0+1}$.

• I do not really understand your answer, would you clarify? Why can it be expressed through a polynomial of degree higher Aug 13 '18 at 18:04
• Why does such a polynomial exist? I don't know how to show there is such a $P$ with $P(n) - P(n-1) = n^{n_0}$ without explicitly constructing it. Aug 13 '18 at 18:05
• @VladislavKharlamov: if $P(n)$ is a polynomial of degree $n_0+1$ then $P(n)-P(n-1)$ is a polynomial of degree $n_0$ and conversely.
– user65203
Aug 13 '18 at 18:31
• @JairTaylor: expand $P(n)-P(n-1)$ where the coefficients are indeterminate; then identify to some $Q(n)$ and solve for the coefficients. The system is triangular.
– user65203
Aug 13 '18 at 18:35
• Could you justify the assertion (be that by proof, link, etc.) that, for $f:\mathbb{N} \to \mathbb{N}$, if $f(x+1) - f(x)$ is a polynomial for each $x \in \mathbb{N}$, then $f$ is a polynomial? Your entire answer hinges on this fact and its validity is not at all apparent to me nor it appears several others. Aug 13 '18 at 22:00

For positive integer $k\leq n$ we have $$\int_{k-1}^kx^{n_0}dx<k^{n_0}<\int_k^{k+1}x^{n_0}dx.$$ Now add from $k=1$ to $k=n.$

• Best answer ... I would have posted it if I got here first. In fact, this method will yield the exact value $1/(n_0+1)$ for the limit in question. Aug 13 '18 at 20:37
• To the proposer: Comparison to an integral is a widely-used tool to obtain estimates or to prove convergence of a series. Aug 14 '18 at 2:05

I'll use $p$ instead of $n_0$. The number you're interested in is: $$L_p=\lim_{n\to\infty}\frac{1^p+2^p+\cdots+n^p}{n^{p+1}}$$ Alternatively, by factoring out $1/n$, we may write: $$L_p=\lim_{n\to\infty}\frac 1n\sum_{k=1}^n\left(\frac kn\right)^p$$ The term in the limit is an average of $n$ values all of which are in $[0,1]$, provided $p>0$. The limit function itself then must be bounded to this interval.

This does not show that the limit exists, but provided it does, it must be in the unit interval.

• This also shows that $L_p=\int_0^1 x^p\,dx$ since the sum can be interpreted as a Riemann sum for integration. This corresponds to Yves' answer. Aug 13 '18 at 18:13
• Indeed. That would suffice to show that the sum converges, but it would require the additional baggage of Riemann integrability. Aug 13 '18 at 18:14

Here's a completely elementary proof that just uses Bernoulli's inequality.

$\begin{array}\\ (x+1)^m-x^m &=x^m((1+1/x)^m-1)\\ &\ge x^m(1+m/x-1) \qquad\text{by Bernoulli}\\ &=mx^{m-1}\\ \end{array}$

Therefore $\sum_{k=0}^{n-1} k^{m-1} \le \sum_{k=0}^{n-1}\frac1{m}((k+1)^m-k^m) =\frac1{m}n^m$ so, for $m \ge 2$, $\sum_{k=1}^{n} k^{m-1} \le n^{m-1}+\frac1{m}n^m$ or $\frac1{n^m}\sum_{k=1}^{n} k^{m-1} \le \frac1{n^m}(n^{m-1}+\frac1{m}n^m) =\frac1{n}+\frac1{m}$ which is bounded.

You have to work a little harder to show that $\frac1{m}$ is the actual limit.

Alternative method: Cesàro-stolz theorem [if you've learned].

• @VladislavKharlamov Then you can see other answers. Although the one above seems need a bit calculation of the first coefficient of the polynomial, which may not be simpler too much.
– xbh
Aug 13 '18 at 18:05
• It's Cesaro-Stolz (at least that's the name by which is popular). Aug 14 '18 at 4:27
• @ParamanandSingh Thanks! I forgot this since in my text we only say "O. Stolz" formula. I might stick to my original terminologies.
– xbh
Aug 14 '18 at 6:54

As in Falling and rising factorials, define (using $p$ instead of $n_0$, as in a previous answer): \begin{align*} (k)_p & = k(k - 1)\cdots(k - p + 1), \\ k^{(p)} & = k(k + 1)\cdots(k + p - 1). \end{align*} Then: \begin{align*} (k + 1)_{p + 1} - k_{p + 1} & = (p + 1)(k)_p, \\ k^{(p + 1)} - (k - 1)^{(p + 1)} & = (p + 1)k^{(p)}. \end{align*} For every positive integer $k$, $$(k)_p \leqslant k^p \leqslant k^{(p)}.$$ Hence, for every positive integer $n$, $$\frac{(n + 1)_{p + 1}}{p + 1} \leqslant \sum_{k=1}^n k^p \leqslant \frac{n^{(p + 1)}}{p + 1}.$$ But $$\frac{(n + 1)_{p + 1}}{n^{p + 1}} \to 1 \text{ as } n \to \infty, \text{ and } \frac{n^{(p + 1)}}{n^{p + 1}} \to 1 \text{ as } n \to \infty,$$ therefore $$\frac{\sum_{k=1}^n k^p}{n^{p + 1}} \to \frac{1}{p + 1} \text{ as } n \to \infty.$$