How to use induction to show the lower bound of this function?

Question

This is a question from lecture notes, but we did not have enough time to cover it in class. It is asked to show that $$\sum_{k=1}^n k^5 = \Omega(n^6)$$ using mathematical induction.

Note: $\Omega(g(n))$ is the lower bound for $f(x)$, which defined as there exist positive constants $c$ and $n_0$ such that $0 \leq c \cdot g(n) \leq f(n) \ \text{for all} \ n \geq n_0 $.

Answer 1

Suppose that we have the induction hypothesis

$$\sum_{k=1}^nk^5\ge cn^6\;.\tag{1}$$

We want to choose $c>0$ so that this ensures that

$$\sum_{k=1}^{n+1}k^5\ge c(n+1)^6\;.$$

Now

$$\sum_{k=1}^{n+1}k^5=(n+1)^5+\sum_{k=1}^nk^5\ge(n+1)^5+cn^6$$

by the induction hypothesis $(1)$, so we want to choose $c$ so that

$$(n+1)^5+cn^6\ge c(n+1)^6\;.$$

It’s convenient to divide through by $c$ (which we can do because $c>0$ and rewrite this as

$$(n+1)^6\le n^6+\frac1c(n+1)^5\;.$$

Expanding the lefthand side and simplifying yields

$$6n^5+15n^4+20n^3+15n^2+6n+1\le\frac1c(n+1)^5$$

or, finally,

$$c\le\frac{n^5+5n^4+10n^3+10n^2+5n+1}{6n^5+15n^4+20n^3+15n^2+6n+1}\;.\tag{2}$$

The question, then, is how to choose $c>0$ so that $(2)$ is true for every $n$ from some point on.

HINT:

$$\frac{n^5+5n^4+10n^3+10n^2+5n+1}{6n^5+15n^4+20n^3+15n^2+6n+1}\ge\frac{n^5}{63n^5}$$

for all $n\ge 1$; why?

---

If you’re feeling ambitious, you can try showing that

$$\frac{n^5+5n^4+10n^3+10n^2+5n+1}{6n^5+15n^4+20n^3+15n^2+6n+1}\ge\frac{n^5}{10n^5}$$

for all $n\ge 15$; then you can use $c=\frac1{10}$ and $n_0=15$.

Answer 2

Can you use induction to prove that $$\sum_{k=1}^n k^5 \geq \frac{n^6}{6}$$

Answer 3

Here's a hint for the induction step: notice that $$(n+1)^6 = n^6 + 6n^5 + 15n^4 + 20n^3 + 15n^2 + 6n + 1$$ And, for $n \ge 1$, $n^5 \ge n^k$ for $k \le 5$, so $$(n+1)^6 \le n^6 + 63n^5.$$

Using this, you should be able to prove the result you want with $c = \frac{1}{63}$.

---

Michael Biro suggests in his answer that you should be able to use $c = \frac{1}{6}$. It is certainly true that this value of $c$ works. Indeed, since $x \mapsto x^5$ is monotone increasing, $$\frac{1}{6}n^6 = \int_0^n x^5\;dx \le \sum_{k=1}^n k^5.$$

However, I don't see a straightforward way to use induction to prove $c=\frac{1}{6}$ works.