Difficulty: Intermediate to Advanced | Prerequisites: Basic induction (see Part 2 notes), matrix multiplication, logarithm properties
This set of notes covers three less routine variants of induction: strong induction (where the hypothesis covers all values up to k, not just k itself), induction on an inequality rather than an equality, and induction involving matrix exponentiation. These appear in discrete maths exams and, more importantly, in algorithm design: strong induction mirrors how recursive algorithms call on smaller sub-problems, inequality induction is the tool behind runtime bounds, and matrix induction connects to fast computation of linear recurrences. If you are comfortable with ordinary induction on equalities, you are ready for this material.
Strong induction lets you assume the statement for every value from the base case up to k, which is essential when the inductive step needs to jump back more than one position. Inequality induction requires careful direction management (do not accidentally flip the inequality). Matrix induction multiplies both sides by the base matrix and uses the hypothesis to simplify.
Strong induction
A variant of induction where the inductive hypothesis assumes the statement holds for all integers from the base case up to k (not just for k alone). In simple terms, you get to use every earlier case, not just the immediately previous one. This is necessary when the problem at n = k+1 depends on cases earlier than n = k.
Partitioning a square
Dividing a square into smaller, non-overlapping squares that tile the entire area with no gaps. This is a classic strong induction problem because going from k squares to k+1 squares requires referencing a case three steps back (k−2).
Inequality induction
Proving that some expression is ≤ or ≥ another for all n. The key difference from equality induction: you work with bounds rather than exact values, and you must ensure every step preserves the direction of the inequality.
Matrix exponentiation
Raising a matrix to the nth power by repeated multiplication. The identity Aⁿ⁺¹ = Aⁿ · A is the inductive engine: if you know Aⁿ in closed form, multiply by A and check that the result matches the closed form for n+1.
Floor / log₂
log₂(i) gives the power of 2 in i. For integers that are not powers of 2, log₂ is not an integer. The sum ∑ log₂(i) counts, roughly, how many bits are needed to represent each index.
This uses strong induction with three base cases.
Base cases:
n = 6: Take a unit square. Partition the right 2/3 into one (2/3)×(2/3) square, and the remaining L-shaped region into five (1/3)×(1/3) squares. Total: 6 squares.
n = 7: Partition a unit square into three (1/2)×(1/2) squares and four (1/4)×(1/4) squares. Total: 7 squares.
n = 8: Partition a unit square into one (3/4)×(3/4) square and seven (1/4)×(1/4) squares. Total: 8 squares.
Inductive hypothesis:
Assume for all integers n with 6 ≤ n ≤ k (where k ≥ 8) that a square can be partitioned into exactly n squares.
Inductive step (prove for k+1):
Since k+1 ≥ 9, we have k−2 ≥ 6. By the IH, a square can be partitioned into k−2 squares.
Take that partition. Pick any one of its squares (say it has side length L).
Subdivide that one square into 4 equal squares, each of side length L/2.
The count changes: remove 1 square, add 4. Net change: +3.
New total: (k−2) − 1 + 4 = k+1 squares.
Why three base cases? The inductive step for k+1 relies on the case k−2. Starting from k+1 = 9, you need k−2 = 6 to be established. So you need 6, 7, and 8 as base cases to cover the first three values that the step cannot reach backwards from.
Base case (n = 1):
LHS: ∑ log₂(i) from i = 1 to 2 = log₂(1) + log₂(2) = 0 + 1 = 1.
RHS: (1−1)·2¹ + 1 = 0 + 1 = 1.
1 ≤ 1 holds.
Inductive hypothesis:
Assume for an arbitrary positive integer k that ∑ log₂(i) from i = 1 to 2ᵏ ≤ (k−1)·2ᵏ + 1.
Inductive step (prove for n = k+1):
Split the sum from 1 to 2ᵏ⁺¹ into two parts:
∑ (i = 1 to 2ᵏ) log₂(i) + ∑ (i = 2ᵏ+1 to 2ᵏ⁺¹) log₂(i)
Apply the IH to the first part: ≤ (k−1)·2ᵏ + 1.
For the second part, note that every i in the range [2ᵏ+1, 2ᵏ⁺¹] satisfies log₂(i) ≤ k+1. There are 2ᵏ terms in this range.
So ∑ (i = 2ᵏ+1 to 2ᵏ⁺¹) log₂(i) ≤ (k+1)·2ᵏ.
Combine: total ≤ (k−1)·2ᵏ + 1 + (k+1)·2ᵏ = [(k−1) + (k+1)]·2ᵏ + 1 = 2k·2ᵏ + 1 = k·2ᵏ⁺¹ + 1.
The target RHS is ((k+1)−1)·2ᵏ⁺¹ + 1 = k·2ᵏ⁺¹ + 1. This matches.
Prove for all non-negative integers n:
$$\begin{pmatrix} 2 & 0 \ 1 & 1 \end{pmatrix}^n = \begin{pmatrix} 2^n & 0 \ 2^n - 1 & 1 \end{pmatrix}$$
Base case (n = 0):
LHS: Any matrix to the power 0 is the identity matrix I = ((1,0),(0,1)).
RHS: ((2⁰, 0),(2⁰−1, 1)) = ((1, 0),(0, 1)).
They match.
Inductive hypothesis:
Assume for an arbitrary non-negative integer k:
((2,0),(1,1))ᵏ = ((2ᵏ, 0),(2ᵏ−1, 1)).
Inductive step (prove for n = k+1):
((2,0),(1,1))ᵏ⁺¹ = ((2,0),(1,1))ᵏ · ((2,0),(1,1))
Apply the IH to the left factor:
= ((2ᵏ, 0),(2ᵏ−1, 1)) · ((2,0),(1,1))
Multiply out:
Top-left: 2ᵏ·2 + 0·1 = 2ᵏ⁺¹
Top-right: 2ᵏ·0 + 0·1 = 0
Bottom-left: (2ᵏ−1)·2 + 1·1 = 2ᵏ⁺¹ − 2 + 1 = 2ᵏ⁺¹ − 1
Bottom-right: (2ᵏ−1)·0 + 1·1 = 1
Result: ((2ᵏ⁺¹, 0),(2ᵏ⁺¹−1, 1)), which is the formula with n = k+1.
Result | Type |
|---|---|
Square → n squares for n ≥ 6 | Strong induction, geometric construction |
∑ log₂(i) (1 to 2ⁿ) ≤ (n−1)·2ⁿ + 1 | Inequality induction |
((2,0),(1,1))ⁿ = ((2ⁿ,0),(2ⁿ−1,1)) | Matrix induction |
The square partition trick: subdividing one square into four adds exactly 3 squares to the count. This "+3" step is the engine of the strong induction proof.
Strong induction mirrors how recursive algorithms work: a function solving a problem of size n might call itself on sizes n−1, n−2, or n−3 simultaneously. The square partitioning problem is a simplified version of rectangle packing, which matters in chip layout design and memory allocation. Matrix exponentiation is used to compute Fibonacci numbers and other linear recurrences in O(log n) time, which is critical in competitive programming and in systems that need to evaluate recurrences for very large n.
Students often try to use ordinary induction (assuming only n = k) for the square partition problem and get stuck. The step requires k−2, so you need strong induction.
In inequality induction, students sometimes write "=" where they should write "≤" and lose the inequality chain. Every line must preserve or tighten the bound, never flip it.
For matrix induction, a common error is multiplying in the wrong order (matrix multiplication is not commutative). Always write Aᵏ⁺¹ = Aᵏ · A with the IH on the left.
Students forget that A⁰ = I (the identity matrix), not A. The base case at n = 0 is the identity, not the matrix itself.
⚠️ Strong induction problems will explicitly say "strong induction" or give you a recurrence that jumps back more than one step. If you see three base cases, that is a strong induction signal.
⚠️ For the square partition proof, examiners expect diagrams with labelled dimensions. Do not submit only algebra; draw the pictures.
⚠️ Matrix induction is a compact proof technique. The examinable skill is performing 2×2 matrix multiplication correctly under exam pressure. Practise until it is mechanical.
⚠️ Inequality proofs: clearly state where the inequality enters (usually when you apply the IH or bound a sub-expression). Examiners mark for this.
True or False: Strong induction assumes the statement for only n = k.
Fill in the blank: Subdividing one square in a partition into four equal squares changes the total count by ______.
True or False: ((2,0),(1,1))⁰ = ((2,0),(1,1)).
Fill in the blank: In the inequality induction, the sum from 2ᵏ+1 to 2ᵏ⁺¹ has exactly ______ terms.
True or False: The square partition proof requires exactly three base cases because the inductive step references the case n = k−2.
Answers: 1. False (it assumes for all values from the base case up to k). 2. +3 (remove 1, add 4). 3. False (it equals the identity matrix). 4. 2ᵏ terms. 5. True.
Q: Why does the square partition proof need the cases n = 6, 7, and 8 specifically?
A: The inductive step for n = k+1 calls on the case n = k−2. The smallest value of k+1 we need to prove is 9 (the first value not covered by base cases), which requires k−2 = 6. Working backwards: 9 needs 6, 10 needs 7, 11 needs 8. From 12 onward, k−2 ≥ 9, which is already proved by the inductive step itself.
Q: In the matrix induction, what is the bottom-left entry of ((2ᵏ,0),(2ᵏ−1,1)) · ((2,0),(1,1))?
A: (2ᵏ−1)·2 + 1·1 = 2ᵏ⁺¹ − 2 + 1 = 2ᵏ⁺¹ − 1.
Q: How would the inequality proof break if the bound on the second partial sum were too loose?
A: If you bounded ∑ log₂(i) for i in [2ᵏ+1, 2ᵏ⁺¹] by something larger than (k+1)·2ᵏ, the final combined bound would exceed (k)·2ᵏ⁺¹ + 1, and the inductive step would fail. The bound must be tight enough to land on the target.
Q: Verify that the matrix formula holds at n = 2 by direct computation.
A: ((2,0),(1,1))² = ((2,0),(1,1))·((2,0),(1,1)) = ((4,0),(3,1)). The formula gives ((2²,0),(2²−1,1)) = ((4,0),(3,1)). They match.
Strong induction connects to structural induction on trees and recursive data structures, which you will encounter in data structures and algorithms courses. Matrix induction ties back to the recurrence relation in Q3 of this homework: the fast matrix exponentiation method for computing g(n) relies on exactly this kind of identity. The inequality proof technique is the foundation for proving Big-O and Big-Theta bounds rigorously.
strong induction, multiple base cases, square partitioning, tiling, inequality induction, upper bound proof, matrix exponentiation, matrix induction, matrix power, identity matrix, log sum, logarithm inequality, 2x2 matrix multiplication, COT 3100, discrete mathematics, UCF, proof technique, recursive structure