# Mathematical Induction

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

## Example

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.