3

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.

Someone
  • 2,865
pinklemonade
  • 337
  • The inductive step is equivalent to $3(k+1)^2 > (k+1)^3-k^3 > 3k^2$. – Aphelli Sep 02 '19 at 16:43
  • how is that the case? – pinklemonade Sep 02 '19 at 16:45
  • My stated inequality or the logical link between it and your induction? – Aphelli Sep 02 '19 at 16:46
  • both of those things – pinklemonade Sep 02 '19 at 16:46
  • My stated inequality: expand everything and recall $k \geq 1$. The link with the induction: $1^2+\ldots+k^2=k^2+1^2+\ldots+(k-1)^2 < k^2+ \frac{k^3}{3} < \frac{(k+1)^3-k^3}{3}+\frac{k^3}{3}=\frac{(k+1)^3}{3}$ and same for the other inequality (the first $<$ is induction hypothesis, the second one is “my inequality”). – Aphelli Sep 02 '19 at 16:50
  • I suggest you start by breaking it down into two statements $P_1(k)$: $1^2 + \ldots + (k-1)^2 < k^3/3$ and $P_2(k)$: $k^3/3 < 1^2 + \ldots + k^2$ and prove each of these independently using induction (and each of these cases are more like a 'standard' induction problem). – Winther Sep 02 '19 at 16:54

3 Answers3

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

Jack D'Aurizio
  • 353,855
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$$

ArsenBerk
  • 13,211
0

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

AgentS
  • 12,195