COMP 250
INTRODUCTION TO COMPUTER SCIENCE
Week 9-1 : Induction
Giulia Alberini, Fall 2020
WHAT ARE WE GOING TO DO IN THIS VIDEO?
Inductive/Recursive definitions
Inductive/Recursive proofs Mathematical Induction
INDUCTION
PROOFS
For all 𝑛 ≥ 1,
1+2+3+ ….+ 𝑛−1 +𝑛=
𝑛 𝑛+1 2
How can we prove such a statement ?
By “proof”, we mean a formal logical argument that convincingly demonstrate the truth of a given proposition.
Note that “convincingly” is itself not well defined.
EXAMPLE
1+2+…+𝑛−1+𝑛
Rewrite by considering 𝑛/2 pairs :
1+2+⋯+𝑛+ 𝑛+1 …+ 𝑛−1 +𝑛
If 𝑛 is even, then adding up the 𝑛/2 pairs gives 𝑛/2 *(𝑛+ 1)
What if 𝑛 is odd?
22
EXAMPLE
What if 𝑛 is odd?
Then, 𝑛-1 is even. So, 1+2+…+𝑛−1+𝑛
= 𝑛−1∗𝑛 +𝑛 2
= 𝑛−1+1∗𝑛 2
= 𝑛+1∗𝑛 2
which is the same formula as before.
RECURSIVE (INDUCTIVE) DEFINITION
Some set of elements can be define recursively/inductively. A recursive/inductive definition consists of the following:
A base clause
Which one or more basic/initial element of the set.
One or more inductive clauses
Rules on how to generate “new” elements of the set from “old” ones.
A final clause
which simply states that no other element is part of the set.
EXAMPLE – NATURAL NUMBERS
The set of natural numbers can be defined as follows: Base clause:
0 is a natural number Inductive clause:
If 𝑛 is a natural number, then 𝑛 + 1 is also a natural number. Final clause: Nothing else is a natural number.
MATHEMATICAL INDUCTION
Consider a statement of the form:
“For all 𝑛 ≥ 𝑛0, 𝑃 𝑛 is true”
where 𝑛0 is some constant and proposition 𝑃(𝑛) has value true or
false for each 𝑛.
If n is an element of an inductively defined set, then the statement above can be proven using a technique called mathematical induction.
(WEAK) MATHEMATICAL INDUCTION
To prove a property by mathematical induction, we proceed as follows:
Base case
Show that the property holds for the basic/initial elements of the set.
Induction step
Assume the property hold for some element 𝑛. (Induction Hypothesis)
Show that the property also holds for any element generated from 𝑛 using the inductive clauses.
Conclusion
The property holds for all elements.
EXAMPLE
For all 𝑛 ≥ 1,
“For all 𝑛 ≥ 𝑛0, 𝑃 𝑛 is true”
𝑛 𝑛+1 2
1+2+3+ ….+ 𝑛−1 +𝑛=
This is a property of natural numbers. Since this is a set that can be defined inductively, we can use mathematical induction to prove such property!
PROOF BY MATHEMATICAL INDUCTION
We need to prove the following: Base case:
𝑃 𝑛0 is true, i.e. the property holds for 𝑛0 which in this case is 1.
Induction step:
IH: Assume 𝑃(𝑘) is true, i.e. the property holds for an element 𝑘. Prove that 𝑃 𝑘 + 1 is true, i.e. the property holds for 𝑘 + 1.
Base case:
P(𝑛0) is true.
Induction step:
For any k >= 𝑛0, if P(k) is true
then P(k+1) is true.
12 n0
Thus we have proved:
For any n >= 𝑛0,
kk+1
P(n) is true.
12 n0
kk+1
BACK TO THE PROOF
Forall𝑛≥1, 1+2+3+ ….+ 𝑛−1 +𝑛= 𝑛 𝑛+1 2
Base case: 𝑛 = 1, to prove
1=1∗ 1+1 2
1=2=1 2
Statement:Forall𝑛≥1, 1+2+3+ ….+ 𝑛−1 +𝑛= 𝑛 𝑛+1 2
BACK TO THE PROOF
Induction step:
IH: Assume that it holds for 𝑘, that is
1+2+⋯+𝑘=𝑘 𝑘+1 2
Statement:Forall𝑛≥1, 1+2+3+ ….+ 𝑛−1 +𝑛= 𝑛 𝑛+1 2
BACK TO THE PROOF
Induction step:
IH: Assume that it holds for 𝑘, that is
Prove it for 𝑘 + 1:
1+2+⋯+𝑘=𝑘 𝑘+1 2
1+2+⋯+𝑘+ 𝑘+1 = 𝑘 𝑘+1 + 𝑘 + 1 , by IH
2
= 𝑘+1 ∗ 𝑘+1 = 𝑘+1 𝑘+2 22
EXAMPLE 2
Prove the following statement:
For all 𝑛 ≥ 3, 2𝑛 + 1 < 2𝑛.
EXAMPLE 2
Statement: For all 𝑛 ≥ 3, 2𝑛 + 1 < 2𝑛.
Note: P( 𝑛 ) is false for n= 1, 2.
But that has nothing to do with what we need to prove.
EXAMPLE 2
Statement: For all 𝑛 ≥ 3, 2𝑛 + 1 < 2𝑛.
Proof: (by mathematical induction) Base case (𝑛 = 3):
2 ∗ 3 + 1 = 7 < 8 = 23
EXAMPLE 2
Induction step:
IH: Assume 2 ∗ 𝑘 + 1 < 2𝑘.
Statement: Forall𝑛≥ 3, 2𝑛+1< 2𝑛.
EXAMPLE 2
Induction step:
IH: Assume 2 ∗ 𝑘 + 1 < 2𝑘. Prove it for 𝑘 + 1:
Statement: Forall𝑛≥ 3, 2𝑛+1< 2𝑛.
2∗ 𝑘+1 +1 =2∗𝑘+2+1
EXAMPLE 2
Induction step:
IH: Assume 2 ∗ 𝑘 + 1 < 2𝑘. Prove it for 𝑘 + 1:
Statement: Forall𝑛≥ 3, 2𝑛+1< 2𝑛.
2∗ 𝑘+1 +1=2𝑘+2+1 =2∗𝑘+1+2
< 2𝑘 + 2, by IH
< 2𝑘 + 2𝑘, for 𝑘 ≥ 3 = 2𝑘+1
EXAMPLE 3
Statement: For all 𝑛 ≥ 5, 𝑛2 < 2𝑛.
EXAMPLE 3
Statement: For all 𝑛 ≥ 5, 𝑛2 < 2𝑛.
Proof: (by mathematical induction) Base case (𝑛 = 5):
52 =25<32=25
EXAMPLE 3
Statement: For all 𝑛 ≥ 5, 𝑛2 < 2𝑛. Induction step.
What should we assume? What do we need to prove?
EXAMPLE 3
Statement: For all 𝑛 ≥ 5, Induction step.
What should we assume? Whatdoweneedtoprove?
𝑛2 < 2𝑛.
𝑘2 < 2𝑘 for a 𝑘 ≥ 5 𝑘+1 2 <2𝑘+1
EXAMPLE 3
Statement: For all 𝑛 ≥ 5, 𝑛2 < 2𝑛.
Induction step.
IH:𝑘2 <2𝑘 fora𝑘≥5
𝑘 + 1 2 = 𝑘2 + 2𝑘 + 1
EXAMPLE 3
Statement: For all 𝑛 ≥ 5, 𝑛2 < 2𝑛.
Induction step.
IH:𝑘2 <2𝑘 fora𝑘≥5
𝑘 + 1 2 = 𝑘2 + 2𝑘 + 1
<2𝑘 +2𝑘+1,byIH
< 2𝑘 + 2𝑘, by Example 2 = 2𝑘+1
(STRONG) MATHEMATICAL INDUCTION
Sometimes one would like to assume the induction hypothesis not only for the previous element, but also for smaller elements. This leads to a logically equivalent proof method called strong (or complete) mathematical induction.
To prove a property by strong mathematical induction, we proceed as follows:
Induction step
Assume the property hold for all elements less than an arbitrary 𝑘. (Induction Hypothesis) Show that the property also holds for the 𝑘 element which was generated using the inductive clauses.
Conclusion
The property holds for all elements.
FIBONACCI NUMBERS
The Fibonacci sequence is one of the most common example of a recursively-defined set.
Consider the following sequence of numbers:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
Let 𝑓 denote the nth Fibonacci number. How can we define the sequence 𝑛
above?
FIBONACCI NUMBERS – INDUCTIVE DEFINITION
Fibonacci sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... Base clause:
𝑓 = 𝑓 = 1 are Fibonacci numbers. 01
Inductive clause:
If 𝑓 and 𝑓 are Fibonacci numbers, then 𝑓
number.
= 𝑓 𝑛−1
+ 𝑓 𝑛−2
is a Fibonacci
𝑛−1
𝑛−2 𝑛
EXAMPLE 4
𝑛 𝑛
Statement: For all 𝑛 ≥ 0, 𝑓 ≤
7 4
EXAMPLE 4
Statement: For all 𝑛 ≥ 0, 𝑓 ≤ Proof: (by strong mathematical induction)
Induction step
IH: Let 𝑘 be ≥ 0, and assume that for any number 𝑖 such that 0 ≤ 𝑖 < 𝑘 then
𝑖
𝑛 𝑛
𝑓≤ 𝑖
7 4
7 4
EXAMPLE 4
Statement: For all 𝑛 ≥ 0, 𝑓 ≤ Proof: (by strong mathematical induction)
Induction step
IH: Let 𝑘 be ≥ 0, and assume that for any number 𝑖 such that 0 ≤ 𝑖 < 𝑘 then
𝑛 𝑛
7 4
𝑓≤ 𝑖
7 4
𝑛
To show: 𝑓 ≤
7 4
𝑘 𝑘
EXAMPLE 4
There are 3 possible cases:
1. 𝑘=0
𝑓 = 1 and 7 0 = 1, so the claim holds.
4
𝑓 =1and 7 1 >1,sotheclaimholds.
4
0
2. 𝑘=1
1
EXAMPLE 4
There are 3 possible cases:
3. 𝑘>1
𝑓=𝑓+𝑓
𝑘 𝑘−1 𝑘−2
≤ = = < =
7 𝑘−1 + 7 𝑘−2, by IH 44
7 𝑘−2 1+7 = 7 𝑘−2 11 4444
7 4
7 4
𝑘−2 44 16
𝑘−2 49 = 7 𝑘−2 7 2 16 4 4
𝑘 4
7
RECOMMENDED EXERCISES
1. Prove that for all 𝑛 ≥ 0, σ𝑛 𝑖=0
2. Prove that for all 𝑛 ≥ 0, σ𝑛 𝑖=0
2𝑖 = 2𝑛+1 − 1
𝑖3 =
𝑛 𝑛+1
2 2
3. Consider the following recursive definition of addition ('+') on natural numbers: Base clause:
0+𝑚=𝑚
𝑛+1 +𝑚= 𝑛+𝑚 +1
Inductive clause:
Prove that addition is associative, i.e. for all natural numbers
𝑎 + 𝑏
+ 𝑐 = 𝑎 +
𝑏 + 𝑐
Hint: use mathematical induction on 𝑎
In the next videos: Recursive algorithms #1