Prove that $1^2 + 2^2 + {...}+ {(n - 1)}^2 < \frac{n^3}{3} < 1^2 + 2^2 + {...}+ {n}^2 $

Question

Prove that $1^2 + 2^2 + {...}+ {(n - 1)}^2 < \frac{n^3}{3} < 1^2 + 2^2 + {...}+ {n}^2 $

---

I know I need to use induction for this proof, but it feels like a pretty complicated one.

Basis: For $n = 2$,

$$1^2 < \frac{8}3 < 1^2 + 2^2$$

Induction Hypothesis: Assume $P(n)$ holds for $n=k$, that is,

$$1^2 + 2^2 + {...}+ {(k - 1)}^2 < \frac{k^3}{3} < 1^2 + 2^2 + {...}+ {k}^2$$

We need to show that $P(n)$ also holds for $n=k+1$

Proof:

$$1^2+2^2+{...}+{(k)}^2=1^2+2^2+{...}+{(k-1)}^2+{k}^2$$

After this, I'm not sure how to use the assumed inequality to prove it because it's a less than inequality. If I could get a hint that'd be awesome.

Answer 1

HINT: Since we know that $1^2 + 2^2 + {...}+ {(k - 1)}^2 < \frac{k^3}{3} < 1^2 + 2^2 + {...}+ {k}^2$ by induction hypothesis, what we need to prove is that

$$k^2 \le \frac{3k^2+3k+1}{3} \le (k+1)^2$$

Answer 2

Since $x^2$ is an increasing function on $[0,1]$ we have that $\frac{1}{3}=\int_{0}^{1}x^2\,dx$ can be bounded by two Riemann sums:

$$ \frac{1}{n}\sum_{k=0}^{n-1}\left(\frac{k}{n}\right)^2 < \int_{0}^{1}x^2\,dx < \frac{1}{n}\sum_{k=1}^{n}\left(\frac{k}{n}\right)^2 $$ i.e. the lower/upper Riemann sums associated to the partition of $[0,1]$ into $n$ congruent sub-intervals.
By multiplying each term by $n^3$ the claim is readily proved.

---

Through induction we just have to prove that $\frac{1}{3}\left[(n+1)^3-n^3\right]$ is bounded between $n^2$ and $(n+1)^2$, i.e. $ n^2<n^2+n+1<n^2+2n+1 $, which is also pretty straightforward.

---

Yet another way: $\sum_{m=0}^{M}m^2$ can be computed through the hockey stick identity.
We have $m^2=2\binom{m}{2}+\binom{m}{1}$, hence $$ \sum_{m=0}^{M}m^2=2\sum_{m=0}^{M}\binom{m}{2}+\sum_{m=0}^{M}\binom{m}{1} =2\binom{M+1}{3}+\binom{M+1}{2}=\frac{M(M+1)(2M+1)}{6}$$ and the claim is equivalent to $$ M(M-1)(2M-1) < 2M^3 < M(M+1)(2M+1). $$

Answer 3

If you're allowed to use $\sum\limits_{k=1}^{n} k^2 =\frac{n(n+1)(2n+1)}{6} $, $$1^2 + 2^2 + {…}+ {(n - 1)}^2 < \frac{n^3}{3} < 1^2 + 2^2 + {…}+ {n}^2$$

because

$\dfrac{(n-1)n(n-\frac{1}{2})}{3} \lt \dfrac{n^3}{3}$
and
$\dfrac{n(n+1)(n+\frac{1}{2})}{3} \gt \dfrac{n^3}{3}$