Chapter 7: Induction

Source files used: Intro_ocw (Lecture 1 notes, greedy proofs on pages 5A and 5B), Medians_induction (Lecture 2 notes, page 10), Matrix Multiplication (Recitation 1, Section 3.3), MIT6_046JS15_pset1 (Problem 1-1 as practice); textbook Chapter 4 (chap4, Section 4.3) as support. No worked examples are included.

1. Big Picture

Induction is the proof engine of the course. It shows up in two places:

• correctness: proving a greedy algorithm is optimal (interval scheduling),
• running time: proving a guessed bound for a recurrence (the substitution method, median finding).

The Recurrences guide asked: how do you guess a bound? This guide asks: how do you prove it, and how do you prove an algorithm correct?

$$\boxed{\text{State the exact claim, prove the base case, assume it for smaller cases, prove the next case.}}$$

Every exam proof is graded on the same three parts: base case, inductive hypothesis, inductive step.

---

2. Core Ideas

2.1 Anatomy of an Induction Proof

• Claim $P(n)$: a precise statement with named constants, not $O(\cdot)$.
• Base case: prove $P$ for the smallest values (one value or a range).
• Inductive hypothesis: assume $P$ holds for smaller values.
• Inductive step: use the hypothesis to prove $P$ for the next value.

---

2.2 Strong Induction

For recurrences you usually assume the bound for all $m<n$, not only $n-1$, because the recursion calls sizes like $n/5$ and $7n/10+6$. The recitation states it this way: assume the bound holds for all positive $m<n$.

---

2.3 What to Induct On

• Greedy correctness: induct on the size of the optimal solution ($k^*$ in interval scheduling).
• Recurrence bounds: induct on the input size $n$.

Pick the quantity that shrinks when you remove the first decision or make a recursive call.

---

2.4 Exchange Argument

The core move in greedy proofs: take an optimal solution and swap its first choice for the greedy choice. Show the result is still valid and still optimal. Then the rest of the problem is a smaller instance, where the inductive hypothesis applies.

---

2.5 Substitution Method = Induction on a Recurrence

Textbook definition:

1. Guess the form of the solution using symbolic constants.
2. Use induction to show the guess works, and find the constants.

Prove $O$ and $\Omega$ separately; together they give $\Theta$.

---

3. Main Governing Equations and Formulas

3.1 Greedy Validity (Lecture 1, Claim 1)

Earliest-finish-time greedy outputs

$$s(i_1)<f(i_1)\le s(i_2)<f(i_2)\le\cdots\le s(i_k)<f(i_k)$$

Proof by contradiction: if $f(i_j)>s(i_{j+1})$, intervals $j$ and $j+1$ intersect, contradicting step 2 of the algorithm (reject incompatible requests).

Use to show the output is a legal schedule before arguing optimality.

---

3.2 Greedy Optimality: Statement (Lecture 1, Claim 2)

Given a list of intervals $L$, the greedy algorithm with earliest finish time produces $k^*$ intervals, where $k^*$ is the optimal number.

Proof: induction on $k^*$.

---

3.3 The Exchange Fact

Let the optimal schedule be $S^*=\langle j_1,\dots,j_{k^*+1}\rangle$ and the greedy schedule $S=\langle i_1,\dots,i_k\rangle$. Greedy picks the earliest finish time, so

$$f(i_1)\le f(j_1)$$

Therefore

$$S^{**}=\langle i_1,j_2,j_3,\dots,j_{k^*+1}\rangle$$

is valid ($f(i_1)\le f(j_1)\le s(j_2)$) and also optimal (same size).

---

3.4 Greedy Optimality: Full Proof

1. Base case $k^*=1$: any interval works.
2. Hypothesis: the claim holds for every list whose optimal schedule has $k^*$ intervals.
3. Step: let $L$ have an optimal schedule of $k^*+1$ intervals. Build $S^{**}$ as in Section 3.3.
4. Define $L'$ as the set of intervals with $s(i)\ge f(i_1)$.
5. Since $S^{**}$ is optimal for $L$, $S^{**}[2,\dots,k^*+1]$ is optimal for $L'$ (otherwise adding $i_1$ in front would beat $k^*+1$). So the optimal schedule for $L'$ has size $k^*$.
6. By the inductive hypothesis, greedy on $L'$ produces a schedule of size $k^*$.
7. By construction, greedy on $L'$ produces exactly $S[2,\dots,k]$.
8. So $k-1=k^*$, that is $k=k^*+1$, and $S[1,\dots,k]$ is optimal.

Use this structure for any “prove your greedy algorithm is optimal” question.

---

3.5 Substitution Example: $O(n\lg n)$ (Textbook)

Recurrence $T(n)=2T(\lfloor n/2\rfloor)+\Theta(n)$. Hypothesis: $T(n)\le cn\lg n$ for $n\ge n_0$.

$$T(n)\le2\left(c\left\lfloor\frac{n}{2}\right\rfloor\lg\left\lfloor\frac{n}{2}\right\rfloor\right)+\Theta(n)\le cn\lg\frac{n}{2}+\Theta(n)$$ $$=cn\lg n-cn+\Theta(n)\le cn\lg n$$

The last step needs $c$ large enough that $cn$ dominates the $\Theta(n)$ term.

Base case: $n=1$ fails because $1\lg1=0$. Use $n_0=2$ and pick $c=\max\{T(2),T(3)\}$, which covers $n=2,3$.

---

3.6 Substitution Example: Median Finding (Lecture 2)

Prove $T(n)\le cn$ for $T(n)=T(\lceil n/5\rceil)+T(7n/10+6)+an$:

