# 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.