CS2050 L07 Proof by Induction
Watch on YouTube →
Overview
Abrahim Ladha presents mathematical induction as a proof method over the natural numbers: establish a base case, then prove that an arbitrary case k implies case k + 1. Worked examples apply the method to sums, convex polygon angles, divisibility, and recursive tromino tilings, while counterexamples expose why a missing base case or a broken inductive step invalidates a proof.
Key takeaways
- A standard induction proof over natural numbers needs a true base case and a valid implication from an arbitrary case k to k + 1; the domino analogy captures why both are necessary.
- The induction hypothesis becomes useful when the target at k + 1 can be rewritten to contain the case k, as in the sum identities and the divisibility proof for 4ⁿ − 1.
- Induction can prove geometric results by changing the structure of an object: a diagonal reduces a convex (k + 1)-gon to a triangle plus a convex k-gon.
- Recursive tromino tilings rely on carefully shaping smaller subproblems: a central L-tromino creates three smaller boards with one missing corner, allowing the induction hypothesis to apply.
- The horse-color fallacy fails specifically at the transition from one horse to two because the proposed overlapping groups share no horse.
- A plausible inductive step cannot establish a theorem without a valid base case; the claim that n(n + 1) is odd fails because consecutive integers have an even product.
Chapters
- For a predicate φ on natural numbers, prove φ(0) and prove φ(k) implies φ(k + 1) for arbitrary k, then conclude φ(n) for all n.
- The domino analogy separates the proof's two requirements: one domino must fall, and each falling domino must knock over the next.
- Ladha notes that this principle is for a one-way sequence such as the natural numbers, not an unrestricted induction over the integers.
- In the inductive step, k is arbitrary and local to the step; assuming φ(k) is not the same as assuming the desired result for every n.
- The proof does not list infinitely many cases: it establishes a reusable implication from one case to its successor.
- A complete induction proof identifies the variable of induction, states the base case, names the induction hypothesis, and shows the next case.
- Ladha proves Σ(i = 1 to n) i = n(n + 1)/2, beginning at n = 1 because the sum is defined there.
- For the inductive step, he writes the sum through k + 1 as the sum through k plus the new final term k + 1.
- Substituting the hypothesis k(k + 1)/2 reduces the problem to algebra that yields (k + 1)(k + 2)/2.
- The target identity is Σ(i = 1 to n) i² = n(n + 1)(2n + 1)/6, with n = 1 checked directly.
- The induction step separates the final square: the sum through k + 1 equals the sum through k plus (k + 1)².
- Replacing the partial sum with k(k + 1)(2k + 1)/6 and factoring the resulting numerator produces (k + 1)(k + 2)(2k + 3)/6.
- Ladha proves Σ(i = 1 to n) i³ = [n(n + 1)/2]², using the previously established formula for the sum of integers as context.
- The base case n = 1 gives 1³ = [1(2)/2]².
- For k + 1, he adds (k + 1)³ to the assumed sum k²(k + 1)²/4 and factors to obtain (k + 1)²(k + 2)²/4.
- The theorem states that a convex n-gon has interior-angle sum (n − 2) × 180°; the triangle case n = 3 supplies the base case.
- Convexity matters because drawing an interior diagonal can divide a convex polygon into smaller convex polygons.
- The inductive step targets every convex (k + 1)-gon, rather than a specific polygon such as a heptagon.
- A diagonal from A1 to A3 splits a convex (k + 1)-gon into a triangle and a convex k-gon.
- The triangle contributes 180°, while the induction hypothesis gives the k-gon an angle sum of (k − 2) × 180°.
- Adding the two parts gives (k − 1) × 180°, which is the required formula for a (k + 1)-gon.
- Ladha defines a divides b to mean there exists an integer c such that ac = b.
- The definition explains why every n divides 0, by choosing c = 0, and why 1 divides every n, by choosing c = n.
- This factor-based relation is distinct from calculator division and remains meaningful when the dividend is zero.
- The claim is that 3 divides 4ⁿ − 1 for every n ≥ 0; the base case uses 4⁰ − 1 = 0.
- Assuming 3 divides 4ᵏ − 1 gives 4ᵏ = 3c + 1 for some integer c.
- Then 4ᵏ⁺¹ − 1 = 4(3c + 1) − 1 = 3(4c + 1), establishing divisibility for the next exponent.
- The first tiling theorem concerns a 2ⁿ-by-2ⁿ board with one quadrant missing, tiled using L-shaped trominoes made of three squares.
- For n = 1, the 2-by-2 board has three remaining squares, exactly one tromino.
- The recursive goal is to turn a board of order k + 1 into smaller boards of order k that satisfy the induction hypothesis.
- Divide the 2ᵏ⁺¹-by-2ᵏ⁺¹ board into four quadrants, each a 2ᵏ-by-2ᵏ board.
- Place a central L-shaped tromino across the three quadrants that do not contain the original missing quadrant, creating one missing corner in each.
- Each quadrant now fits the induction hypothesis, so their tilings combine into a tiling of the full board without gaps or overlaps.
- The stronger theorem says any 2ⁿ-by-2ⁿ board with one square missing can be tiled by L-shaped trominoes.
- Its base case is a 2-by-2 board with one square removed, leaving exactly one tromino-shaped region.
- The missing square lies in one of four quadrants; symmetry can reduce the discussion to one placement, provided the proof states that assumption.
- One proof applies the earlier quadrant-missing theorem to tile a larger region, then uses the induction hypothesis on the remaining board sections.
- A direct construction tiles the quadrant containing the missing square by induction and places one central tromino over squares in the other three quadrants.
- Those three quadrants then each have a single square missing, so the induction hypothesis tiles all four sections.
- The false claim that all horses have the same color appears to work by comparing two overlapping groups of k horses within a group of k + 1.
- The argument fails when moving from k = 1 to k = 2: the two one-horse groups do not overlap, so there is no shared horse to connect their colors.
- This example shows that an inductive step must work at the first transition after the base case, not merely for larger values of k.
- Ladha gives a deliberately false claim that n(n + 1) is odd, even though consecutive integers have an even product.
- An algebraic argument can appear to carry an assumed case forward, but the base case is false and the chain of implications never starts.
- A valid induction proof needs both a verified base case and a correct inductive step; either component alone is insufficient.
Transcript excerpt
0:01 So this is uh CS uh 2050 and the topic of today is a technique called proof by induction. Induction is not simply a proof technique as we'll do it in this class. It is a proof technique but it is also like an entire way of thinking and is an entire form of like a kind of structuralism. It's like um it's a specific way once we do several examples of induction you'll understand what it means for a property to be inductive or to think inductively and and things like this. Most formally there is a statement of induction which is for fi a predicate uh of the natural numbers
0:53 and this is important. And it does not work for integers or anything. So 0 1 and so on. We state that uh if five of 0 is true and if for all k five of k implies five of k + one is true from this we may deduce uh for all n fi of n. So this is known as the statement of induction. There are several parts to it and an induction proof like a proof by contra uh contradiction or and things will have a kind of syntax that needs to be followed. There is what's known as the base case and then you do what's known as the inductive step
1:45 and in the inducted step you get to assume the induct induction hypothesis. And then if you can just show assuming an induction hypothesis that the next one must follow then from that that's all you have to do to show for all n5 of n right. So let me give you intuition and talk about the logic of this statement. Essentially you can think of uh these two parts as uh the natural
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.