Mathematical Induction

Mathematical Induction

How to prove statemets by using mathematical induction: example and its solution.

Example

Prove the given statement. 1 + 2 + 3 + 4 + ... + n = n(n + 1)/2

Show that
'if n = 1, the given statement is true'.

Assume that
'if n = k, the given statement is true'.

So assume that
1 + 2 + 3 + ... + k = k(k + 1)/2
is true.

Show that
'if n = k + 1, the given statement is true'.

For n = k + 1,
(left side) = 1 + 2 + 3 + ... + k + (k + 1).

So add (k + 1) on both sides:
1 + 2 + 3 + ... + k + (k + 1) = k(k + 1)/2 + (k + 1).

Then change the right side
to (k + 1)[(k + 1) + 1]/2.

By showing this, you can prove that
'if n = k + 1, the given statement is true'.

This part is the most tricky part
when solving mathematical induction problems.

'If n = 1, the given statement is true' makes
'if n = 2, the given statement is true'.

'If n = 2, the given statement is true' makes
'if n = 3, the given statement is true'.

'If n = 3, the given statement is true' makes
'if n = 4, the given statement is true'.

...

By this way, for all n,
the given statement is true.

So the given statement is true.