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

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 InductionSolved Problems

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

Solution. For any n ≥ 1, let Pn be the statement that 6n − 1 is divisible by 5.

Base Case:  The statement P1 says that,

=> 61 − 1 = 6 − 1 = 5 is divisible by 5, which is true.

Inductive Step: let k ≥ 1, and suppose that Pk is true, that is, 6k − 1 is divisible by 5.

It remains to show that Pk+1 is also true, that is, 6k+1 − 1 is divisible by 5.

=> 6k+1 − 1 = 6(6k ) − 1

= 6(6k − 1) − 1 + 6

= 6(6k − 1) + 5.

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

Inductive Hypothesis: Thus by the principle of mathematical induction, for all n ≥ 1, Pn holds.

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

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

Base Case. The statement P7 says that,

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

Inductive Step:  Let k ≥ 7, suppose that Pk is true, that is, k! > 3k . It remains to show that Pk+1 is also true, that is,

(k + 1)! > 3k+1

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

> (k + 1)3k

>(7 + 1)3k

> 8 × 3k

> 3 × 3k

(k + 1)! > 3k+1

Therefore Pk+1 is true.

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

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

Solution. For any n ≥ 0, let Pn be the statement that pn = cos(nθ).

Base Cases: The statement P0 says that,

p0 = 1 = cos(0θ) = 1, which is true.
The statement P1 says that p1 = cos θ = cos(1θ), which is also true.

Inductive Step: let k ≥ 0, and suppose that both Pk and Pk+1 are true , that is, pk = cos(kθ), and pk+1 = cos((k + 1)θ).

It remains to show that Pk+2 is true, that is, that pk+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, pk+2 = 2p1pk+1 − pk

= 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 Pk+2 holds.

Inductive Hypothesis Thus by the principle of mathematical induction, for all n ≥ 1, Pn holds.

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

Scroll to Top