Transcript PPT - UBC Computer Science

snick

snack
CPSC 121: Models of Computation
2011 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 Pattern for Induction
• Induction on Numbers
• Next Lecture Notes
2
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.
4
Learning Goals: In-Class
By the end of this unit, you should be able
to:
– Given a theorem to prove via induction and
the insight into how the problem breaks down
into one or more smaller problem(s), write out
a complete proof strategy.
– Prove naturally self-referential properties by
induction. (That is, identify the “insight” and
flesh out the strategy into a complete proof.)
5
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 recursion (or
iteration)... which is
almost all interesting
algorithms!
Hardware
How do we build devices to
compute?
Now: Taking a break in
lecture. In lab, continuing
to build toward the
complete, working
computer! (Although
lab’s taking a break
soon, too, for regular
expressions.)
6
Outline
• Prereqs, Learning Goals, and Quiz Notes
• Problems and Discussion
– Single-Elimination Tournaments
– Binary Trees
• A Pattern for Induction
• Induction on Numbers
• Next Lecture Notes
7
Single-Elimination Tournaments
In each round teams play in pairs. Losing
teams are eliminated. The tournament
ends when only one team remains.
8
What is a
Tournament?
Let’s think like CPSC 110ers…
A tournament is one of:
9
Single-Elimination
Tournament Problem
What’s the maximum number of teams in a
0-round single-elimination tournament?
a. 0 teams
b. 1 team
c. 2 teams
d. 3 teams
e. None of these
10
Think: what does this correspond to in the data definition?
Single-Elimination
Tournament Problem
What’s the maximum number of teams in a
1-round single-elimination tournament?
a. 0 teams
b. 1 team
c. 2 teams
d. 3 teams
e. None of these
A “one round tournament” has only one set of games.
11
A “two round tournament” has two sets of games (finals and semi-finals).
Single-Elimination
Tournament Problem
What’s the maximum number of teams in a
2-round single-elimination tournament?
a. 0 teams
b. 1 team
c. 2 teams
d. 3 teams
e. None of these
Would there be any “byes” in the tournament?
12
A team with a “bye” gets to advance to the next round “for free”.
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
13
Tournament
Step-by-Step
Problem 2: Prove your result for...
n=0
n=1
n=2
n=3
...
14
Tournament Logic
If at most 2n-1 teams can play in an (n-1)-round
tournament, then at most 2n teams can play
in an n-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
15
The “insight into how the
problem breaks down”
A tournament of n rounds is made up of two
tournaments of (n-1) rounds, like how the
Stanley Cup Finals is set “on top of” the
“east half” and “west half” tournaments.
One extra round:
east winner vs. west winner
16
The “insight into how the
problem breaks down”
The n-round tournament with the maximum
number of teams is made from two
(n-1)-round tournaments with the
maximum number of teams.
17
Completing (?)
the Proof
Theorem: if at most 2n-1 teams can play in an (n-1)round tournament, then at most 2n teams can play
in an n-round tournament.
Proof:
Assume at most 2n-1 teams can play in an (n-1)round tournament. An n-round tournament is two
(n-1)-round tournaments where the winners play
each other (since there must be a single
champion). By assumption, each of these may
have at most 2n-1 teams. So, the overall
tournament has at most 2*2n-1 = 2n teams. QED!
18
Are We Done?
Here’s the logical structure of our theorem:
nZ0, Max(n-1,2n-1)  Max(n,2n).
Does that prove nZ0, Max(n,2n)?
a. Yes.
b. No.
c. I don’t know.
P.S. Is this really what we proved?
19
Is our theorem true for all non-negative integers?
What More Do We Need?
This parallels the self-referential variant of
our tournament “data definition”:
nZ0, (n > 0)  Max(n-1,2n-1)  Max(n,2n).
Why doesn’t this work for 0?
What do we do about our base case of our
data definition?
20
Completing (?)
the Proof (again)
Base Case Theorem: At most one team
can play in a 0-round tournament.
Proof:
Every tournament must have one unique
winner. A zero-round tournament has no
games; so, it can only include one team:
the winner. QED!
21
Everybody’s a winner. That’s so sweet 
Now Are We Done?
Here’s the logical structure of our theorems:
Max(0,1).
nZ0, (n > 0)  Max(n-1,2n-1)  Max(n,2n).
Do these prove nZ0, Max(n,2n)?
a. Yes.
b. No.
c. I don’t know.
22
Step-by-Step?
Here’s the logical structure of our theorems:
Max(0,20).
nZ0, (n > 0)  Max(n-1,2n-1)  Max(n,2n).
Do these prove Max(1,21)?
a. Yes.
b. No.
c. I don’t know.
23
Step-by-Step?
Here’s the logical structure of our theorems:
Max(0,20).
nZ0, (n > 0)  Max(n-1,2n-1)  Max(n,2n).
Plus, we know Max(1,21).
Do all of these prove Max(2,22)?
a. Yes.
b. No.
c. I don’t know.
24
Step-by-Step?
Here’s the logical structure of our theorems:
Max(0,20).
nZ0, (n > 0)  Max(n-1,2n-1)  Max(n,2n).
Plus, we know Max(1,21) and Max(2,22).
Do all of these prove Max(3,23)?
a. Yes.
b. No.
c. I don’t know.
25
Step-by-Step?
Here’s the logical structure of our theorems:
Max(0,20).
nZ0, (n > 0)  Max(n-1,2n-1)  Max(n,2n).
From this, can we prove Max(n,2n)
for any particular integer n?
a. Yes.
b. No.
c. I don’t know.
26
Tournament Proof Summary
Theorem: 2n teams can play in an n-round tournament.
Proof: We proceed by induction on n.
Base Case: Every tournament must have a single winner. A
zero-round tournament has no games and so can only include
one (that is, 20) team: the winner. So, 20 teams can play in a
0-round tournament. 
Inductive Step (for n greater than 0: if at most 2n-1 teams can
play in an (n-1)-round tournament, then at most 2n teams can
play in an n-round tournament):
WLOG, let n be an integer greater than 0. Assume at most 2n-1
teams can play in an (n-1)-round tournament. An n-round
tournament is two (n-1)-round tournaments where the winners
play each other (since there must be a single champion). By
assumption, each of these may have at most 2n-1 teams. So,
the overall tournament has at most 2*2n-1 = 2n teams. 
This completes our induction proof. QED
27
Outline
• Prereqs, Learning Goals, and Quiz Notes
• Problems and Discussion
– Single-Elimination Tournaments
– Binary Trees
• A Pattern for Induction
• Induction on Numbers
• Next Lecture Notes
28
“Binary Trees”
A “binary tree” is either
a leaf or a root “node”
and two children,
each of which is a
binary tree.
(Note: a slightly different
definition is common,
but less convenient.)
10
5
2
20
9
7
15
17
29
(They let us do some cool CS things... see CS110, 210, 221.)
Binary Tree Data Definition
A binary-tree is one of:
- A leaf
- (make-node binary-tree
binary-tree number)
10
5
2
20
9
7
15
17
30
10
Binary Trees’ Height
5
2
20
9
15
7
17
A binary tree’s “height” is the
maximum number of steps it takes
to get from the root down to a node
with only leaves as children.
This one’s height is:
a. 0
b. 1
c. 2
d. 3
e. 4
31
10
Binary Trees’ Height
5
2
20
15
9
7
17
Problem 1: What’s the maximum number of
nodes in a binary tree of height n?
32
10
Binary Trees’ Height
5
2
20
9
15
7
17
Problem 2: Prove your result.
33
10
Binary Trees,
Take Two
5
2
20
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.
34
10
5
Worked: Algorithm for Height
2
9
20
15
7
17
Height(t):
Is t a leaf?
Yes: evaluate to -1
No: recursively find the height of
each subtree hl and hr and
evaluate to max(hl, hr) + 1.
35
10
Worked: Proof of
Algorithm’s Correctness
5
2
20
9
15
7
17
We proceed by induction on the size of the tree.
Base case: On a leaf (the smallest tree), our algorithm gives a
height of -1. We must go up one level to reach a node with leaves
as children; so, this is correct. (Really, it’s just correct by definition.)
Inductive case: Assume our algorithm works correctly on all trees
smaller than a particular non-leaf tree t.
t is not a leaf; so, our algorithm calculates the height of each subtree
hl and hr. These heights are correct by assumption.
To reach a node with only leaves as children, we go into either the
left or right subtree. The length of the path through the left subtree
is therefore hl+1, with the +1 for the step down into that subtree.
Similarly, the right path is hr +1. The height is the larger of these
possible paths; so, it’s max(hl, hl) + 1, which is what our algorithm
evaluates to. QED
36
Outline
• Prereqs, Learning Goals, and Quiz Notes
• Problems and Discussion
– Single-Elimination Tournaments
– Binary Trees
• A Pattern for Induction
• Induction on Numbers
• Next Lecture Notes
37
An Induction Proof Pattern
Type of Problem: Prove some property of a
structure that is naturally defined in terms of itself.
Part 1: Insight: how does the problem “break down”
in terms of smaller pieces? 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 is true for
your base case(s). Establish that it is true at each
step of construction of a more complex structure.
38
A Pattern For Induction
Theorem: 2n teams can play in an n-round tournament.
Proof: We proceed by induction on n.
Base Case(s) (at most 20 teams can play in a 0-round
tournament): Every tournament must have one unique winner.
A zero-round tournament has no games; so, it can only
include one (that is, 20) team: the winner.
Inductive Step (for n greater than 0: if at most 2n-1 teams can
play in an (n-1)-round tournament, then at most 2n teams can
play in an n-round tournament):
WLOG, let n be an integer greater than 0. Assume at most 2n-1
teams can play in an (n-1)-round tournament. An n-round
tournament is two (n-1)-round tournaments where the winners
play each other (since there must be a single champion). By
assumption, each of these may have at most 2n-1 teams. So,
the overall tournament has at most 2*2n-1 = 2n teams.
This completes our induction proof. QED
39
A Pattern For Induction
Theorem: P(n) is true for all n  some smallest number.
Proof: We proceed by induction on n.
Base Case(s) (P(.) is true for a few simple cases): Prove with our other
techniques. Which cases? Almost certainly the some smallest
number. Maybe more. Make notes on which you need, as with a
witness proof!
Inductive Step (for n > the largest of your base cases: if P(.) is true for
whichever cases you need, then P(n) is true):
WLOG, let n be greater than the largest of your base cases.
Assume P(.) is true for whichever cases you need.
Break P(n) down in terms of the smaller case(s). The smaller cases
are true, by assumption. Build back up to show that: P(n) is true.
This completes our induction proof. QED
40
A Pattern For Induction
 Which base cases? Almost certainly the smallest n. Otherwise,
