Friday 31 March 2017

discrete mathematics - What's the shortest way to prove $sum_{t=1}^n t^2=frac{n(n+1)(2n+1)}6$ by a mathematical induction?




Is there a quick way to prove the following? The method I used seems bit too long and lengthy, which I'd rather not post here.



enter image description here



$$\sum_{t=1}^n t^2=1^2+2^2+3^2+\dots+t^2=\frac{n(n+1)(2n+1)}6$$


Answer



I assume the equation is meant to be $\sum_{t=1}^{n}t^2 = 1^2 + 2^2 + \dots + \color{red}{n}^2$ instead of $\sum_{t=1}^{n}t^2 = 1^2 + 2^2 + \dots + \color{red}{t}^2$.



The equation holds for $n=1$ because

$$\sum_{t=1}^{1} = 1^2 = 1$$
and
$$\frac{1(1+1)(2\times 1+1)}{6} = 1$$
so
$$\sum_{t=1}^{1} = \frac{1(1+1)(2\times 1+1)}{6}$$



Now if the equation holds for $n = k$ where $k \in \mathbb{N}_{\ge 1}$, then
$$\sum_{t=1}^{k} = 1^2 + 2^2 + \dots + k^2 = \frac{k(k+1)(2k+1)}{6} = \frac{2k^3 + 3k^2 + k}{6}$$
and hence
$$\sum_{t=1}^{k+1} = 1^2 + 2^2 + \dots + k^2 + (k+1)^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2 = \frac{2k^3 + 3k^2 + k}{6} + (k^2 + 2k +1) = \frac{2k^3 + 3k^2 + k}{6} + \frac{6k^2 + 12k+6}{6} = \frac{2k^3+9k^2+13k+6}{6}$$




Also
$$\frac{[k+1]([k+1]+1)(2[k+1]+1)}{6} = \frac{(k+1)(k+2)(2k+3)}{6} = \frac{2k^3+9k^2+13k+6}{6}$$
so
$$\sum_{t=1}^{k+1}t^2 = \frac{[k+1]([k+1]+1)(2[k+1]+1)}{6}$$
and thus the equation holds for $n=k+1$.



Therefore by induction
$$\sum_{t=1}^{n}t^2 = 1^2 + 2^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}$$




As a straightforward induction proof, it cannot get any shorter.



Hope it helps. :)


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...