Transcript Introduction to Induction

snick

snack
CPSC 121: Models of Computation
2009 Winter Term 1
Introduction to Induction
Steve Wolfman
1
Outline
• Prereqs, Learning Goals, and Quiz Notes
• Problems and Discussion
– Single-Elimination Tournaments
– Binary Trees
• A First Pattern for Induction
• Induction on Numbers
• Next Lecture Notes
2
Quiz Notes
You’re faced with a problem like “How many teams can
play in a 100 round tournament?” or “How many teams
can play in an n-round tournament?”
You don’t know the answer.
What can you do?
Strategies:
• Try to clearly define terms (What’s a tournament?
What’s a round?)
• Try a smaller number. 100 is hard, what about 1 or 2?
• Write the problem (or a small version) out as a story
and figure out which parts of the story matter.
3
Quiz Notes:
Summations/Products
All of these were tricky. It’s worth practicing
with them since they come up in induction
proofs.
n
k 1
For example, let’s play with 
k 2
k 1
4
Quiz Notes:
Summations/Products
All of these were tricky. It’s worth practicing
with them since they come up in induction
proofs.
First, let’s change the bounds. We can do
that by “shifting” k over.
Instead of “k”, use “k+1” and decrease the
bounds by 1, and the formula stays the
n
same:
k  1 n 1 (k  1)  1 n 1 k  2
 k  1   (k  1)  1  
k 2
k 1
k 1
k
5
Quiz Notes:
Summations/Products
All of these were tricky. It’s worth practicing
with them since they come up in induction
proofs.
Now, let’s split the sum. First, break up the
fraction, then just tease apart the two
addends:
k 1 n k
1
 n k   n 1 


 
  


k  1  k 2 k  1   k 2 k  1 
k 2 k  1
k 2 k  1
n
Now, look at the first quiz problem again.
Which responses are correct?
6
Quiz Notes:
Summations/Products
Or, the easier way. Try a (small) value for n.
For example, with n=3, are these two
equal?
k 1 ? n k  2


