Mathematical Induction

Mathematical Induction is a good way to start writing proof for beginner too. Mathematical Induction is usually read by students at post-secondary level(Diploma/A-level). Problem is, equations are given to you and you just have to prove $$ (k+1)$$ is true. As a real problem solver, you should explore more and able to create without memorizing!

Example: $$ 1 + 2 + 3 .... + n = \frac{n(n+1)}{2}$$
Before we prove (k+1) .. lets find out why $$\frac{n(n+1)}{2}$$.

If you add the very last number to the first, then move the 2nd last to the 2nd and so on, the result will be ...

Sum them up:
$$\small (n+1) + ((n-1)+2) + ((n-1)+3) .... + ((n-m+1)+m)$$
Result : $$\small \underbrace {(n+1) + (n+1) + (n+1) ...... + (n+1)}_\textrm{n times. so = n(n+1)}$$

Since 2 integers being sum together, we divide them by 2 so, $$\frac{n(n+1)}{2}$$ created. Now you can prove (k+1) for $$\sum_{i=1}^{n}i=\frac{n(n+1)}{2}$$
Now you can prove for (k+1) easily.

Another Example: Let's explore further for $$1^{2} + 2^{2} + 3^{2} + ...... n=?$$. Lets say you can't remember. Time to think creatively and do real math.

Lets see ..

$$ \underbrace{\underbrace{1^2 + 2^2}_\textrm{5} + 3^2}_\textrm{14} ... + n^{2}=5, 14, 30, 55, 91, .... $$

$$ \underbrace{\underbrace{1 + 2}_\textrm{3} + 3}_\textrm{6} ....... + n=3, 6, 10, 15, 21 .... $$

Divide them $$\frac{1^2 + 2^2 + 3^2 ... n^2}{1 + 2 + 3 ....... n}=\frac{5, 14, 30, 55, 91 ...}{3, 6, 10, 15, 21 ...}$$

Finally, divide the denominator and numerator $$=\frac{ 3 \, 5 \, 7 \, 9 \, 11 \, 13}{ 3 \, 3 \, 3 \, 3 \, 3 \, 3}$$

Can you see the above number pattern? the numerator are odd integers while denominator are constant 3. Therefore,
$$ \frac{1^2 + 2^2 + 3^2 ... + n^2}{1 + 2 + 3 ....... + n} = \frac{2n+1}{3}$$

$$\frac{1^2 + 2^2 + 3^2 ... + n^2}{\frac{n(n+1)}{2}}=\frac{2n+1}{3}$$

$$1^2 + 2^2 + 3^2 ... + n^2=\frac{n(n+1)(2n+1)}{6}$$ created!

Now you can prove (k+1) for $$\sum_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6}$$