Proof by Induction for an Inequality

Question

In Tom Apostol's Calculus Vol 1, there is an exercise (i4.10 13) to prove by induction:

$$\sum_{k=1}^{n-1} k^p \lt \frac{n^{p+1}}{p+1} \lt \sum_{k=1}^{n} k^p$$

It is a 3 part exercise, and in a preceding part, it says

Let p and n denote positive integers

While in part c (this part of the exercise), the text suggests you to use the result from part b. I take this to mean that we ought to let n and p be positive integers. So for my first step, I am thinking I should be able to let $n=1$.

Does this make sense with the range being k=1, and the top equal to 0? Should I interpret the set as

$$ \sum_{k=1}^{n-1} k^p = 1^p + 0^p $$

Answer 1

I'm going to start off by repeating the comments:

• It would be helpful to know what sort of proof was expected by seeing part (b) of the problem.
• No, your interpretation of the summation when $n=1$ is not correct. The intended meaning is the sum over all $k$ for which $1\leq k\leq 0$; of course no such $k$ exist, so that sum is zero.

In particular, the base case reads: $$0=\sum_{k=1}^{1-1} k^p \lt \frac{1^{p+1}}{p+1} \lt \sum_{k=1}^{1} k^p=1,$$ which is clearly true for all $p>0$.

Now suppose the statement holds for $n$; we need to prove that $$\sum_{k=1}^{n} k^p \lt \frac{(n+1)^{p+1}}{p+1} \lt \sum_{k=1}^{n+1} k^p.$$ Let us start by analyzing the sum in the lower bound: $$\sum_{k=1}^{n} k^p = n^p+ \sum_{k=1}^{n-1} k^p < \frac{(p+1)n^p}{p+1}+\frac{n^{p+1}}{p+1},$$ where the inequality between the second terms holds by the lower bound in the inductive hypothesis. Recall that by the Binomial Theorem, $(n+1)^{p+1} = n^{p+1} + (p+1)n^p + \binom{p+1}{2}n^{p-1}+\cdots + \binom{p+1}{p+1}.$ Since all terms in this sum are positive, we conclude that $$\frac{(p+1)n^p}{p+1}+\frac{n^{p+1}}{p+1} < \frac{1}{p+1}(n+1)^p.$$ Taken together with the analysis above, this completes the lower bound.

The upper bound begins similarly: $$\sum_{k=1}^{n+1} k^p = (n+1)^p+ \sum_{k=1}^{n} k^p > (n+1)^p+\frac{n^{p+1}}{p+1},$$ Again, the Binomial Theorem states that $(n+1)^p = \frac{1}{p+1}\sum_{i=0}^p (p+1)\binom{p}{i} n^{p-i}$. Recall that $(p+1)\binom{p}{i} = (i+1)\binom{p+1}{i+1}$, and so in particular

$$ (n+1)^p + \frac{n^{p+1}}{p+1} > \frac{1}{p+1}\left[(n+1)^p + \sum_{i=0}^p \binom{p+1}{i+1} n^{p-i}\right] = \frac{1}{p+1}\sum_{i=-1}^p \binom{p+1}{i+1} n^{p-i}.$$

Reindexing the last sum with $j=i+1$ and applying the Binomial Theorem gives $\frac{(n+1)^p}{p+1}$, which completes the upper bound and hence the proof.