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