3  Proof by Induction

Modified

February 25, 2026

This section recalls numerical induction and introduces structural induction. These techniques will be crucial to design and analysis of algorithms throughout the course, particularly with Divide and Conquer, Graph Traversal, and Dynamic Programming.

Objectives. After learning this material, you should be able to:

3.1 Numerical Induction

In past courses, you have seen numerical induction. This is a method to prove a statement of the form “for all \(n\), \(P(n)\) is true.” Here is an example.

Recall that the Fibonacci numbers are defined as \(F_0 = 0\), \(F_1 = 1\), and \(F_n = F_{n-1} + F_{n-2}\) for \(n \geq 2\). The first few are 0,1,1,2,3,5,8,13,…

Exercise 3.1 Prove by induction that \(F_n \leq 2^n\).

Example solution.

The first base case is \(n=0\). In this case, \(F_0 = 0 \leq 1 = 2^0\). The second base case is \(n=1\). In this case, \(F_1 = 1 \leq 2 = 2^1\).

For the inductive step, let \(n \geq 2\). The inductive hypothesis (IH) is that for all \(k < n\), we have \(F_k \leq 2^k\). Using the IH: \[\begin{align*} F_n &= F_{n-1} + F_{n-2} & \text{definition} \\ &\leq 2^{n-1} + F_{n-2} & \text{by IH} \\ &\leq 2^{n-1} + 2^{n-2} & \text{by IH} \\ &\leq 2^{n-1} + 2^{n-1} \\ &= 2 \left(2^{n-1} \right) \\ &= 2^{n}. \end{align*}\] We have proven that \(F_n \leq 2^n\). This completes the proof by induction.

Note: strong induction. The previous example is actually called “strong” induction. This is because, in order to prove the statement for \(n\), we needed to assume it was true for all \(k < n\). In contrast, weak induction only uses the inductive hypothesis that the statement is true for \(k=n-1\). However, the distinction between strong and weak induction will not be very important for this class; they are both proofs by induction.

Checking your familiarity. In order to tackle the next portion of the class, you should be comfortable with the following type of example. Can you solve it?

Exercise 3.2 Prove by induction that the sum of the first \(n\) odd numbers is equal to \(n^2\).

3.2 “Non-numerical” induction

You probably also have used induction to prove facts that are not just numerical equalities or inequalities. Here is an example. Recall that a prime factorization of an integer is a list of prime numbers whose product equals the integer.

Exercise 3.3 Prove by induction that every integer \(n \geq 2\) has a prime factorization.

Example solution.

The base case is \(n=2\). This has the prime factorization \(2\).

For the inductive step, assume that every \(k < n\) has a prime factorization. We must prove this holds for \(n\) as well. There are two cases: \(n\) is prime, or \(n\) is composite. If \(n\) is prime, then it has the prime factorization \(n\), so we are done. If \(n\) is compsite, then \(n = ab\) for \(a,b \in \{2,\dots,n-1\}\). By inductive hypothesis, \(a\) and \(b\) each have a prime factorization. Multiplying them together gives a prime factorization of \(n\).

3.3 Structural Induction

We will often deal with “structures” such as strings, graphs, and trees. Many of our algorithms’ correctness and runtime guarantees will be proven by a type of induction. We will begin with an example.

Definition 3.1 (String) Given a finite set \(X\), called the alphabet, whose elements are called characters, a string is either:

  • the empty string ““; or
  • a character followed by a string.

For example, we can take the alphabet to the be 26 lowercase English letters, in which case a string would be all lists consisting of these letters, including the empty string.

The length \(len(s)\) of a string \(s\) is defined inductively: if \(s\) is empty, its length is zero. If \(s\) consists of \(c\) followed by a string \(s'\), its length is \(1 + len(s')\).

Proposition 3.1 Let \(m = |X|\), the size of the alphabet. Then there are \(m^t\) different strings of length \(t\).

Proof (Proof by induction). The base case is when \(t=0\), i.e. the string has length zero. In this case, it is the empty string, and there is only one empty string, so the number of strings is \(1 = m^0\), so the formula is correct.

For the inductive case, fix \(t \geq 1\) and suppose the claim is true for all \(k < t\). A string of length \(t\) is of the form \(cs'\), where \(c\) is a character and \(s'\) is a string of length \(t-1\). By inductive hypothesis, there are \(m^{t-1}\) possible strings \(s'\). For each \(s'\), we get a different string of length \(t\) by prepending each of the \(m\) possible characters. So there are \(m \cdot m^{t-1} = m^t\) possible strings of length \(t\).

3.3.1 Binary trees

Here is another example of structural induction.

Definition 3.2 (Binary tree) A binary tree is either:

  • a single node with no children, called a leaf; or
  • a node with at most two children, each of which is a binary tree.

The root of a binary tree is the node that is not a child of any other node. The height of a binary tree is the length of the longest path from the root to any leaf.

Proposition 3.2 A binary tree of height \(h\) has at most \(2^{h+1} - 1\) nodes.

Proof. The base case is a leaf node, i.e. a tree of height \(0\). The number of nodes is \(1 = 2^{0+1} - 1\), as needed.

Now let \(h \geq 1\) and suppose the claim holds for all \(k < h\). Consider a binary tree of height \(h\). The root has at most two children. Each child is the root of a binary tree of height at most \(h-1\). So by inductive hypothesis, there are most \(2^{h} - 1\) nodes in each subtree. Adding them together gives an upper bound of \(2(2^{h} - 1) = 2^{h+1} - 2\) nodes. Adding the root node gives an upper bound of \(2^{h+1} - 1\) nodes, proving the claim.