Mathematical Induction

Mathematical Induction

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

Example

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

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.