# Mathematical Induction

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

## Example

First, show that

the given statement is true when *n* = [1].

Then 1 = 1⋅(1 + 1)/2.

See if this statement is true.

1 + 1 = 2

1⋅2/2 = 1

1 = 1

This statement is true.

So the given statement is true when *n* = [1].

Next, assume that

the given statement is true when *n* = [*k*].

Then

1 + 2 + 3 + ... = *k*(*k* + 1)/2.

Then, show that

the given statement is true when *n* = [*k* + 1].

Start from the statement when *n* = [*k*]:

1 + 2 + 3 + ... = *k*(*k* + 1)/2.

Add +[*k* + 1] to both sides.

Then the left side is

1 + 2 + 3 + ... + *k* + [*k* + 1].

And the right side is*k*(*k* + 1)/2 + [*k* + 1].

Change the right side.

[*k* + 1] = 2(*k* + 1)/2

(*k* + 1)/2 are the common factors.

So *k*⋅(*k* + 1)/2 + 2⋅(*k* + 1)/2 = (*k* + 2)⋅(*k* + 1)/2.

Switch (*k* + 2) and (*k* + 1).

(*k* + 2) = ([*k* + 1] + 1)

So (right side) = [*k* + 1]([*k* + 1] + 1)/2.

1 + 2 + 3 + ... + *k* + [*k* + 1] = [*k* + 1]([*k* + 1] + 1)/2

This shows that

the given statement is true when *n* = [*k* + 1].

The given statement is true when *n* = 1.

If the given statement is true when *n* = *k*,

then the given statement is true when *n* = *k* + 1.

So

if the given statement is true when *n* = 1,

then the given statement is true when *n* = 2.

If the given statement is true when *n* = 2,

then the given statement is true when *n* = 3.

If the given statement is true when *n* = 3,

then the given statement is true when *n* = 4.

...

So, for any *n*,

the given statement is true.

So the given statement is true.

This is the proof of the statement

by using mathematical induction.