**Principle of Mathematical Induction** is a powerful and elegant technique for proving certain types of mathematical statements. It works for general propositions which assert that something is true for all positive integers or for all positive integers from some point on.

The modern sources believed that *Giovanni Vacca* (1872 –1953) an Italian mathematician discovered the principle of mathematical induction in 1909.

Index

**Proof by Induction**

Suppose that you want to prove that some property P(n) holds for all non negative integers. To prove that using the induction principle, we follow the following steps:

**Prove that P(0) is true.**

This step is called the**basis or the base case**.**Prove that for any natural number n, if P(n) is true, then P(n + 1) is true as well.**

In this step, we assume that P(n) is true for a natural number k and then try to prove that it is true for k+1 as well.

This is called the**inductive step**.- If we prove the inductive step successfully, then by induction we can say that P(n) is true for all the non-negative integers. (Logically, as P(0) is true and from inductive step P(1) will be true and then P(2) will be true and so on.)
**P(n) is called the inductive hypothesis.**- Conclude by induction that P(n) holds for all n.

**Example on Principle of Mathematical Induction**

**Statement:** The sum of the first n positive natural numbers is n(n + 1)/2.

**Proof:** By induction, let P(n) be “the sum of the first n positive natural numbers is n(n + 1) / 2.”

Now, we need to show that P(n) is true for all natural numbers n.

**Step 1 – Base Case **

We need to show P(0) is true, meaning that the sum of the first zero positive natural numbers is 0(0 + 1)/2. Since the sum of the first zero positive natural numbers is 0 = 0(0 + 1)/2.

P(0) is true.

**Step 2 – Inductive Step**

For the inductive step, assume that for some n, P(n) holds, so 1 + 2 + … + n = n(n + 1) / 2.

We need to show that P(n + 1) holds, meaning that the sum of the first n + 1 natural numbers is (n + 1)(n + 2)/2. Consider the sum of the first n + 1 positive natural numbers. This is the sum of the first n positive natural numbers, plus n + 1. By the inductive hypothesis, this is given by,

1+…+n+(n+1)= n(n+1)/2 +n+1= [n(n+1)+2(n+1)]/ 2 = (n+1)(n+2)/2

**Step 3 – Inductive Hypothesis**

Thus P(n + 1) holds when P(n) is true, so P(n) is true for all natural numbers n.

**Structure Of Proof**

- State that you are attempting to prove something by induction.
- State what your choice of P(n) is.
- Prove the base case:
- State what P(0) is, then prove it.
- Prove the inductive step.
- State that you’re assuming P(n) and what P(n) is.
- State what P(n + 1) is. (this is what you’re trying to prove)
- Go prove P(n + 1)
- This is very rigorous, so as we gain more familiarity with the induction we will start being less formal in our proofs.

**Principle of Mathematical Induction** **Solved Problems**

**Principle of Mathematical Induction**

**Question 1.** For any positive integer n, 6^{n} −1 is divisible by 5. Verify the statement using principle of induction.

**Solution**. For any n ≥ 1, let P_{n} be the statement that 6^{n} − 1 is divisible by 5.

**Base Case:** The statement P_{1} says that,

=> 6^{1} − 1 = 6 − 1 = 5 is divisible by 5, which is true.

**Inductive Step**: let k ≥ 1, and suppose that P_{k} is true, that is, 6^{k} − 1 is divisible by 5.

It remains to show that P_{k+1} is also true, that is, 6^{k+1} − 1 is divisible by 5.

=> 6^{k+1} − 1 = 6(6^{k} ) − 1

= 6(6^{k} − 1) − 1 + 6

= 6(6^{k} − 1) + 5.

By P^{k}, the first term 6(6^{k} − 1) is divisible by 5, the second term is clearly divisible by 5. Therefore the left hand side is also divisible by 5. Therefore P^{k}+1 holds.

**Inductive Hypothesis**: Thus by the principle of mathematical induction, for all n ≥ 1, P^{n} holds.

**Question 2.** Show that n! > 3^{n} for n ≥ 7.

