How to prove a statement using mathematical induction?
Proving a statement by mathematical induction is a two-step process. The first step is called the basis step, and the second step is called the inductive step. Base step is generally easy and proved for n=1 or whatever the domain restriction given for n, whereas inductive step require logical thinking and sometimes use some algebraic operations. This process is used to prove variety of statements which are formulated in terms of n, where n is a positive integer.
How many types of mathematical induction is there?
We use two types of mathematical Induction : Weak Induction and Strong induction.
Both are similar in a way that both use the base case but how you prove the inductive step is slightly different for both types. Lets observe the difference.
What is the difference between strong induction and weak induction?
Spot the difference from the point of view of asking a domino why it is falling.
Weak induction: “I’m falling because the domino before me has fallen.”
Strong induction: “I’m falling because all the dominoes before me have fallen.”
Trivially, every statement provable by weak induction is also provable by strong induction, but it is not so obvious whether the converse holds.
Example1 :Prove using mathematical induction that for all n ≥ 1,
Lets assume P(n) be the given equation.
Basis step: We need to show that P(1) is true. Which means there is only first term.
Therefore, P(1) is true.
Inductive hypothesis: For all integers k≥1, suppose P(k) is true.
Inductive step: We will show that for all integers k≥1, if P(k) is true then P(k+1) is also true.
[by substitution from the inductive hypothesis]
Next, we simplify right side.
[Make the denominators same]
[ factored out ]
Above expression can be written as a squared function.
Which is actually the right hand side of P(k+1).
Therefore, statement is proved by mathematical induction.
Example 2: Use mathematical induction to prove for all integers 𝑛 > 6.
Since n is given greater than 6, so n value used for basis step will be 7.
Lets assume P(n) be the given equation.
Basis step: We need to show that P(7) is true.
which is true.
That shows P(7) is true.
Inductive hypothesis: For all integers k > 6, suppose P(k) is true.
Inductive step: We will show that for all integers k > 6, if P(k) is true then P(k+1) is also true.
[ using inductive hypothesis ]
[ 3 will always be less than k+1 as k is greater than 6 so 3 can be replaced with k+1 ]
Which proves that p(k+1) is true.
Therefore, statement is proved by mathematical induction.
Example 3: Use mathematical induction to prove that log(n!) ≤ nlog(n) for all integers, n≥1.
As given restriction is n≥1 so the n value used for basis step will be 1.
Lets assume P(n) be the given equation.
Basis step: We need to show that p(1) is true.
log(1)≤1(0)
0 ≤ 0
This shows p(1) is true.
Inductive hypothesis:
For all integers k ≥ 1, suppose P(k) is true.
Inductive step:
Next to show that for all integers k ≥1, if P(k) is true then P(k+1) is also true.
[ from inductive hypothesis ]
Adding log(k+1) to both sides,
[ Since log(k) ≤ log(k+1), so log(k) can be replaced with log(k+1) keeping inequality true ]
Which proves that p(k+1) is true.
Therefore, statement is proved by mathematical induction.
Example 4 : Prove by mathematical induction on the positive integers ∀𝑛𝑃(𝑛) where 𝑃(𝑛) is: If 𝐴1, 𝐴2, ⋯ , 𝐴𝑛 and 𝐵 are sets, then
Lets assume P(n) be the given equation.
Basis step: We need to show that p(1) is true.
This shows P(1) is true.
Inductive hypothesis:
For all integers k ≥ 1, suppose P(k) is true.
Inductive step:
Next to show that for all integers k ≥1, if P(k) is true then P(k+1) is also true.
[ from inductive hypothesis ]
Adding k+1th term to both sides,
[ using distributive law of sets (𝑋 ∩ 𝑌) ∪ 𝑍 = (𝑋 ∪ 𝑍) ∩ (𝑌 ∪ 𝑍)]
Which proves that p(k+1) is true.
Therefore, statement is proved by mathematical induction.
Here is an example for proof by strong induction.
Example 5: Consider a proof by strong induction of ∀𝑛𝑃(𝑛) where 𝑃(𝑛) is: If 𝑛 ≥ 12, then 𝑛 cents of postage can be formed by using only 3-cent stamps and 7-cent stamps.
let P(n) : If 𝑛 ≥ 12, then 𝑛 cents of postage can be formed by using only 3-cent stamps and 7-cent stamps.
Since n ≥ 12 , so we prove that P(12), P(13),P(14), P(15) is true for basis step.
P(12) : 4(3) Four 3-cent stamps can make 12 cents of postage.
P(13) : 2(3)+1(7) Two 3-cents stamps and one 7-cent stamp can make 13 cents of postage.
P(14) : 2(7) Two 7-cents stamps can make 14 cents of postage.
P(15): 5(3) Five 3-cents stamps can make 15 cents of postage.
This proves the basis step.
Inductive hypothesis:
For all integers k ≥ 12, suppose P(k) is true.
That means any amount of postage from 12 cents to k cents can be formed by using 3-cents and 7-cents stamps.
Inductive step:
Next to show that for all integers k ≥12, if P(k) is true then P(k+1) is also true. That means if any amount of postage from 12 cents to k cents can be formed by using 3-cents and 7-cents stamps then k+1 cents of postage can also be formed by using 3-cents and 7-cents stamps.
Since P(k) is true by inductive hypothesis, P(k-2) will also be true, where 12≤k-2≤k.
That means postage of k-2 cents can be made using 3 -cents and 7-cents stamps.
P(k+1) = P(k-2 +3)
P(k+1) = P[(k-2)+3]
Which represent postage of k+1 cents of postage can be made using k-2 cents of postage and an additional 3 cent stamp.
Which proves that p(k+1) is true.
Therefore, statement is proved by strong induction.
Practice problems:
- Prove the following by principle of mathematical induction.
2. Prove using mathematical induction that for all n≥4,
3. Prove that is divisible by 7 for all n≥0.
4. Prove the following by principle of mathematical induction.