Base case for $\sum_{j=1}^{n-1}{j^k}<\frac{n^{k+1}}{k+1}$ with $k\in \mathbb{N}$ and $n\geq 2$

Question

Base case for $\sum_{j=1}^{n-1}{j^k}<\frac{n^{k+1}}{k+1}$ with $k\in \mathbb{N}$ and $n\geq 2$

Do I have to use $k_0=1$ and $n_0=2$? I am a little confused since that's what I can come up with:$$j^1<\frac{2^{1+1}}{1+1}=2$$

Answer 1

Presumably, you're performing your induction on $n$, where $n \in \{2,3,...\}$.

Since you want to show the expression holds for $n \ge 2$, you should choose your base case to be $n=2$. As for $k$, keep it arbitrary (aside from being a natural number). Thus, you would verify

$$\sum_{j=1}^{2-1} j^k < \frac{n^{k+1}}{k+1} \iff 1 < \frac{2^{k+1}}{k+1}$$

where $k \in \Bbb N$. I believe you could attempt to prove this by induction as well, this time on $k$ in $\Bbb N$.

To recollection, this sort of proof - where you have to do induction for the intermediate bits - is called "nested induction," but I don't have much experience outside of ordinary induction, so grain of salt.

Answer 2

The Mean Value Theorem says that for some $\xi\in(0,1)$, $$ \frac{(j+1)^{k+1}}{k+1}-\frac{j^{k+1}}{k+1}=(j+\xi)^k\ge j^k $$ Sum over $j$ from $0$ to $n-1$ $$ %\begin{align} \frac{n^{k+1}}{k+1} &=\sum_{j=0}^{n-1}\left(\frac{(j+1)^{k+1}}{k+1}-\frac{j^{k+1}}{k+1}\right)\\ &\ge\sum_{j=0}^{n-1}j^k \end{align} $$