微信客服：xiaoxionga100
微信客服：ITCS521
程序代写案例-CS 173
时间：2022-07-09
Induction
CS 173
Summer 2022
Calvin Beideman
Learning Objectives
•Understand how to read and write induction proofs
•Understand why induction is a valid proof technique
Proving “for all” statements
∀ ∈ ℕ, σ=1
=
+1
2
Induction
∀ ∈ ℕ, ()
Proof Outline:
We will show that () is true for every natural number by induction on .
Base case(s): We need to show that (0) is true.
[show that (0) is true]
Induction step: Suppose that () is true for = 0, 1, … , − 1. We need to
show that () is true.
[show that () is true]
Induction
∀ ∈ ℕ, σ=1
=
+1
2
Proof:
Let be the statement
We will show that () is true for every natural number by induction on .
Base case(s): We need to show that (0) is true.
Induction step: Suppose that () is true for = 0, 1, … , − 1. We need to
show that () is true.
Why does induction work?
• Dominoes
• Each domino knocks down
the next, so eventually,
they all fall.
• Recursion Fairy
• “magically” solves smaller problems
• Smallest Counterexample
• “Well-ordering-property”
• Okay to not fully “get it”
Another Example
For every natural number ≥ 4, ! > 2
Induction with multiple variables
∀, ∈ ℤ+, with ≠ 1, we have σ=1
=
(−1)
−1
Induction with multiple variables
∀, ∈ ℤ+, with ≠ 1, we have σ=1
=
(−1)
−1
Let () be the statement “∀ ∈ ℤ+, with ≠ 1, σ=1
=
(−1)
−1
.” We will show that () is
true for every positive integer by induction on .
Making Change
The land of Inconvenience has only 3 cent coins and 5 cent coins. Show that
every price which is at least 15 cents can be made using only these coins.
Be careful with base cases!
For every ∈ ℕ, is even.
Proof:
Let be the statement: “ is even.”
We will show that () is true for every natural number by induction on .
Base case: We need to show that (0) is true.
0 = 2 0 , so by the definition of even, 0 is even.
Induction step: Suppose that () is true for = 0, 1, … , − 1. We need to show
that () is true.
By our induction hypothesis, − 2 = 2 for some integer .
So = − 2 + 2 = 2 + 2 = 2( + 1), so by the definition of even, is even.
Induction on Graphs
For any positive integer , if all nodes in a graph have degree less than or
equal to , then can be colored with + 1 colors.
More Graph Induction
For any graph = (, ), we have σ∈ deg() = 2|| .
More Graph Induction
For any graph = (, ), we have σ∈ deg() = 2|| .
Graph Induction gone wrong
Every graph with minimum degree at least 1 is connected.
Proof:
Let be the statement “every graph with nodes and minimum degree at least 1 is connected.”
We will show that () is true for every positive integer by induction on .
Base case: We need to show that (1) is true.
Let be a graph with 1 node, and let be that node. There is a walk from to , so is connected.
Induction step: Suppose that () is true for = 1, 2, … , − 1. We need to show that () is true.
Let be a graph with − 1 nodes, and let be the graph on nodes created by adding a new node to . If
has minimum degree 1, then must have an edge to some vertex of . By our induction hypothesis, is
connected, so there exists a walk from to every other node of . By adding the edge {, } to each of these
walks, we can obtain a walk from to every vertex of , so is connected as well.
Induction on Games
In The Subtraction Game, there are 2 players and a pile of objects. On their
turn, a player can remove 1, 2, or 3 of these objects. Whoever removes the last
object wins. Show that the 2nd player can guarantee a win if is a multiple of 4.
Induction on Games
Chomp!
In the 2-player game of Chomp!, the initial board is an × grid. On a
player’s turn, they remove a rectangle of squares which includes the top left
square. Whoever removes the bottom right square loses. Show that when
and are not both 1, then second player can guarantee a win.
Chomp!
Fundamental Theorem of Arithmetic
For every ∈ ℕ, ≥ 2, can be expressed as the product of one or more primes.
Learning Objectives
•Understand how to read and write induction proofs
•Understand why induction is a valid proof technique
CS 173
Summer 2022
Calvin Beideman
Learning Objectives
•Understand how to read and write induction proofs
•Understand why induction is a valid proof technique
Proving “for all” statements
∀ ∈ ℕ, σ=1
=
+1
2
Induction
∀ ∈ ℕ, ()
Proof Outline:
We will show that () is true for every natural number by induction on .
Base case(s): We need to show that (0) is true.
[show that (0) is true]
Induction step: Suppose that () is true for = 0, 1, … , − 1. We need to
show that () is true.
[show that () is true]
Induction
∀ ∈ ℕ, σ=1
=
+1
2
Proof:
Let be the statement
We will show that () is true for every natural number by induction on .
Base case(s): We need to show that (0) is true.
Induction step: Suppose that () is true for = 0, 1, … , − 1. We need to
show that () is true.
Why does induction work?
• Dominoes
• Each domino knocks down
the next, so eventually,
they all fall.
• Recursion Fairy
• “magically” solves smaller problems
• Smallest Counterexample
• “Well-ordering-property”
• Okay to not fully “get it”
Another Example
For every natural number ≥ 4, ! > 2
Induction with multiple variables
∀, ∈ ℤ+, with ≠ 1, we have σ=1
=
(−1)
−1
Induction with multiple variables
∀, ∈ ℤ+, with ≠ 1, we have σ=1
=
(−1)
−1
Let () be the statement “∀ ∈ ℤ+, with ≠ 1, σ=1
=
(−1)
−1
.” We will show that () is
true for every positive integer by induction on .
Making Change
The land of Inconvenience has only 3 cent coins and 5 cent coins. Show that
every price which is at least 15 cents can be made using only these coins.
Be careful with base cases!
For every ∈ ℕ, is even.
Proof:
Let be the statement: “ is even.”
We will show that () is true for every natural number by induction on .
Base case: We need to show that (0) is true.
0 = 2 0 , so by the definition of even, 0 is even.
Induction step: Suppose that () is true for = 0, 1, … , − 1. We need to show
that () is true.
By our induction hypothesis, − 2 = 2 for some integer .
So = − 2 + 2 = 2 + 2 = 2( + 1), so by the definition of even, is even.
Induction on Graphs
For any positive integer , if all nodes in a graph have degree less than or
equal to , then can be colored with + 1 colors.
More Graph Induction
For any graph = (, ), we have σ∈ deg() = 2|| .
More Graph Induction
For any graph = (, ), we have σ∈ deg() = 2|| .
Graph Induction gone wrong
Every graph with minimum degree at least 1 is connected.
Proof:
Let be the statement “every graph with nodes and minimum degree at least 1 is connected.”
We will show that () is true for every positive integer by induction on .
Base case: We need to show that (1) is true.
Let be a graph with 1 node, and let be that node. There is a walk from to , so is connected.
Induction step: Suppose that () is true for = 1, 2, … , − 1. We need to show that () is true.
Let be a graph with − 1 nodes, and let be the graph on nodes created by adding a new node to . If
has minimum degree 1, then must have an edge to some vertex of . By our induction hypothesis, is
connected, so there exists a walk from to every other node of . By adding the edge {, } to each of these
walks, we can obtain a walk from to every vertex of , so is connected as well.
Induction on Games
In The Subtraction Game, there are 2 players and a pile of objects. On their
turn, a player can remove 1, 2, or 3 of these objects. Whoever removes the last
object wins. Show that the 2nd player can guarantee a win if is a multiple of 4.
Induction on Games
Chomp!
In the 2-player game of Chomp!, the initial board is an × grid. On a
player’s turn, they remove a rectangle of squares which includes the top left
square. Whoever removes the bottom right square loses. Show that when
and are not both 1, then second player can guarantee a win.
Chomp!
Fundamental Theorem of Arithmetic
For every ∈ ℕ, ≥ 2, can be expressed as the product of one or more primes.
Learning Objectives
•Understand how to read and write induction proofs
•Understand why induction is a valid proof technique