you don’t know yet. Do the rest of the proof now. Come back to
the base case(s) when you know which one(s) you need!
41
A Pattern For Induction
 Which values are we going to assume P(.) is true for?
Whichever we need. How do we know the ones we need? We
don’t, yet. So… do the rest of the proof now. Come back
to the assumption (“induction hypothesis”) when you know
which one(s) you need!
42
A Pattern For Induction
 What must n be larger than? The largest of your base cases.
(Why? So you don’t assume the theorem true for something
that’s too small, like a negative one round tournament.) But,
you don’t know all your base cases yet. So…do the rest of the
proof now. Come back to this bound once you know your base
case(s).
43
A Pattern For Induction
 How do we break the problem down in terms of smaller cases?
THIS is the real core of every induction problem. Figure this
out, and you’re ready to fill in the rest of the blanks!
44
A Pattern For Induction
P(n) is ______________.
Theorem: P(n) is true for all n  _______.
Proof: We proceed by induction on n.
Base Case(s) (P(.) is true for _______):
Prove each base case via your other techniques.
Inductive Step (if P(.) is true for ________________, then P(n) is true,
for n > ____________):
WLOG, let n be greater than ____________.
Assume P(.) is true for __________________.
Break P(n) down in terms of the smaller case(s).
The smaller cases are true, by assumption.
Build back up to show that P(n) is true.
45
This completes our induction proof. QED
Examples: Breaking down
into a problem one smaller
You want to prove P(n) for all n  1. You know that P(n) is true if P(n-1)
is true. How do we fill in the blanks?
This is the most common style of
insight, and the same as we had in our
“# teams in a tournament” question.
46
(It’s called “weak induction”.)
Examples: Breaking down
into a problem one smaller
You want to prove P(n) for all n  1. You know that P(n) is true if P(n-1)
is true. How do we fill in the blanks?
Theorem: P(n) is true for all n  _______.
47
Examples: Breaking down
into a problem one smaller
You want to prove P(n) for all n  1. You know that P(n) is true if P(n-1)
is true. How do we fill in the blanks?
Theorem: P(n) is true for all n  1.
Proof: We proceed by induction on n.
Base Case(s) (P(.) is true for _______):
Prove each base case via your other techniques.
48
Examples: Breaking down
into a problem one smaller
You want to prove P(n) for all n  1. You know that P(n) is true if P(n-1)
is true. How do we fill in the blanks?
Theorem: P(n) is true for all n  1.
Proof: We proceed by induction on n.
Base Case(s) (P(.) is true for 1):
Prove each base case via your other techniques. We only need n=1
because n=2 works based on n=1, and all subsequent cases also
eventually break down into the n=1 case.
Inductive Step (for n > _______, if P(.) is true for ____________, then
P(n) is true):
49
Examples: Breaking down
into a problem one smaller
You want to prove P(n) for all n  1. You know that P(n) is true if P(n-1)
is true. How do we fill in the blanks?
Theorem: P(n) is true for all n  1.
Proof: We proceed by induction on n.
Base Case(s) (P(.) is true for 1):
Prove each base case via your other techniques.
Inductive Step (for n > 1: if P(.) is true for n-1, then P(n) is true):
WLOG, let n be greater than ____________.
Assume P(.) is true for __________________.
50
Examples: Breaking down
into a problem one smaller
You want to prove P(n) for all n  1. You know that P(n) is true if P(n-1)
is true. How do we fill in the blanks?
Theorem: P(n) is true for all n  1.
Proof: We proceed by induction on n.
Base Case(s) (P(.) is true for 1):
Prove each base case via your other techniques.
Inductive Step (for n > 1: if P(.) is true for n-1, then P(n) is true):
WLOG, let n be greater than 1.
Assume P(.) is true for n-1.
Break P(n) down in terms of the smaller case(s).
The smaller cases are true, by assumption.
Build back up to show that P(n) is true.
This completes our induction proof. QED
51
Rephrased a bit
(to get rid of P(.))
You want to prove P(n) for all n  1. You know that P(n) is true if P(n-1)
is true. How do we fill in the blanks?
Theorem: P(n) is true for all n  1.
Proof: We proceed by induction on n.
Base Case(s) (P(1) is true):
Prove each base case via your other techniques.
Inductive Step (for n > 1: if P(.) is true for n-1, then P(n) is true):
WLOG, let n be greater than 1.
Assume P(n-1) is true.
Break P(n) down in terms of the smaller case(s).
The smaller cases are true, by assumption.
Build back up to show that P(n) is true.
This completes our induction proof. QED
52
Examples: Breaking down
into all smaller problems
You want to prove P(n) for all n  22. You know that P(n) is true if P(.)
is true for every integer from 22 up to n-1. How do we fill in the
blanks?
This is the second most common style of
insight, and the same as we had in our “prove
the height algorithm correct” question.
(It’s called “strong induction”;
53
technically, we did “structural induction”.)
Examples: Breaking down
into all smaller problems
You want to prove P(n) for all n  22. You know that P(n) is true if P(.)
is true for every integer from 22 up to n-1. How do we fill in the
blanks?
Theorem: P(n) is true for all n  _______.
54
Examples: Breaking down
into all smaller problems
You want to prove P(n) for all n  22. You know that P(n) is true if P(.)
is true for every integer from 22 up to n-1. How do we fill in the
blanks?
Theorem: P(n) is true for all n  22.
Proof: We proceed by induction on n.
Base Case(s) (P(.) is true for _______):
Prove each base case via your other techniques.
55
Examples: Breaking down
into all smaller problems
You want to prove P(n) for all n  22. You know that P(n) is true if P(.)
is true for every integer from 22 up to n-1. How do we fill in the
blanks?
Theorem: P(n) is true for all n  22.
Proof: We proceed by induction on n.
Base Case(s) (P(.) is true for 22):
Prove each base case via your other techniques. For n=23, we just
need n=22. For n=24, we just need n=22 and n=23… and n=23
breaks down in terms of n=22, and so on.
Inductive Step (for n > _______, if P(.) is true for ____________, then
P(n) is true):
56
Examples: Breaking down
into all smaller problems
You want to prove P(n) for all n  22. You know that P(n) is true if P(.)
is true for every integer from 22 up to n-1. How do we fill in the
blanks?
Theorem: P(n) is true for all n  22.
Proof: We proceed by induction on n.
Base Case(s) (P(.) is true for 22):
Prove each base case via your other techniques.
Inductive Step (for n > 22: if P(.) is true for every integer from 22 up
to n-1, then P(n) is true):
WLOG, let n be greater than ____________.
Assume P(.) is true for __________________.
57
Examples: Breaking down
into all smaller problems
You want to prove P(n) for all n  22. You know that P(n) is true if P(.)
is true for every integer from 22 up to n-1. How do we fill in the
blanks?
Theorem: P(n) is true for all n  22.
Proof: We proceed by induction on n.
Base Case(s) (P(.) is true for 22):
Prove each base case via your other techniques.
Inductive Step (for n > 22: if P(.) is true for every integer from 22 up
to n-1, then P(n) is true):
WLOG, let n be greater than 22.
Assume P(.) is true for every integer from 22 up to n-1.
Break P(n) down in terms of the smaller case(s).
The smaller cases are true, by assumption.
Build back up to show that P(n) is true.
58
This completes our induction proof. QED
Rephrased a bit
(to be more predicate logic-y)
You want to prove P(n) for all n  22. You know that P(n) is true if P(.)
is true for every integer from 22 up to n-1. How do we fill in the
blanks?
Theorem: P(n) is true for all n  22.
Proof: We proceed by induction on n.
Base Case(s) (P(.) is true for 22):
Prove each base case via your other techniques.
Inductive Step (for n > 22: if P(.) is true for every integer from 22 up
to n-1, then P(n) is true):
WLOG, let n be greater than 22.
Assume for all integers i where 22  i < n, P(i) is true.
Break P(n) down in terms of the smaller case(s).
The smaller cases are true, by assumption.
Build back up to show that P(n) is true.
59
This completes our induction proof. QED
Examples: breaking down
into a problem half as big
You want to prove P(n) for all n  7. You know that P(n) is true if
P(n/2) and P(n/2) are both true (i.e., P(.) is true for n/2 rounded
down and n/2 rounded up). How do we fill in the blanks?
But, your insight may come in any form.
Maybe you need problems half as large or one-third.
Maybe you need problems that are 7 smaller.
Maybe you need the problems that are 1, 2, and 3 smaller.
60
Regardless, the pattern is the same!
Examples: breaking down
into a problem half as big
You want to prove P(n) for all n  7. You know that P(n) is true if
P(n/2) and P(n/2) are both true (i.e., P(.) is true for n/2 rounded
down and n/2 rounded up). How do we fill in the blanks?
Theorem: P(n) is true for all n  _______.
61
Examples: breaking down
into a problem half as big
You want to prove P(n) for all n  7. You know that P(n) is true if
P(n/2) and P(n/2) are both true (i.e., P(.) is true for n/2 rounded
down and n/2 rounded up). How do we fill in the blanks?
Theorem: P(n) is true for all n  7.
Proof: We proceed by induction on n.
Base Case(s) (P(.) is true for _______):
Prove each base case via your other techniques.
62
Examples: breaking down
into a problem half as big
You want to prove P(n) for all n  7. You know that P(n) is true if
P(n/2) and P(n/2) are both true (i.e., P(.) is true for n/2 rounded
down and n/2 rounded up). How do we fill in the blanks?
Theorem: P(n) is true for all n  7.
Proof: We proceed by induction on n.
Base Case(s) (P(.) is true for n = 7, 8, 9, 10, 11, 12, 13):
Prove each base case via your other techniques. (We need all the
way up to 13 because only at 14/2 do we reach a base case. From
15 on, we always eventually hit a base case.)
Inductive Step (for n > _______, if P(.) is true for ____________, then
P(n) is true):
63
Examples: breaking down
into a problem half as big
You want to prove P(n) for all n  7. You know that P(n) is true if
P(n/2) and P(n/2) are both true (i.e., P(.) is true for n/2 rounded
down and n/2 rounded up). How do we fill in the blanks?
Theorem: P(n) is true for all n  7.
Proof: We proceed by induction on n.
Base Case(s) (P(.) is true for n = 7, 8, 9, 10, 11, 12, 13):
Prove each base case via your other techniques.
Inductive Step (for n > 13: if P(.) is true for n/2 and n/2 , then P(n)
is true):
WLOG, let n be greater than ____________.
Assume P(.) is true for __________________.
64
Examples: breaking down
into a problem half as big
You want to prove P(n) for all n  7. You know that P(n) is true if
P(n/2) and P(n/2) are both true (i.e., P(.) is true for n/2 rounded
down and n/2 rounded up). How do we fill in the blanks?
Theorem: P(n) is true for all n  7.
Proof: We proceed by induction on n.
Base Case(s) (P(.) is true for n = 7, 8, 9, 10, 11, 12, 13):
Prove each base case via your other techniques.
Inductive Step (for n > 13: if P(.) is true for n/2 and n/2 , then P(n)
is true):
WLOG, let n be greater than 13.
Assume P(.) is true for n/2 and n/2.
Break P(n) down in terms of the smaller case(s).
The smaller cases are true, by assumption.
Build back up to show that P(n) is true.
65
This completes our induction proof. QED
Rephrased slightly
(to get rid of P(.))
You want to prove P(n) for all n  7. You know that P(n) is true if
P(n/2) and P(n/2) are both true (i.e., P(.) is true for n/2 rounded
down and n/2 rounded up). How do we fill in the blanks?
Theorem: P(n) is true for all n  7.
Proof: We proceed by induction on n.
Base Case(s) (P(7), P(8), P(9), P(10), P(11), P(12), P(13)):
Prove each base case via your other techniques.
Inductive Step (for n > 13: if P(.) is true for n/2 and n/2 , then P(n)
is true):
WLOG, let n be greater than 13.
Assume P( n/2) and P(n/2) are both true.
Break P(n) down in terms of the smaller case(s).
The smaller cases are true, by assumption.
Build back up to show that P(n) is true.
66
This completes our induction proof. QED
Outline
• Prereqs, Learning Goals, and Quiz Notes
• Problems and Discussion
– Single-Elimination Tournaments
– Binary Trees
• A Pattern for Induction
• Induction on Numbers
• Next Lecture Notes
67
Natural Numbers and Induction
Can we prove things inductively about the
natural numbers without a recursive data
definition? Are they “self-referential”?
Here’s one answer:
A natural number is:
- 1
- The next number after (successor of) a
natural number
68
Natural Numbers and Induction
Can we prove things inductively about the
natural numbers without a recursive data
definition? Are they “self-referential”?
But, let’s just try one!
Problem: What is the sum of the natural
numbers 0..n?
69
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?
70
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?
71
Outline
• Prereqs, Learning Goals, and Quiz Notes
• Problems and Discussion
– Single-Elimination Tournaments
– Binary Trees
• A Pattern for Induction
• Induction on Numbers
• Next Lecture Notes
72
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.
73
Next Lecture Learning Goals:
Pre-Class
By the start of class, you should be able to:
– Given a theorem to prove and the insight into
how to break the problem down in terms of
smaller problems, 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.
74
We will have much more practice on inductive proofs.
Next Lecture Prerequisites
See the Mathematical Induction Textbook
Sections at the bottom of the “Textbook
and References” page.
75