Prove or Disprove Inequality By Induction

Question

Prove or Disprove

$\sum_{i=0}^n(2i)^3 \le (8n)^3 $

If true, prove using induction. If false, give the smallest value of n that is a counter example and the values for the left and right hand sides of the equation.

I started out with the Base Case at n = 1:

$\sum_{i=0}^1(2i)^3 = 8, 8^3 = 512 $

$8 \le 512 \therefore $ true

Induction Hypothesis: Assume $\sum_{i=0}^k(2i)^3 \le (8n)^3 $ is true

Induction: $\sum_{i=0}^{k+1} (2i)^3 \le (8(k+1))^3 $

$\sum_{i=0}^{k+1} (2i)^3 = \sum_{i=0}^k(2i)^3 + (2(k+1))^3 $

This is where I'm stuck in the problem right now. I'm not sure how to use the hypothesis when it's an inequality.

Answer 1

$1.$ It is not true that the inequality holds for all $n$.

$2.$ To solve the problem, use the fact that $$1^3+2^3+\cdot+n^3=\frac{n^2(n+1)^2}{4}.\tag{1} $$ The identity (1) can be proved by induction.

Answer 2

As a very rough, not-at-all rigorous general rule of thumb, it turns out that if $f(n)$ is monotonically increasing, then: $$ \sum_{i=1}^n f(i) = \Theta\left( \int f(n) \right) $$ Thus, since the LHS is roughly $\sum i^3 \approx n^4$ while the RHS is roughly $n^3$, the inequality should be false for large enough $n$. Indeed, the inequality holds if $n = 253$ but fails when $n = 254$.

Answer 3

Indeed the inequality does not hold for all $n$. We have: $$\sum_{i=0}^n(2i)^3 \leq (8n)^3,$$ which is the same as: $$\sum_{i=0}^n i^3 \leq 64n^3.$$ Using the relation given by @AndréNicolas (which for a complete proof should be proven as well), we get: $$\frac{n^2(n+1)^2}{4}\leq64n^3 \quad\iff\quad n^2(n^2-254n+2)\leq0.$$ Using the quadratic formula it is easy to find that this inequality holds for $n\leq253$, but not for $n\geq254.$