CS计算机代考程序代写 algorithm COMP 250

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