The Traditional Order
Many students have difficulty knowing where to start with a proof by induction. I saw this problem all the time while I was teaching CPSC 121, the introductory logic course at UBC. Typically, textbooks teach you to write your base case (or base cases) first, then write your inductive step, like the following:
$\textbf{Base Case / Cases}$
Prove that the proposition $\textnormal{P}(n)$ holds true for specific value of $n$, often $n = 1$.
$\textbf{Inductive Step}$
Prove that if the proposition $\textnormal{P}(n)$ holds true when $n$ is equal to some constant $k$, then it follows that $\textnormal{P}(n)$ will also hold true when $n=k+1$.
There’s nothing wrong with writing inductive proofs in this order. However, while you need both the base case and the inductive step to make a complete inductive proof, the order you write them in doesn’t affect the correctness of the proof.
After reading this post, you should feel comfortable writing proofs by induction in the order of inductive step first, followed by base cases. You should be able to use this method of writing proofs to identify the correct base cases in problems where it is not clear how many or which base cases are necessary.
A Self-Inflicted Difficulty
It’s easy to get into the habit of writing the base case first. After all, that part of the inductive proof often contains the easiest math (and hence the easiest marks). But, when students try to write the base cases before the inductive step, they often run into a problem: it can be non-obvious which base cases, or how many base cases, are required.
Worse still, starting their work on the inductive step from a less-than-ideal set of base cases can needlessly make writing the inductive step difficult or impossible.
The Hot Dog Question
Let’s consider the “hot dog” question, whose name exaggerates and parodies the nonsensical quantities of hot dogs historically sold in Canadian stores. One example of the question is as follows:
- At the store, you can purchase hot dogs in packages of exactly 4, 7, 9, or 13 hot dogs; and,
- You can purchase as many packages of each size as you like, but there are no other package sizes.
- Prove you can purchase any integer number of hot dogs greater than or equal to 11.
Seeing than we’re making a statement about “any integer greater than or equal to…” is an instant clue that we’re looking at an inductive proof. Let’s walk through how this proof might look if we begin by writing a base case:
$\textbf{Base Case}$
I $\textit{need to show}$ that I can purchase $n=11$ hot dogs.
I can purchase one package of 4 and one package of 7 ($4 + 7 = 11$).
So far so good. But, watch how convoluted the proof becomes as we attempt to write an inductive step:
$\textbf{Inductive Step}$
Assume I can purchase $k$ hot dogs for some constant $k \in \mathbb{Z} \ge 11$.
I $\textit{need to show}$ that I can purchase $k+1$ hot dogs.
Start by getting all that packages I need to purchase $k$ hot dogs, which I know I can do by assumption. If I have a package of 7 hot dogs (which is not guaranteed), then I can put it back on the shelf and then pick up two packages of 4, giving me $k-7+4+4 = k+1$ hot dogs. But, if I don’t have a package of 7, then…$\textbf{(umm, uh oh)}$.
The inductive step quickly breaks down into a collection of confusing cases. During an exam, that translates to a lot of wasted time and effort. Note: the proof could still be completed as we started it above; but, forcing an inductive proof to fit the traditional ordering can make it very difficult and time-consuming to complete correctly.
Flipping Your Approach
Instead, let’s see what happens if we write our inductive step first. This approach frees us to focus on what we can prove more easily. Let’s consider a simpler inductive step:
$\textbf{Inductive Step}$
Assume I can purchase $k$ hot dogs for some constant $k \in \mathbb{Z} \ge 11$.
I $\textit{need to show}$ that I can purchase $\boldsymbol{k+4}$ hot dogs.
Start by getting all the packages I need to purchase $k$ hot dogs, which I can do by assumption. Purchase an additional package of 4 hot dogs, bringing my purchase to $k+4$ hot dogs.
So, if we can purchase k hot dogs, it follows that we’re able to purchase k+4 hot dogs. This inductive step was easy to prove by considering k+4 instead of k+1.
Now, we just need base cases to start our chains of inductive reasoning. Let’s consider what happens when we show a single base case:
$\textbf{Base Case}~\boldsymbol{(n = 11)}$
I $\textit{need to show}$ that I can purchase $n=11$ hot dogs.
I can purchase one package of 4 and one package of 7 ($4 + 7 = 11$).
By combining this single base case with the statement of the inductive step, we’ve shown:
- As an unqualified fact, we can purchase 11 hot dogs [base case]
- If we can purchase 11 hot dogs, then it follows that we can purchase 15 [inductive step]
- If we can purchase 15 hot dogs, then it follows that we can purchase 19 [inductive step]
- If we can purchase 19 hot dogs, then it follows that we can purchase 23 [inductive step]
- […]
Noting the Missing Base Cases
Note what’s missing in this chain of reasoning. We haven’t shown that we can purchase 12 hot dogs, nor that we can purchase 16, 20, nor 24.
Similarly, we haven’t shown that we can purchase 13 hot dogs (nor 17, 21, nor 25). We also haven’t shown that we can purchase 14 hot dogs (nor 18, 22, nor 26).
The trick to knowing how many base cases you need comes from looking at the wording of what we proved in the inductive step: if we can purchase k hot dogs, then we can purchase k+4. Because our inductive step works in increments of 4, we need 4 different launching points (i.e., base cases) for our chains of inductive reasoning.
Completing the inductive step before worrying about your base cases can demonstrate to you, while you’re designing your proof, which base cases and how many base cases you’ll need.
Bringing it All Together
Now that we’ve seen how completing the inductive step first reveals that we need four base cases as launching points for our inductive reasoning, let’s show a complete proof of our hot dog problem.
Question: You can purchase hot dogs only in packages of 4, 7, 9, or 13. Prove you can purchase any number of hot dogs $n$, where $n \in \mathbb{Z} \ge 11$.
Answer:
$\textbf{Inductive Step}$
Assume I can purchase $k$ hot dogs for some constant $k \in \mathbb{Z} \ge 11$.
I $\textit{need to show}$ that I can purchase $\boldsymbol{k+4}$ hot dogs.
Start by getting all the packages I need to purchase $k$ hot dogs, which I can do by assumption. Purchase an additional package of 4 hot dogs, bringing my purchase to $k+4$ hot dogs.
$\textbf{Base Case}~\boldsymbol{(n = 11)}$
I $\textit{need to show}$ that I can purchase $n=11$ hot dogs.
I can purchase one package of 4 and one package of 7 ($4 + 7 = 11$).
$\textbf{Base Case}~\boldsymbol{(n = 12)}$
I $\textit{need to show}$ that I can purchase $n=12$ hot dogs.
I can purchase three packages of 4 hot dogs ($3 \cdot 4 = 12$).
$\textbf{Base Case}~\boldsymbol{(n = 13)}$
I $\textit{need to show}$ that I can purchase $n=13$ hot dogs.
I can trivially purchase one package of exactly 13 hot dogs.
$\textbf{Base Case}~\boldsymbol{(n = 14)}$
I $\textit{need to show}$ that I can purchase $n=14$ hot dogs.
I can purchase two packages of 7 hot dogs ($2 \cdot 7 = 14$).
Summary
A proof by induction consists of an inductive step, as well as one or more base cases. Most textbooks show the base case written before the inductive step, and writing your inductive proofs that way will probably become a habit for simpler proofs.
But, the order in which you write those two parts of a proof doesn’t affect the correctness of your proof. Writing your inductive step first can be a powerful tool to help you design simpler proofs which are more likely to be correct. Starting with the inductive step is an approach I encourage all my students to try, particularly if they’re finding it difficult to know where to begin on an inductive proof.
For more tips, and to arrange for personalized tutoring for yourself or your study group, check out Vancouver Computer Science Tutoring.