**Solution. ** For any n ≥ 7, let P_{n} be the statement that n! > 3^{n} .

**Base Case.** The statement P_{7} says that,

7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040 > 3^{7} = 2187, which is true.

**Inductive Step**: Let k ≥ 7, suppose that P_{k} is true, that is, k! > 3^{k} . It remains to show that P_{k+1} is also true, that is,

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

(k + 1)! = (k + 1)k!

> (k + 1)3^{k}

>(7 + 1)3^{k}

> 8 × 3^{k}

> 3 × 3^{k}

(k + 1)! > 3^{k+1} .

Therefore P_{k+1} is true.

**Inductive Hypothesis: **Thus by the principle of mathematical induction, for all n ≥ 1, P_{n} holds

**Question 3.** Let p_{0} = 1, p_{1} = cos θ (for θ some fixed constant) and p_{n+1} = 2p_{1}p_{n} − p_{n}−1 for n ≥ 1. Use an extended Principle of Mathematical Induction to prove that p_{n} = cos(nθ) for n ≥ 0.

**Solution**. For any n ≥ 0, let P_{n} be the statement that p_{n} = cos(nθ).

**Base Cases**: The statement P_{0} says that,

p_{0} = 1 = cos(0θ) = 1, which is true.

The statement P_{1} says that p_{1} = cos θ = cos(1θ), which is also true.

**Inductive Step:** let k ≥ 0, and suppose that both P_{k} and P_{k+1} are true , that is, p_{k} = cos(kθ), and p_{k+1} = cos((k + 1)θ).

It remains to show that P_{k+2} is true, that is, that p_{k+2} = cos((k + 2)θ).

We have the following identities:

cos(a + b) = cos a cos b − sin a sin b c

cos(a − b) = cos a cos b + sin a sin b

Therefore, using the first identity when a = θ and b = (k + 1)θ, we have

cos(θ + (k + 1)θ) = cos θ cos(k + 1)θ − sin θ sin(k + 1)θ,

cos θ cos(k + 1)θ = sin θ sin(k + 1)θ + cos(θ + (k + 1)θ) ————(1)

and, using the second identity when a = (k + 1)θ and b = θ, we have

cos((k + 1)θ − θ) = cos(k + 1)θ cos θ + sin(k + 1)θ sin θ.

cos(k + 1)θ cos θ = cos((k + 1)θ − θ) + sin(k + 1)θ sin θ. ———(2)

Therefore, p_{k+2} = 2p_{1}p_{k+1} − p_{k}

= 2(cos θ)(cos((k + 1)θ)) − cos(kθ)

= (cos θ)(cos((k + 1)θ)) + (cos θ)(cos((k + 1)θ)) − cos(kθ)

From (1)

= cos(θ + (k + 1)θ) + sin θ sin(k + 1)θ + (cos θ)(cos((k + 1)θ)) − cos(kθ)

= cos((k + 2)θ) + sin θ sin(k + 1)θ + (cos θ)(cos((k + 1)θ)) − cos(kθ)

From(2)

= cos((k + 2)θ) + sin θ sin(k + 1)θ + cos((k + 1)θ − θ) − sin(k + 1)θ sin θ − cos(kθ)

= cos((k + 2)θ) + cos(kθ) − cos(kθ)

= cos((k + 2)θ).

Therefore P_{k+2} holds.

** Inductive Hypothesis: ** Thus by the principle of mathematical induction, for all n ≥ 1, P

_{n}holds.

More => **Proof Of Binomial Theorem By Mathematical Induction**

**FAQs**

**What is the first principle of mathematical induction?**The principle of mathematical induction is then: If the integer 0 belongs to the class C and C is hereditary,then we say that every nonnegative integer belongs to C.

Alternatively, if the integer 1 belongs to the class C and C is hereditary, then we say that every positive integer belongs to C.

**Who created mathematical induction?**Giovanni Vacca (1872 –1953) an Italian mathematician discovered the principle of mathematical induction (1909).

**What are the limitations of mathematical induction?**One of the major limitations of mathematical Induction is that it is limited to items quantifiable in the set of numbers; can’t go beyond quantifiable sets.