Principle of Mathematical Induction

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.

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

Question 1. For any positive integer n, 6ⁿ −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ⁿ − 1 is divisible by 5. 

Base Case:  The statement P₁ says that,

=> 6¹ − 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ⁿ holds.

Question 2. Show that n! > 3ⁿ for n ≥ 7. 

Solution.  For any n ≥ 7, let P_n be the statement that n! > 3ⁿ . 

Base Case. The statement P₇ says that,

 7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040 > 3⁷ = 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₀ = 1, p₁ = cos θ (for θ some fixed constant) and p_n+1 = 2p₁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₀ says that,

p₀ = 1 = cos(0θ) = 1, which is true.
The statement P₁ says that p₁ = 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₁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