TITLE: Prove by Induction ( a Limit)
QUESTION [2 upvotes]: I think I did a lot wrong in my attempt to solve this exercise. I think I did solve it, in that case I'd like to know others way to solve the problem.
(Introduction to calculus and analysis vol 1, Courant page 113, exersice 16 )
Prove the relation 
$$ \lim_{n\to \infty}\frac{1}{n^{k+1}} \sum_{i=1}^{n} i^{k} = \frac{1}{k+1}$$
for any nonnegative integer $k$. (Hint: use induction with respect to $k$ and use relation  $$\sum_{i=1}^{n} i^{k+1} - (i-1)^{k+1} = n^{k+1}  ,$$ 
expanding $(i-1)^{k+1}$ in powers of $i$).

what I've done – $P(k): \lim_{n\to \infty}\frac{1}{n^{k+1}} \sum_{i=1}^{n} i^{k} = \frac{1}{k+1}$ and use induction.
$P(1) : \lim_{n\to \infty}\frac{1}{n^{2}} \sum_{i=1}^{n} i = \lim_{n\to \infty}\frac{1}{n^{2}} \frac{n(n+1)}{2} = \frac{1}{2} = \frac{1}{1+1}$
Then suppose $P(k)$ I want to deduce $P(k+1):\lim_{n\to \infty}\frac{1}{n^{(k+1)+1}} \sum_{i=1}^{n} i^{k+1} = \frac{1}{(k+1)+1}$ . I use $$ \sum_{i=1}^{n} i^{k+2} - (i-1)^{k+2} = n^{k+2}$$ using the binomio sum (Newton) $$n^{k+2} =\sum_{i=1}^{n} i^{k+2} - (i-1)^{k+2} = \sum_{i=1}^{n} -\sum_{j=2}^{k+2} \binom{k+2}{j} i^{(k+2)-j} (-1)^j + (k+2)\sum_{i=0}^{n} i^{k+1} = -\sum_{j=2}^{k+2} \binom{k+2}{j}(-1)^j \sum_{i=1}^{n} i^{(k+2)-j} + (k+2)\sum_{i=0}^{n} i^{k+1} $$ Then I replace in $P(k+1)$
$$\lim_{n\to \infty}\frac{1}{n^{(k+1)+1}} \sum_{i=1}^{n} i^{k+1} = \lim_{n\to \infty}\frac{\sum_{i=1}^{n} i^{k+1}}{-\sum_{j=2}^{k+2} \binom{k+2}{j}(-1)^j \sum_{i=1}^{n} i^{(k+2)-j} + (k+2)\sum_{i=0}^{n} i^{k+1}} = \lim_{n\to \infty}\frac{1}{\frac{-\sum_{j=2}^{k+2} \binom{k+2}{j}(-1)^j \sum_{i=1}^{n} i^{(k+2)-j}}{\sum_{i=1}^{n} i^{k+1}} + (k+2)} $$ Then using limits properties I want to (I know that I have to use induction hip, but I don't know how to follow)
$$\lim_{n\to \infty}\frac{-\sum_{j=2}^{k+2} \binom{k+2}{j}(-1)^j \sum_{i=1}^{n} i^{(k+2)-j}}{\sum_{i=1}^{n} i^{k+1}} = 0 $$
some help to solve this in an easy way?

REPLY [0 votes]: I think that it is easier to show that
$$
\frac{-%
%TCIMACRO{\dsum \limits_{j=2}^{k+2}}%
%BeginExpansion
{\displaystyle\sum\limits_{j=2}^{k+2}}
%EndExpansion
\binom{k+2}{j}\left(  -1\right)  ^{j}%
%TCIMACRO{\dsum \limits_{i=1}^{n}}%
%BeginExpansion
{\displaystyle\sum\limits_{i=1}^{n}}
%EndExpansion
i^{k+2-j}}{n^{k+2}}=-%
%TCIMACRO{\dsum \limits_{j=2}^{k+2}}%
%BeginExpansion
{\displaystyle\sum\limits_{j=2}^{k+2}}
%EndExpansion
\binom{k+2}{j}\left(  -1\right)  ^{j}\frac{%
%TCIMACRO{\dsum \limits_{i=1}^{n}}%
%BeginExpansion
{\displaystyle\sum\limits_{i=1}^{n}}
%EndExpansion
i^{k+2-j}}{n^{k+2}}\rightarrow0
$$
by induction.
So from
$$
n^{k+2}=-%
%TCIMACRO{\dsum \limits_{j=2}^{k+2}}%
%BeginExpansion
{\displaystyle\sum\limits_{j=2}^{k+2}}
%EndExpansion
\binom{k+2}{j}\left(  -1\right)  ^{j}%
%TCIMACRO{\dsum \limits_{i=1}^{n}}%
%BeginExpansion
{\displaystyle\sum\limits_{i=1}^{n}}
%EndExpansion
i^{k+2-j}+\left(  k+2\right)
%TCIMACRO{\dsum \limits_{i=0}^{n}}%
%BeginExpansion
{\displaystyle\sum\limits_{i=0}^{n}}
%EndExpansion
i^{k+1}%
$$
we get
$$
1=\frac{-%
%TCIMACRO{\dsum \limits_{j=2}^{k+2}}%
%BeginExpansion
{\displaystyle\sum\limits_{j=2}^{k+2}}
%EndExpansion
\binom{k+2}{j}\left(  -1\right)  ^{j}%
%TCIMACRO{\dsum \limits_{i=1}^{n}}%
%BeginExpansion
{\displaystyle\sum\limits_{i=1}^{n}}
%EndExpansion
i^{k+2-j}}{n^{k+2}}+\left(  k+2\right)  \frac{%
%TCIMACRO{\dsum \limits_{i=0}^{n}}%
%BeginExpansion
{\displaystyle\sum\limits_{i=0}^{n}}
%EndExpansion
i^{k+1}}{n^{k+2}}%
$$
and hence
$
\frac{%
%TCIMACRO{\dsum \limits_{i=0}^{n}}%
%BeginExpansion
{\displaystyle\sum\limits_{i=0}^{n}}
%EndExpansion
i^{k+1}}{n^{k+2}}\rightarrow\frac{1}{k+2}.
$

REPLY [0 votes]: The general technique is to attempt to find a sufficiently good approximation to the anti-difference (summation). In this case a first-order approximation is enough.
$(i+1)^{k+1} - i^{k+1} = (k+1) i^k + \sum_{j=0}^{k-1} \binom{k+1}{j} i^j$. [The most significant term is the one we want.]
$\sum_{i=1}^n (k+1)i^k = \sum_{i=1}^n \left( (i+1)^{k+1} - i^{k+1} - \sum_{j=0}^{k-1} \binom{k+1}{j} i^j \right)$
$\ = (n+1)^{k+1} - 1 - \sum_{i=1}^n \sum_{j=0}^{k-1} \binom{k+1}{j} i^j$.
$\frac{1}{n^{k+1}} \sum_{i=1}^n (k+1)i^k = (1+\frac{1}{n})^{k+1} - \frac{1}{n^{k+1}} - \sum_{j=0}^{k-1} \left( \frac{1}{n^{k-j}} \binom{k+1}{j} \frac{1}{n^{j+1}} \sum_{i=1}^n i^j \right)$
$\ \approx 1 - 0 - \sum_{j=0}^{k-1} \left( \frac{1}{n^{k-j}} \binom{k+1}{j} \frac{1}{j+1} \right)$ [by induction]
$\ \approx 1$
{"set_name": "stack_exchange", "score": 2, "question_id": 1344003}