CS2050 L08 Strong Induction
Watch on YouTube →
Overview
Abrahim Ladha explains strong induction as a proof method that assumes a claim holds for all smaller cases, then uses examples to show how this handles recurrences and problems with varied dependencies. He proves results about a recursively defined square sequence, Binet's formula for Fibonacci numbers, minimum chocolate-bar cuts, prime factorization existence, and graph and polyhedron structure.
Key takeaways
- Strong induction is especially useful when proving case k + 1 requires multiple earlier cases or an arbitrary smaller case, as in the recurrence for aₙ = n².
- Base cases must cover every dependency used by the inductive step: the square recurrence needs n = 0 and n = 1 because it references the previous two terms.
- For a chocolate bar with n unit squares, any first cut creates smaller pieces whose required cuts add to n − 2; including the first cut proves the minimum is n − 1.
- Every integer n ≥ 2 can be shown to have a prime factorization by splitting composites into smaller factors and applying strong induction, but uniqueness requires a separate argument.
- A connected acyclic graph with n vertices has n − 1 edges because deleting an edge splits it into two smaller connected acyclic graphs.
- For spherical polyhedra with faces of at least three sides, deleting an edge reduces both E and F by one while preserving V, so V − E + F remains 2.
Chapters
- Ordinary induction uses the case k to prove k + 1, while strong induction can use every case from the starting point through k.
- The domino analogy distinguishes a simple chain from arrangements where several earlier dominoes may be needed to trigger the next.
- Strong induction may require multiple base cases, depending on which earlier cases the inductive step uses.
- The sequence is defined by a₀ = 0, a₁ = 1, and aₙ = 2aₙ₋₁ − aₙ₋₂ + 2 for n ≥ 2.
- Computing early terms gives 0, 1, 4, 9, and 16, suggesting the closed form aₙ = n².
- The recurrence references two earlier terms, foreshadowing why the proof needs more than the immediately preceding case.
- The proof establishes base cases n = 0 and n = 1, matching the recurrence's two previous terms.
- The inductive hypothesis can assume aᵢ = i² for every 0 ≤ i ≤ k, or just the two terms needed: aₖ and aₖ₋₁.
- Substituting into the recurrence gives aₖ₊₁ = 2k² − (k − 1)² + 2 = (k + 1)².
- For a recurrence depending on the previous two terms, both initial values a₀ and a₁ must be established before the step can prove later cases.
- Checking the dependency structure reveals whether the induction can start without relying on an unproven case.
- More irregular recurrences, such as one referencing an index near n/3, can make the required base cases less obvious.
- The Fibonacci recurrence is f₀ = 0, f₁ = 1, and fₙ = fₙ₋₁ + fₙ₋₂ for n ≥ 2.
- Binet's formula uses φ = (1 + √5)/2 and ψ = (1 − √5)/2 to express fₙ as (φⁿ − ψⁿ)/√5.
- Both φ and ψ satisfy x² = x + 1, as follows from solving x² − x − 1 = 0.
- The proof checks n = 0 and n = 1, then assumes the formula for fₖ and fₖ₋₁.
- Using the Fibonacci recurrence combines the two assumed expressions into powers of φ and ψ.
- The identities φ² = φ + 1 and ψ² = ψ + 1 reduce the result to the claimed expression for fₖ₊₁.
- A bar contains n unit squares, and each cut must split one piece into exactly two pieces.
- The claim is that producing all individual squares takes n − 1 cuts, regardless of the bar's shape.
- The proof must establish a lower bound, not merely give an example of a way to make the cuts.
- The base case is a one-square bar, which requires zero cuts.
- A first cut splits a bar of size k + 1 into pieces of sizes i and j, where i + j = k + 1 and both sizes are smaller.
- By strong induction, those pieces require at least i − 1 and j − 1 more cuts, so the total is 1 + (i − 1) + (j − 1) = k.
- Cutting off individual squares one at a time achieves the same count, so n − 1 is both necessary and sufficient.
- The fundamental theorem of arithmetic states that every integer n ≥ 2 has a unique factorization into primes.
- The lecture proves existence of a prime product, while reserving uniqueness for later number-theory tools.
- Examples include 60 = 2² · 3 · 5 and 75 = 3 · 5².
- The base case n = 2 is prime, so it is already a product consisting of one prime factor.
- For k + 1 prime, the claim holds directly; for k + 1 composite, write it as ab with 2 ≤ a, b ≤ k.
- The inductive hypothesis factors a and b into primes, and combining those products factors k + 1.
- This argument proves existence only; it does not establish that the prime factorization is unique.
- Structural induction proves claims about objects by assuming the claim for smaller objects from which the object can be built or reduced.
- A graph consists of vertices and edges, with each edge joining two vertices; the examples exclude self-loops and multiple edges.
- A connected graph has a path between every pair of vertices, while an acyclic graph contains no cycle.
- The claim is that a connected acyclic graph with n vertices has n − 1 edges.
- The base case is a single vertex with zero edges.
- Deleting an edge from a connected acyclic graph splits it into two smaller connected acyclic graphs with i and j vertices, where i + j = n.
- The smaller graphs have i − 1 and j − 1 edges, and restoring the deleted edge gives i − 1 + j − 1 + 1 = n − 1.
- The lecture restricts attention to polyhedra drawable on a sphere, with each face having at least three sides.
- A tetrahedron has 4 vertices, 6 edges, and 4 faces; a square pyramid has 5, 8, and 5; a cube has 8, 12, and 6.
- Each example satisfies V − E + F = 2, motivating the claim that every valid polyhedron obeys Euler's formula.
- The smallest valid polyhedron is the tetrahedron, which supplies the structural-induction base case.
- Structural induction assumes V − E + F = 2 for every smaller valid polyhedron.
- Deleting an edge keeps the vertex count unchanged, reduces the edge count by one, and merges two faces into one.
- The reduced polyhedron therefore has V′ = V, E′ = E − 1, and F′ = F − 1.
- Substitution preserves the expression: V′ − E′ + F′ = V − (E − 1) + (F − 1) = V − E + F = 2.
Transcript excerpt
0:00 All right, let's get started. Uh, the topic of today is strong induction. Recall the a normal principle of mathematical induction for a predicate defined over the natural numbers five. If you can prove five zero and for all k that 5k must imply 5k + 1 then from there you may conclude that for all n 5n right the classic analogy is that if you have a sequence of dominoes uh and one knocks over the next uh if the first if the kth domino falls over
0:48 and it knocks over the kith plus one domino and the fact that the k the zerooth domino falls over you should [clears throat] be able to conclude clude uh that all the dominoes are going to fall over. Um in contrast, strong induction proofs uh require something like this. Zero five of zero must be true. And I'll put an asterisk here and you'll see why. uh and for all k um uh five of zero and and five of k imply uh 5k + one and then from that you may conclude for all n 5n. So the difference between strong induction and normal induction and it's not the s sense that normal induction is weak or anything like that but you get a
1:36 much more powerful inductive hypothesis in the sense you don't just get to assume the kith dominoes fall over you get to actually assume all the previous dominoes fall over before the k plus one and that uh relationship makes the will make certain problems very simple to do via strong induction. When you have an arrangement of dominoes in a line, it's kind of obvious one will knock over the next. But perhaps you arrange them in a way that's not necessarily a line. And
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Abrahim Ladha.