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.

Table of Contents

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

- Prove that n=1 is true for the problem.
- 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) = n^{2} for n is positive integer.

Use the steps.

- Prove n = 1

2n-1 = n^{2}

(2(1) – 1) = 1^{2}^{}

1 = 1 (true)

- Assume that n = k is true

1 + 3 + 5 + … + (2n-1) = n^{2}^{}

1 + 3 + 5 + … + (2k-1) = k^{2}(assume it is true)

Prove that n = k+1

1 + 3 + 5 + … + (2k-1) + (2 (k+1)-1) = (k+1)^{2}^{}

k^{2} + 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 5^{2n}+3n-1 can be divided by 9.

Use the steps.

- Prove n = 1

5^{2n}+3n-1 = 5^{2(1)}+3(1)-1

=25+3-1

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

- Assume that n = k is true

5^{2k}+3k-1 is true can be divided by 9 or can be written to be 9a.

Prove that n = k+1

5^{2(k+1) }+ 3(k+1) – 1 = 5^{2k}.5^{2}+ 3k + 3 – 1

= 25. 5^{2k} + 3k + 3 – 1

= 25. (5^{2k} +3k-1) – 75k + 25 + 3k + 3 – 1

(trick: 5^{2k} is replaced by 5^{2k} +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 5^{2n}+3n-1 can be divided by 9.

2. Prove that n^{3 }+ 2n can be divided by 3.

Use the steps.

1) Prove n = 1

n^{3 }+ 2 = 1^{3} +2.1

= 3 (it is true that it can be divided by 3)

2) Assume that n = k is true

k^{3 }+ 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) = k^{3} + 3k^{2} + 3k + 1 + 2k + 2

= k^{3} + 3k^{2} + 5k + 3

= k^{3} + 2k + 3k^{2} + 3k + 3

= k^{3} + 2k + 3(k^{2}+ k + 1)

= 3a + 3(k^{2}+ k + 1)

= 3 (a + k^{2}+ k + 1)

Note : 5k = 2k + 3k

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

### C. Multiple

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

- Prove n = 1

3^{n }– 1 = 3^{1 }– 1 = 2 (true that it is multiple of 2)

- Assume that n = k is true

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

Prove n = k+1

3(k+1) – 1 = 3^{1}. 3^{k} – 1

= 3.3^{k} – 1

= 2.3^{k} + 3^{k} – 1

= 2. 3^{k} + (3^{k} – 1)

=2. 3^{k} + 2a

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

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

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

1) Prove n = 1

5^{1+1} – 4(1) – 5 = 25 – 4 – 5 = 16 (true)

2) Assume that n = k is true

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

Prove n = k+1

5^{k+1+1} – 4(k+1) – 5 = 5^{k+2} – 4k – 4 – 5

= 5^{k+2} – 4k – 4 – 5

= 5(5^{k+1} – 4k – 5) – 4 +16k +20 (trick to get 16a)

= 5(16a) + 16k + 16

= 16(5a + k + 1)

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

### D. Inequality

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

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

4.6 < 2^{6}^{}

24 < 64 (it is true)

- Assumed that n=k is true

4k < 2^{k }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 (2^{k}) ^{ }(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 < 2^{n} for n>5.

2. Prove that n! > 2^{n} for n>3.

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

4! > 2^{4}

24 > 8 (true)

2) Assumed that n=k is true

k! > 2^{k }is true

Prove n = k+1

(k+1)! > 2^{(k+1)}^{}

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

And 2^{(k+1)} = 2^{k}.2

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