Standard 4: Divide and Conquer 1: Induction

Short description: Prove theorems by numerical and/or structural induction.

Relevant notes: Topic B: Divide and Conquer.

Full description

Prove claims by induction. Claims can be numerical, such as equalities and inequalities; other types of facts, such as properties of numbers or objects; or structural, such as claims about inductively-defined objects like strings and trees.

Example problem

Part a. Let $F_n$ be the $n$th Fibonacci number. Prove by induction that $F_n \leq 2^n$ for all $n$.

Part b. Prove by induction that a binary tree of height $h$ has at most $2^{h+1} - 1$ nodes.

Sample solution

Part a.

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 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, using the inductive hypothesis, that $F_n \leq 2^n$, as required. This completes the proof by induction.

Part b.

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.

Rubric

Rubric.

Both parts of the problem must be passed successfully for the problem to be a pass.

To pass, a solution must follow the course requirements for writing and proofs.

Inductive proofs, here and throughout the course, should always meet the following requirements:

The inductive structure should be clear from context or clearly stated if not. What is being inducted on? What are the base case(s) and inductive case(s).
The base cases should be stated and proven.
The inductive case should be stated and proven. It should be clear what the inductive hypothesis is and how it is used.

For Part a, in particular we should remember to state that the inductive step applies to $n \geq 2$. For Part b, we should in particular use the inductive structure of the definition of a binary tree to note that the root has two children of height at most $h-1$.

The numerical rubric for this problem is:

4 (Pass, Near-Perfect): perfectly clear, no arithmetic mistakes, all steps of solution included, no excess writing.
3 (Pass, Proficient): clear, easy to follow, generally correct arithmetic with perhaps inconsequential mistakes, little to no excess writing or unnecessary scratch work.
2 (Fail, Progress): may have consequential arithmetic mistakes. May skip major steps without justifying them. May include confusing or excess scratch work. May omit key components of a proof by induction, e.g. be missing a base case or not fully prove the inductive case. May not be clear how the inductive hypothesis is used.
1 (Fail, Wrong Track): Does not follow the structure of a proof by induction correctly. E.g., fails to separate base and inductive steps or fails to use the inductive structure of a binary tree in Part b.