Induction and recursion

Overview

Kent Quanrud develops induction and recursion as complementary tools for algorithm design: first specify clearly what a recursive procedure takes in and guarantees, then use induction to justify its calls on smaller inputs. Examples progress from Tower of Hanoi and the Euclidean GCD algorithm to a proof of König’s theorem for bipartite graphs, connecting correctness, running-time analysis, and matching–vertex-cover duality.

Key takeaways

A recursive specification should clearly state the inputs and guarantee; for Tower of Hanoi, specifying the source, destination, spare post, and ring count makes the same procedure reusable on every subproblem.
Induction proves recursive correctness when each call reduces a well-defined measure: Hanoi reduces the ring count, while subtraction-based GCD requires the less obvious measure x+y.
Measure complexity in terms of the representation size: subtraction-based GCD can require Θ(x) iterations, which is exponential in the Θ(log x) bits needed to encode x.
Euclid’s GCD recurrence gcd(x, y) = gcd(y, x mod y) shrinks its second argument by at least a factor of two every two calls, yielding O(log y) iterations.
For bipartite graphs, every matching is no larger than every vertex cover because disjoint matching edges require distinct covering vertices; König’s theorem strengthens this bound to equality for an optimal pair.
Strengthening a recursive specification—such as requiring a minimum-move Hanoi solution—can make subproblems more useful by giving recursive calls stronger guarantees.

Chapters

0:00 Recursive Specifications Set Up Algorithm Design

The class connects recursion with algorithm analysis and proofs by induction.
For merge sort, identifying the input, output, and relationship between them is the key design step; the implementation often follows naturally.
A precise recursive specification can make later correctness proofs and recursive calls much simpler.

3:00 Stair Climbing as an Inductive Argument

Treat a staircase of n steps uniformly rather than writing separate instructions for each step.
Use zero steps as a base case and reduce an n-step problem by taking one step, leaving n−1 steps.
Induction formalizes why instructions that work for the smaller remainder also work for the full staircase.

7:00 Tower of Hanoi: Why Brute-Force Moves Become Confusing

The puzzle moves eight ordered rings from post A to post B using three posts, without placing a larger ring on a smaller one.
Trying moves one at a time quickly becomes difficult: the class reaches only a few rings while debating whether an early move was correct.
The example motivates replacing local guesswork with a recursive description of the task.

11:00 Specify and Implement Recursive Tower of Hanoi

Define the procedure by the number of rings and the roles of the source, destination, and spare posts.
To move n rings from A to B, recursively move n−1 from A to C, move the largest ring from A to B, then move n−1 from C to B.
The base case n = 0 performs no moves; naming the posts as parameters lets the same procedure handle each subproblem.

18:00 Prove Hanoi Correctness and Strengthen the Specification

Prove the Hanoi algorithm by induction on n: the empty-tower case is immediate, and the recursive calls handle n−1 rings.
Once those calls are correct, the largest ring can move legally and the remaining rings can be placed on it.
A stronger specification can ask for the minimum number of moves as well as a legal solution, giving the recursive calls a more useful guarantee.
Recursive specifications also adapt to variants, such as restricting moves to a cyclic order among the three posts.

25:00 From a Valid Hanoi Solution to a Minimum-Move Solution

To move the largest ring, the top n−1 rings must first be cleared from its post; the largest ring then requires one move.
The remaining n−1 rings must be transferred to the destination, so the same recursive structure yields the minimum-move recurrence.
Strengthening a specification may make the promised result more demanding, but it also provides stronger guarantees for recursive subproblems.

34:45 Define the Greatest Common Divisor Problem

The GCD of two positive integers is their greatest common divisor; for example, gcd(4953, 8763) = 381.
The recursive specification takes integers x and y and returns gcd(x, y), with the inputs arranged so x is at least y.
The key number-theoretic observation is that common divisors are preserved when replacing one input with a suitable difference.

38:00 Subtraction-Based GCD and a Decreasing Induction Measure

The subtraction algorithm uses gcd(x, y) = gcd(x−y, y) when x is larger than y, and returns x when y = 0.
Induction on y alone is insufficient because subtracting a small y from a much larger x may leave the smaller argument unchanged after reordering.
The sum x+y decreases on each recursive call, so it supplies a valid induction measure and a simple upper bound of O(x+y) iterations.

46:00 Why Subtraction GCD Is Exponential in Input Bit Length

An integer x takes about log₂x bits to represent, so x itself is not the input length.
The subtraction algorithm can take Θ(x) iterations when x is a huge odd number and y = 2, repeatedly subtracting 2.
That iteration count is exponential in the number of bits, despite the algorithm appearing linear in the numeric value.

53:00 Euclid’s Remainder Identity Produces a Faster GCD Algorithm

Write x = ky + r, where r = x mod y; a number divides both x and y exactly when it divides y and r.
This yields the recursive algorithm gcd(x, y) = gcd(y, x mod y), with gcd(x, 0) = x as its base case.
Because 0 ≤ x mod y < y, induction on the second argument directly justifies that each recursive call is smaller.

58:00 Bound Euclid’s Algorithm by Halving Every Two Steps

If the remainder r is below y/2, the second argument immediately shrinks by at least a factor of two.
If r is at least y/2, the next remainder y mod r is at most y−r, which is at most y/2.
Thus every two iterations halve the second argument, giving O(log y) iterations and a running time linear in the operands’ bit lengths under the lecture’s operation-count model.

1:04:00 Bipartite Matching and Vertex Cover

A matching selects edges with no shared endpoints; a vertex cover selects vertices incident to every edge.
In the illustrated bipartite graph, the class finds candidate solutions of size five for both problems, while noting that optimality needs proof.
The two problems express complementary goals: pack as many disjoint edges as possible or cover all edges with as few vertices as possible.

1:10:00 Why Every Matching Is No Larger Than Every Vertex Cover

Each edge in a matching must have at least one endpoint in any vertex cover.
Matching edges are endpoint-disjoint, so a single selected vertex cannot cover two of those matching edges.
Therefore, every matching’s size is at most every vertex cover’s size.

1:13:00 Set Up Induction for König’s Theorem

König’s theorem states that every bipartite graph has a maximum matching whose size equals the size of a minimum vertex cover.
Induct on graph size, defined as the number of vertices plus the number of edges; the empty graph is the base case.
Let a minimum vertex cover consist of left-side vertices S and right-side vertices T, and split the proof according to whether a minimum cover uses both sides.

1:16:00 Combine Smaller Matchings When the Cover Uses Both Sides

When a minimum cover has nonempty S and T, form one smaller graph by deleting T and its incident edges, and another by deleting S and its incident edges.
S remains a cover in the first subgraph, while T remains a cover in the second.
Induction supplies matchings of sizes |S| and |T|; because the deleted vertex sets separate the subproblems, those matchings can be combined into one of size |S| + |T|.

1:19:00 Handle Lopsided Covers to Complete König’s Theorem

If every minimum cover lies entirely on one side, delete an edge and apply induction to the smaller graph.
If the original one-sided cover is still minimum after deletion, the inductive matching already has the required size and remains valid in the original graph.
If it is no longer minimum, the smaller graph has a strictly smaller cover; adding back an endpoint of the deleted edge creates a smaller cover for the original graph, contradicting minimality.
The two cases establish a matching equal in size to a minimum vertex cover, completing the inductive proof.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Kent Quanrud.