4
$\begingroup$

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

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

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

$\endgroup$
8
  • $\begingroup$ I do not really understand your answer, would you clarify? Why can it be expressed through a polynomial of degree higher $\endgroup$ Aug 13 '18 at 18:04
  • $\begingroup$ 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. $\endgroup$ Aug 13 '18 at 18:05
  • $\begingroup$ @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. $\endgroup$
    – user65203
    Aug 13 '18 at 18:31
  • $\begingroup$ @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. $\endgroup$
    – user65203
    Aug 13 '18 at 18:35
  • $\begingroup$ 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. $\endgroup$
    – Alex W
    Aug 13 '18 at 22:00
3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – GEdgar
    Aug 13 '18 at 20:37
  • $\begingroup$ To the proposer: Comparison to an integral is a widely-used tool to obtain estimates or to prove convergence of a series. $\endgroup$ Aug 14 '18 at 2:05
2
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Clayton
    Aug 13 '18 at 18:13
  • $\begingroup$ Indeed. That would suffice to show that the sum converges, but it would require the additional baggage of Riemann integrability. $\endgroup$
    – Kajelad
    Aug 13 '18 at 18:14
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ @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. $\endgroup$
    – xbh
    Aug 13 '18 at 18:05
  • $\begingroup$ It's Cesaro-Stolz (at least that's the name by which is popular). $\endgroup$ Aug 14 '18 at 4:27
  • $\begingroup$ @ParamanandSingh Thanks! I forgot this since in my text we only say "O. Stolz" formula. I might stick to my original terminologies. $\endgroup$
    – xbh
    Aug 14 '18 at 6:54
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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