k
k 2 k  1
k 1
n
If they’re equal for n=3, does that prove they’re always equal?
7
If they’re not equal for n=3, does that prove they’re not always equal?
Lecture Prerequisites
Read Section 4.1.
Note: 4.1 is background information. We don’t
intend to directly assess this material, but
assignment and exam questions may require
skills and knowledge from 4.1 to answer.
Solve problems like Exercise Set 4.1, #1-8, 1214, 18-31, 37-44, 52-60.
Complete the open-book, untimed quiz on Vista
that’s due before the next class.
8
Learning Goals: Pre-Class
By the start of class, you should be able to:
– Convert sequences to and from explicit formulas
that describe the sequence.
– Convert sums to and from summation/”sigma”
notation.
– Convert products to and from product/”pi”
notation.
– Manipulate formulas in summation/product
notation by adjusting their bounds, merging or
splitting summations/products, and factoring out
values.
9
Learning Goals: In-Class
By the end of this unit, you should be able
to:
– Establish properties of self-referential
structures using inductive proofs that naturally
build on those self-references.
10
Where We Are in
The Big Stories
Theory
How do we model
computational systems?
Now: Developing a new
proof technique that’s
perfect for algorithms
involving (111 people)
loops or (110 people)
recursion... which is
almost all interesting
algorithms!
Hardware
How do we build devices to
compute?
Now: Taking a break in
lecture. In lab, about one
week away from
pulling it all together
into a working
computer!
11
Outline
• Prereqs, Learning Goals, and Quiz Notes
• Problems and Discussion
– Single-Elimination Tournaments
– Binary Trees
• A First Pattern for Induction
• Induction on Numbers
• Next Lecture Notes
12
Single-Elimination Tournaments
In each round teams play in pairs. Losing
teams are eliminated. The tournament
ends when only one team remains.
13
Single-Elimination
Tournament Problem
What’s the maximum number of teams in an
n-round single-elimination tournament?
a. n teams
b. 2n teams
c. n2 teams
d. 2n teams
e. None of these
14
Tournament
Step-by-Step
Problem 2: Prove your result for...
n=0
n=1
n=2
n=3
n=4
...
15
Tournament Logic
So, if p teams can play in an n-round
tournament, then 2p teams can play in an
n+1-round tournament.
If we want to prove this statement, which of the
following techniques might we use?
a. Antecedent assumption
b. Witness proof
c. WLOG
d. Proof by cases
e. None of these
16
Tournament Proof
Proof that 2n teams can play in an n-round
tournament:
Only 20 = one team (the automatic winner!) can
“play” in a 0-round tournament.
We work up to any other size by showing: if 2k teams
can play in a k-round tournament, then 2k+1 teams
can play in an k+1-round tournament.
Why? Assume the antecedent. Then, a k+1-round
tournament has half its teams eliminated in the
first round. It then has k rounds left and, by
assumption, can have 2k teams. The first round
started with twice that many: 2*2k = 2k+1.
17
Tournament
Step-by-Step
Problem 2: Prove your result for...
n=0
n=1
n=2
n=3
n=4
...
20 = 1 team
2*1 = 21 = 2 teams
2*2 = 22 = 4 teams
2*4 = 23 = 8 teams
2*8 = 24 = 16 teams
18
Outline
• Prereqs, Learning Goals, and Quiz Notes
• Problems and Discussion
– Single-Elimination Tournaments
– Binary Trees
• A First Pattern for Induction
• Induction on Numbers
• Next Lecture Notes
19
“Binary Trees”
A “binary tree” is a root
“node” and a collection
of “child nodes”
beneath the root.
Each node is an object
that has up to two
children—a left child
and a right child—each
of which are
themselves binary
trees.
10
5
2
20
9
7
15
17
20
(They let us do some cool CS things... see CS110, 211, and 221.)
10
Binary Trees’ Height
A binary tree’s “height” is the
maximum number of steps it
takes to get from the root down
to a node with no children.
5
This one’s height is:
a. 0
2
b. 1
c. 2
7
d. 3
e. 4
5
20
2
9
15
7
17
10
20
9
15
17
21
10
Binary Trees’ Height
5
20
2
15
9
7
17
Problem 1: What’s the maximum number of
nodes in a binary tree of height n?
22
10
Binary Trees’ Height
5
20
2
9
15
7
17
Problem 2: Prove your result.
23
10
Binary Trees,
Take Two
5
20
2
9
15
7
17
Problem 1: Give an algorithm to determine
the height of a binary tree.
Problem 2: Prove that your algorithm is
correct.
24
Outline
• Prereqs, Learning Goals, and Quiz Notes
• Problems and Discussion
– Single-Elimination Tournaments
– Binary Trees
• A First Pattern for Induction
• Induction on Numbers
• Next Lecture Notes
25
An Induction Proof Pattern
Type of Problem: Prove some property of a
structure that is naturally defined in terms of
itself.
Part 1: Insight. Induction doesn’t help you with
this part. It is not a technique to figure out
patterns, only to prove them.
Part 2: Proof. Establish that the property holds
for simple structures. Establish that it holds
at each step of construction of a more
complex structure.
26
Natural Numbers and Induction
Can we prove things about the natural
numbers using induction? Are they “selfreferential”?
Let’s try one...
Problem: What is the sum of the natural
numbers 0..n?
27
Partly Worked Problem:
Sum of 0..n
Partly Worked Problem: What is the sum
of the natural numbers 0..n?
Induction doesn’t help with insight...
But spoilers do: n(n+1)/2.
Now, how do we prove it?
28
Partly Worked Problem:
Sum of 0..n
Partly Worked Problem: Prove that the
sum of the natural numbers 0..n is
n(n+1)/2.
Is this self-referential? If we knew the sum
of the numbers 0..(n-1), would it tell us
anything about the sum of the numbers
0..n?
29
Outline
• Prereqs, Learning Goals, and Quiz Notes
• Problems and Discussion
– Single-Elimination Tournaments
– Binary Trees
• A First Pattern for Induction
• Induction on Numbers
• Next Lecture Notes
30
Learning Goals: In-Class
By the end of this unit, you should be able
to:
– Establish properties of self-referential
structures using inductive proofs that naturally
build on those self-references.
Note: this learning goal is not yet looking for formal
inductive proofs. Instead, we’re just exploring how we
work with things that are defined in terms of themselves.
31
Next Lecture Learning Goals:
Pre-Class
By the start of class, you should be able to:
– Given a theorem to prove stated in terms of its
induction variable (i.e., usually, in terms of n),
write out the skeleton of an inductive proof
including: the base case(s) that need to be
proven, the induction hypothesis, and the
inductive step that needs to be proven.
So, take what we did in this lecture and use the
textbook readings to formalize your understanding.
32
We will have much more practice on inductive proofs.
Next Lecture Prerequisites
Read Section 4.2-4.4.
Solve (or at least “set up”, by writing the base
case(s) that need to be proved, the induction
hypothesis, and the inductive step that needs
to be proved) problems like Exercise Set 4.2
#1-2, 5-17, and 31; 4.3 #1, 8-27, 29, and 3031, and 4.4 #1-7, 9-10, and 24.
Solve problems like Exercise Set 4.2 #3-4 and
32, 4.3 #6-7 and 30-31, and 4.4 #17.
Complete the open-book, untimed quiz on Vista
that’s due before the next class.
33