# Mathematical Induction

How to prove the given statement by using mathematical induction: 1 example and its solution.

## Example

### Example

This formula is one of the summation formula.

Sum of k

Let's prove this formula
by using mathematical induction.

### Solution

To prove a statment
by using mathematical induction,
show the below 3 steps.

Step 1: n = 1

Show that the given statement is true
when n = 1.

The left side is 1.

The right side is [1(1 + 1)]/2.

Show that the right side
is equal to the left side: 1.

1 + 1 = 2

1⋅2/2 = 1

The left side, 1,
is equal to
the right side, 1.

So the given statment is true
when n = 1.

Step 2: n = k

Assume that the given statement is true
when n = k.

Then assume that
1 + 2 + 3 + ... + k = [k(k + 1)]/2
is true.

Step 3: n = k + 1

Show that the given statment is true
when n = k + 1.

Use the previous equation
1 + 2 + 3 + ... + k = [k(k + 1)]/2.

To make the case when n = k + 1,
add [k + 1] on both sides.
1 + 2 + 3 + ... + k + [k + 1] = [k(k + 1)]/2 + [k + 1]

The goal is to change the right side,
[k(k + 1)]/2 + [k + 1],
to make the right side of the given statement
when n = k + 1:
[(k + 1)(k + 2)]/2.

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

The common factor of [k(k + 1)]/2 and +[2(k + 1)]/2 is
(k + 1)/2.

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

Common Monomial Factor

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

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

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

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

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

See the three steps you've wrote.

Step 1: n = 1
The given statement is true.

Step 2: n = k
Assume that the given statement is true
when n = k.

Step 3: n = k + 1
Then the given statement is true
when n = k + 1.

The given statement is true
when n = 1.
(Step 1)

If the given statement is true
when n = 1,
then the given statement is true
when n = 2.
(step 2, 3)

If the given statement is true
when n = 2,
then the given statement is true
when n = 3.
(step 2, 3)

If the given statement is true
when n = 3,
then the given statement is true
when n = 4.
(step 2, 3)
...

So, for all n,
the given statement is true.

Inductive Reasoning

This is the proof of the given statement
by using mathematical induction.