# Mathematical Induction

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

## Example1 + 2 + 3 + ... + n = [n(n + 1)]/2

This formula is one of the summation formula.

Sum of k

Let's prove this formula

by using mathematical induction.

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 (given) is true.

Step 2: n = k

Assume that (given) is true.

Step 3: n = k + 1

Then (given) is true.

Let's use these 3 steps.

When n = 1,

(given) is true.

(Step 1)

Then, when n = 1 + 1 = 2,

(given) is true.

(step 2, 3)

Then, when n = 2 + 1 = 3,

(given) is true.

(step 2, 3)

Then, when n = 3 + 1 = 4,

(given) is true.

(step 2, 3)

...

So, for all n,

(given) is true.

Inductive Reasoning

This is the proof of the given statement

by using mathematical induction.