# Mathematical Induction: Principle & Examples

Mathematical induction describe as a domino cards or climbing a ladder. In domino cards, if the first card falls, then the second falls too and so does the third, fourth and finally all of cards fall.

Climbing a ladder is like domino cards. If the first step is passed, then going to second step, third step and finally all of step ladder is passed.

## Principle of mathematical induction

Mathematical induction is one of proof technique in mathematics. If a statement is true based on mathematical induction, it means that it is also true for all of natural numbers.

Mathematical statement that can be proved by using mathematical induction is like a sequence statement P(n) for natural numbers (n=1,2,3,…) of infinitely P(1), P(2), P(3), ….

Principle of using mathematical induction consists of two steps. There are base and induction step.

1. Base step (it is also called basis step) prove statement that n = 0 (or based on the problem’s condition) is true.  It is also often use n = 1.

If the problem said that n = a, so the base step is n = b that b>a (a and b is natural numbers). Proving the statement must be independent, it is not depends on other condition or other problems.

2. Induction step proves that for every n natural numbers, if given n=k is true then n=k+1 is also true for the problems.

After all of steps are true then the statement of the problem is true.

Based on the principle, there are simple steps that will make it easily.

1. Prove that n=1 is true for the problem.
2. Assume that n=k is true then proves n=k+1. Be careful doing this second step, it needs your trick and your logic.

## Mathematical induction examples

Generally, there are three types of mathematical induction problems.

### A. Sum of consecutive natural numbers

Example:

1. Prove that 1 + 3 + 5 + … + (2n-1) = n2 for n is positive integer.

Use the steps.

• Prove n = 1

2n-1 = n2

(2(1) – 1) = 12

1 = 1 (true)

• Assume that n = k is true

1 + 3 + 5 + … + (2n-1) = n2

1 + 3 + 5 + … + (2k-1) = k2(assume it is true)

Prove that n = k+1

1 + 3 + 5 + … + (2k-1) + (2 (k+1)-1) = (k+1)2

k2 + 2k + 1 = (k+1)2 (because of the assumption)

(k+1)2 = (k+1)2 (true)

Because of all steps are true, then the 1 + 3 + 5 + … + (2n-1) = n2 for n is positive integer is true.

2. Prove the mathematical induction!

Sum of consecutive natural numbers

12 + 22 + 32 + 42 + … + n2 = {n(n+1) (2n+1)} / 6 for all n is positive integer.

1)Prove n = 1

12 = {1(1+1) (2(1)+1)} / 6
1 = 1 (true)

2)Assume that n = k is true

12 + 22 + 32 + 42 + … + k2 = {k(k+1) (2k+1)} / 6 (assume that it is true)

Prove that n = k+1

12 + 22 + 32 + 42 + … + k2 + (k+1)2 = {(k+1)(k+1+1)(2(k+1)+1)} / 6
[{k(k+1) (2k+1)} / 6]+ k2 + 2k + 1 = {(k+1)(k+1+1)(2(k+1)+1)} / 6
{2k3 + k2 + 2k2 + k + 6k2 + 12k + 6} / 6 = {(k+1)(k+1+1)(2(k+1)+1)} / 6
{2k3 + 9k2 + 13k + 6} / 6 = {(k+1)(k+1+1)(2(k+1)+1)} / 6 *
{(k+1)(2×2+7x+6)} / 6 = {(k+1)(k+1+1)(2(k+1)+1)} / 6
{(k+1)(k+2)(2k+3)} / 6 = {(k+1)(k+1+1)(2(k+1)+1)} / 6
{(k+1)(k+2)(2k+2+1)} / 6 = {(k+1)(k+1+1)(2(k+1)+1)} / 6
{(k+1)(k+1+1)(2(k+1)+1)} / 6 = {(k+1)(k+1+1)(2(k+1)+1)} / 6 **

Note: from * to ** you can use Horner to make it easily.

Because of all steps are true, then the 12 + 22 + 32 + 42 + … + k2 = {k(k+1) (2k+1)} / 6 for n is positive integer is true.

### B. Division

1. Prove that 52n+3n-1 can be divided by 9.

