Induction

Mathematical Induction

Hi readers, I guess this post goes under algebra. Today, we will be introducing a new method and in case you haven't read the title, it's the INDUCTION METHOD!!! Mathematical induction is a powerful method to prove some mathematical statement for all natural numbers (positive integers). Consider this: Show that

$\displaystyle{0+1+2+\cdots +n=\frac{n(n+1)}{2}}$

for every natural n.

Now we are going to use mathematical induction to prove this.

Induction has just 2 steps:

1. Basic/Base Step: Show that the statement holds for n = 1
2. Inductive step: Show that the statement holds for n = n + 1
Basically its showing that it works for the first natural number (1) and every subsequent natural number (k+1).

So, we will first prove the basic step, which is n=1. Obviously, when you substitute 1 in the equation, the statement holds. To show that this holds for every natural number n, we use n=n+1. We get the equation

$\displaystyle{0+1+2+\cdots + n+n+1 = \frac{(n+1)(n+2)}{2}}$

$\displaystyle{\frac{n(n+1)}{2}+(n+1)=\frac{(n+1)(n+2)}{2}}$

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

So this proves that the equation hold for n=n+1, and every subsequent value of n.