3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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.$

$\endgroup$
1
$\begingroup$

$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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.