$$T(n)\le c\left\lceil\frac{n}{5}\right\rceil+c\left(\frac{7n}{10}+6\right)+an\le cn+\left(-\frac{cn}{10}+7c+an\right)$$

The bracket is $\le0$ when $c\ge70c/n+10a$, which holds for $n\ge140$ and $c\ge20a$. Base case $n\le140$: choose $c$ large. Full detail in the Medians guide.

---

3.7 Trick: Subtract a Lower-Order Term (Textbook)

Recurrence $T(n)=2T(n/2)+\Theta(1)$. The guess $T(n)\le cn$ gives

$$T(n)\le2\cdot c\frac{n}{2}+\Theta(1)=cn+\Theta(1)$$

which is not $\le cn$. The guess $O(n)$ is right, but the hypothesis is too weak. Strengthen it to $T(n)\le cn-d$:

$$T(n)\le2\left(c\frac{n}{2}-d\right)+\Theta(1)=cn-d-\big(d-\Theta(1)\big)\le cn-d$$

which holds once $d$ exceeds the constant in $\Theta(1)$.

With several recursive calls, subtracting a term subtracts it once per call, which is why this helps.

---

3.8 Pitfall: Asymptotic Notation in the Hypothesis (Textbook)

A false “proof” that $2T(\lfloor n/2\rfloor)+\Theta(n)=O(n)$:

$$T(n)\le2\cdot O(\lfloor n/2\rfloor)+\Theta(n)=O(n)\qquad\text{(wrong)}$$

The constant hidden in $O$ grows at every level. With explicit constants the step gives $cn+\Theta(n)$, which is not $\le cn$. Rule: name the constants and prove the exact form of the hypothesis.

---

4. Problem-Solving Workflow

4.1 Proving a Greedy Algorithm Correct

1. Prove the output is valid (often by contradiction with the algorithm’s rejection step).
2. State optimality as a claim about the optimal size $k^*$.
3. Base case: smallest $k^*$.
4. Exchange: replace the optimal solution’s first choice with the greedy choice; show it stays valid and optimal.
5. Define the remaining subproblem ($L'$) and show the rest of the exchanged solution is optimal for it.
6. Apply the hypothesis to the subproblem and match it to the greedy output.

Practice: Problem Set 1, Problem 1-1 (c) asks for a simple greedy algorithm and a correctness proof.

4.2 Proving a Recurrence Bound by Substitution

1. Guess the form (recursion tree, similar known recurrence, or loose bounds squeezed together).
2. Write the hypothesis with named constants: $T(n)\le cn\lg n$, not $T(n)=O(n\lg n)$.
3. Assume it for all $m<n$ and substitute into the recurrence.
4. Simplify until you get (hypothesis) minus (something) plus (driving term).
5. Choose constants so the leftover is $\le0$.
6. Handle the base cases by choosing the leading constant large enough.
7. If the step fails by only a lower-order term, subtract a lower-order term from the guess (Section 3.7).

---

5. Decision Rules / Decision Trees

5.1 The Inductive Step Does Not Close

Off by a lower-order term (for example $cn+\Theta(1)$ vs $cn$)? → subtract a lower-order term: $cn-d$

Off by a growing factor (for example $cn+\Theta(n)$ vs $cn$)? → guess is too small: try a larger form

Used $O(\cdot)$ inside the hypothesis? → rewrite with explicit constants

5.2 Base Case Trouble

Bound is $0$ at $n=1$ (like $cn\lg n$)? → start the induction at $n_0=2$ and cover a small range ($n=2,3$)

Recurrence has $+6$ or ceilings? → use a larger base range (the lecture uses $n\le140$)

5.3 Correctness or Running Time?

“Prove the algorithm returns an optimal answer”? → induction on the solution size + exchange argument

“Prove $T(n)=O(g(n))$”? → substitution method on $n$

---

6. Important Tables / Correlations Needed

6.1 Course Induction Proofs

Proof	Induct on	Key step	Source
Greedy interval scheduling optimal	$k^*$	exchange $j_1$ for $i_1$	Lecture 1
Median Select is $O(n)$	$n$	$-cn/10+7c+an\le0$	Lecture 2
Median Select is $O(n)$ (variant)	$n$	$\frac{9}{10}dn+7d+cn\le dn$, $d>10c$	Recitation 1
$2T(n/2)+\Theta(n)$ is $O(n\lg n)$	$n$	$cn\lg n-cn+\Theta(n)$	Textbook 4.3
$2T(n/2)+\Theta(1)$ is $O(n)$	$n$	guess $cn-d$	Textbook 4.3

6.2 Common Mistakes

Mistake	Fix
$O(\cdot)$ in the hypothesis	name the constant $c$
Proving $cn+\Theta(n)=O(n)$ instead of $\le cn$	prove the exact hypothesis
Base case at $n=1$ for $n\lg n$	start at $n_0=2$
Adding a lower-order term to a failing guess	subtract it instead
Forgetting the validity part of a greedy proof	prove compatibility first

---

7. Key Takeaways

• Every induction proof needs a claim, a base case, a hypothesis, and a step.
• Recurrence proofs use strong induction: assume the bound for all $m<n$.
• Greedy proofs induct on the optimal size $k^*$ and use an exchange argument.
• Interval scheduling exchange fact: $f(i_1)\le f(j_1)$, so $S^{**}$ is valid and optimal.
• Substitution: guess with symbolic constants, then prove by induction.
• Never put $O(\cdot)$ in the inductive hypothesis; name the constants.
• Prove the exact form ($\le cn$), not just "$=O(n)$".
• If the step fails by a lower-order term, subtract a lower-order term from the guess.
• For $cn\lg n$, the base case cannot be $n=1$.
• Median proof closes for $n\ge140$ with $c\ge20a$.