# MandysNotes

Friday, 07 March 2014 21:08

## Mathematical Induction

By  Gideon
Rate this item

For a function $$f(n)$$ of a natural number $$n,$$ we can prove that $$f(n)$$ has the property P, for all $$n$$, if we can do two things:

•  prove that P is true for $$f(n)$$ when $$n$$ = 1;
• second: prove that if P is true for $$f(n)$$, then P is also true for $$f(n+1)$$.

This process is called mathematical induction.

Induction can also be used to define functions of a natural number $$n$$.

For example, we can define a function $$s(n)$$ by:

•  $$s(1) = 1$$;
•  $$s(n+1) = (n+1) + s(n).$$

Then:

• $$s(2) = 2 + s(1) = 2 + 1= 3$$;
•  $$s(3) = 3 + 2 + 1;$$
•  etc.

Evidently, another way to express this function is:

$s(n) = \sum_{i=i}^{n}{i}.$

Claim:

$s(n) = \sum_{i=i}^{n}{i} = \frac{(n+1)(n)}{2}$

We will prove this  claim  by induction.

Proof:

For $$n = 1$$:
$s(n) = s(1) = 1 ,$

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

$s(n) = \frac{(n+1)(n)}{2},$
then
$s(n+1) = (n+1) + \frac{(n+1)(n)}{2}.$

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

$\frac{(2n + 2) + n^{2} + n}{2}$

$= \frac{n^{2} + 3n + 2}{2}$

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