Using induction on $k$, show that $\sum\limits^{n-1}_{i=1} i^k \le \frac{n^{k+1}}{k+1} \le \sum\limits^n_{i=1} i^k$

Question

Prove using induction on $k$ that $\sum^{n-1}_{i=1} i^k \le \frac{n^{k+1}}{k+1} \le \sum^{n}_{i=1} i^k$

I need to assume $\sum^{n-1}_{i=1} i^p \le \frac{n^{p+1}}{p+1} \le \sum^{n}_{i=1} i^p$ and prove that $\sum^{n-1}_{i=1} i^{p+1} \le \frac{n^{p+2}}{p+2} \le \sum^{n}_{i=1} i^{p+1}$

I'm stuck at the general part, any hints would be appreciated.

I found one way of doing this by looking at the graph of $x^k$ and then bounding the area between $[0,n]$ by inner and outer rectangles.

Answer 1

Let $S_k(0)=0$ and, for every positive integer $n$, $S_k(n)=\sum\limits_{i=1}^ni^k$. The goal is to prove, using a recursion on the nonnegative integer $k$, that $$\forall n\geqslant0,\qquad n^{k+1}\leqslant(k+1)S_k(n)\leqslant (n+1)^{k+1}\tag{1}$$

For $k=0$, $S_0(n)=n$ for every nonnegative $n$ and $(1)$ reads $n\leqslant S_0(n)\leqslant n+1$ hence $(1)$ holds.

For $k\geqslant0$, first note that $$S_{k+1}(n)=\sum_{i=1}^ni^k\sum_{j=1}^i1=\sum_{j=1}^n\sum_{i=j}^ni^k=\sum_{j=1}^n(S_k(n)-S_k(j-1))$$ that is, $$S_{k+1}(n)=nS_k(n)-\sum_{j=1}^nS_k(j-1)\tag{2}$$ Now, assume that $(1)$ holds for some given $k\geqslant0$. Then the upper bounds in $(1)$ applied to each $S_k(j-1)$ in $(2)$ yield the lower bound $$S_{k+1}(n)\geqslant nS_k(n)-\sum_{j=1}^n\frac{j^{k+1}}{k+1}=nS_k(n)-\frac{S_{k+1}(n)}{k+1}$$ that is, $$(k+2)S_{k+1}(n)\geqslant n(k+1)S_k(n)$$ which implies that the lower bound in $(1)$ holds for $S_{k+1}(n)$.

Likewise, the lower bounds in $(1)$ applied to each $S_k(j-1)$ in $(2)$ yield the upper bound $$S_{k+1}(n)\leqslant nS_k(n)-\sum_{j=1}^n\frac{(j-1)^{k+1}}{k+1}=nS_k(n)-\frac{S_{k+1}(n)}{k+1}+\frac{n^{k+1}}{k+1}$$ that is, $$(k+2)S_{k+1}(n)\leqslant n(k+1)S_k(n)+n^{k+1}$$ Now, using the upper bound in $(1)$ for $S_k(n)$, one gets $$(k+2)S_{k+1}(n)\leqslant n(n+1)^{k+1}+n^{k+1}\leqslant n(n+1)^{k+1}+(n+1)^{k+1}=(n+1)^{k+2}$$ which completes the proof.

Answer 2

HINT. Let $f(n)=\sum_{i=1}^{n-1} i^k.\;$ If $f(n)\leq \frac {n^{k+1}}{k+1}$ then $$f(n+1)=f(n)+n^k\leq \frac {n^{k+1}}{k+1}+n^k=$$ $$=\frac {n^{k+1}+(k+1)n^k}{k+1}.$$ The numerator in the last expression above cannot exceed $\sum_{j=0}^{k+1} \binom {k+1}{j}n^{k+1-j}=(n+1)^{k+1}.$ (Binomial Theorem.)

So $f(n)\leq \frac {n^{k+1}}{k+1}\implies f(n+1)\leq \frac {(n+1)^{k+1}}{k+1}.$

BTW the above definition of $f(n),$ when $n=1,$ reads $\sum_{i=1}^0i^k.$ The usual custom is that this, the sum of the members of the empty set, is defined to be $0.$