Use the steps.

• Prove n = 1

52n+3n-1 = 52(1)+3(1)-1

=25+3-1

=27 (it is true that it can be divided by 9)

• Assume that n = k is true

52k+3k-1 is true can be divided by 9 or can be written to be 9a.

Prove that n = k+1

52(k+1) + 3(k+1) – 1 = 52k.52+ 3k + 3 – 1

= 25. 52k + 3k + 3 – 1

= 25. (52k +3k-1) – 75k + 25 + 3k + 3 – 1

(trick: 52k is replaced by 52k +3k-1, but we need – 75k + 25 to defend the value)

= 25.9a – 72k + 27 (using the assumption)

= 25a.9 – 9.8k + 9.3

= 9 (25a – 8k + 3) it is true that it can be divided by 9

Because of all steps are true, it is true that 52n+3n-1 can be divided by 9.

2. Prove that n3 + 2n can be divided by 3.

Use the steps.

1) Prove n = 1

n3 + 2 = 13 +2.1
= 3 (it is true that it can be divided by 3)

2) Assume that n = k is true

k3 + 2k is true can be divided by 3 or can be written to be 3a.

Prove that n = k+1

(k+1)3 + 2(k+1) = k3 + 3k2 + 3k + 1 + 2k + 2
= k3 + 3k2 + 5k + 3
= k3 + 2k + 3k2 + 3k + 3
= k3 + 2k + 3(k2+ k + 1)
= 3a + 3(k2+ k + 1)
= 3 (a + k2+ k + 1)

Note : 5k = 2k + 3k

Because of all steps are true, it is true that n3 + 2n can be divided by 3.

### C. Multiple

1. Prove that 3n-1 is multiple of 2 for n = 1, 2, …

• Prove n = 1

3n – 1 = 31 – 1 = 2 (true that it is multiple of 2)

• Assume that n = k is true

3k – 1 is true that it is multiply of 2 or we can write it as 3k – 1 = 2a.

Prove n = k+1

3(k+1) – 1 = 31. 3k – 1

= 3.3k – 1

= 2.3k + 3k – 1

= 2. 3k + (3k – 1)

=2. 3k + 2a

=2 (3k+a) it is true that it is multiple of 2.

Because of all steps are true, it is true that 3n-1 is multiple of 2 for n = 1, 2, …

2. Prove that 5n+1 – 4n – 5 is multiple of 16 for n = 1, 2, …

1) Prove n = 1

51+1 – 4(1) – 5 = 25 – 4 – 5 = 16 (true)

2) Assume that n = k is true

5k+1 – 4k – 5 is true that it is multiply of 16 or we can write it as 16a.

Prove n = k+1

5k+1+1 – 4(k+1) – 5 = 5k+2 – 4k – 4 – 5
= 5k+2 – 4k – 4 – 5
= 5(5k+1 – 4k – 5) – 4 +16k +20 (trick to get 16a)
= 5(16a) + 16k + 16
= 16(5a + k + 1)

It is true that 5n+1 – 4n – 5 is multiple of 16 for n = 1, 2, …

### D. Inequality

1) Prove that 4n < 2n for n>5.

• Prove that n=6 is true (because of there is requisite that n>5)

4.6 < 26

24 < 64 (it is true)

•  Assumed that n=k is true

4k < 2k is true

Prove n = k+1

Prove that 4(k+1) < 2(k+1)

4(k+1) = 4k + 4)

Because of 4<4k, then

< 4k + 4k

< 2 (4k)

< 2 (2k)  (based on assumption)

< 2(k+1) it is true that 4(k+1) < 2(k+1)

Because of all steps are true, it is true that 4n < 2n for n>5.

2. Prove that n! > 2n for n>3.

1) Prove that n = 4 is true (because of there is requisite that n>3)

4! > 24
24 > 8 (true)

2) Assumed that n=k is true

k! > 2k is true

Prove n = k+1

(k+1)! > 2(k+1)

Because of (k+1)! = (k+1).k!

And 2(k+1) = 2k.2

We know that k! > 2k is true and k+1 > 2 then it is true that n! > 2n for n>3