Mathematical Induction Steps

Why This Matters

Mathematical induction is one of the most powerful proof techniques in Discrete Mathematics, and it shows up consistently on exams. You'll see it in multiple choice questions testing your understanding of the logic and in free-response questions requiring complete proofs. The technique connects directly to foundational concepts like recursion, well-ordering of natural numbers, and logical implication, which makes it essential for understanding algorithm correctness, recursive definitions, and combinatorial identities.

What you're really being tested on is not just whether you can execute the mechanical steps, but whether you understand why each step is necessary and how they work together. The inductive step isn't magic. It's a logical domino effect: you prove the first domino falls, then prove that any falling domino knocks over the next one. Don't just memorize the template; know what logical principle each step demonstrates and what goes wrong when any step is missing or incorrectly executed.

---

The Foundation: Setting Up Your Proof

Before you can prove anything, you need absolute clarity about what you're proving and where you're starting. These setup steps prevent the most common errors students make on exams.

Step 1: State the Property P(n)

• Define P(n) as a precise predicate. It's a statement that takes a natural number as input and evaluates to true or false for each value.
• Specify your starting point $n_0$ explicitly. This is typically 0 or 1, but some problems require $n_0 = 2$ or higher.
• Use unambiguous mathematical notation. Vague language like "the formula works" will cost you points. Write exactly what equality or inequality you're claiming.

For example, if you're proving the sum of the first $n$ positive integers, your predicate should be: "Let $P(n)$ be the statement $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$." That's specific and testable for any given $n$.

Step 2: Establish the Base Case

• Verify $P(n_0)$ directly by substituting your starting value and showing the statement holds through calculation.
• Never skip this step, even if it seems trivial. A proof without a base case proves nothing (the dominos never start falling).
• Show your work explicitly. If $P(1)$ claims $\sum_{i=1}^{1} i = \frac{1(2)}{2}$, write out that $1 = 1$. That single line of verification is what earns you the points.

---

The Engine: The Inductive Argument

This is where the actual proving happens. The inductive hypothesis and inductive step work together to create an infinite chain of implications: $P(n_0) \Rightarrow P(n_0+1) \Rightarrow P(n_0+2) \Rightarrow \ldots$

Combined with the base case (which establishes that $P(n_0)$ is true), this chain guarantees every $P(n)$ in the sequence is true.

Step 3: State the Inductive Hypothesis

• Assume $P(k)$ holds for an arbitrary fixed $k \geq n_0$. This is your "given" information for the next step.
• This is an assumption, not a claim. You're not asserting $P(k)$ is universally true. You're setting up a conditional argument: if $P(k)$ is true, then $P(k+1)$ must follow.
• Write it out completely. If proving a summation formula, write the full equation you're assuming: "Assume $\sum_{i=1}^{k} i = \frac{k(k+1)}{2}$ for some arbitrary $k \geq 1$."

Step 4: Prove the Inductive Step

This is the heart of the proof. You need to show that $P(k) \Rightarrow P(k+1)$.

Here's a reliable process for summation-style proofs:

1. Write out what $P(k+1)$ claims. For the running example, that's $\sum_{i=1}^{k+1} i = \frac{(k+1)(k+2)}{2}$.
2. Start with the left-hand side of $P(k+1)$ and split off the last term: $\sum_{i=1}^{k+1} i = \left(\sum_{i=1}^{k} i\right) + (k+1)$.
3. Apply the inductive hypothesis to replace $\sum_{i=1}^{k} i$ with $\frac{k(k+1)}{2}$. This is the critical substitution. Mark it clearly (write "by I.H." or underline it). Graders look for this.
4. Simplify algebraically until you reach the right-hand side of $P(k+1)$: $\frac{k(k+1)}{2} + (k+1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}$.

If your inductive step never references your hypothesis, something is wrong. Go back and look for where the assumed result should plug in.

---

The Conclusion: Sealing the Proof

The final step invokes the formal principle that makes everything click together logically.

Step 5: State the Conclusion

• Invoke the Principle of Mathematical Induction explicitly. Write something like: "By the principle of mathematical induction, $P(n)$ holds for all $n \geq n_0$."
• Reference both completed components. Your conclusion's validity rests on both the base case being true and the implication being proven.
• Match your conclusion to your original claim. If you started with $n_0 = 1$, conclude "for all $n \geq 1$," not "for all natural numbers" (which might include 0, depending on convention).

---

Quick Reference Table

---

Self-Check Questions

1. What is the logical difference between Step 3 (stating the inductive hypothesis) and Step 4 (proving the inductive step)? Which requires proof and which is assumed?

2. A classmate writes a "proof" by induction but never verifies the base case. They correctly prove $P(k) \Rightarrow P(k+1)$. Why is their proof invalid? Try constructing a false statement where this flawed approach would appear to "work." (Hint: consider a predicate like "$n = n + 1$" or try a formula that fails at $n = 1$ but whose inductive step goes through algebraically.)

3. Compare the roles of $k$ and $k+1$ in the inductive step. Why must $k$ be arbitrary rather than a specific value like $k = 5$?

4. If you're proving a property for all integers $n \geq 3$, what must your base case verify? How would your conclusion statement differ from a proof starting at $n = 1$?

5. In the inductive step for proving $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$, identify exactly where the inductive hypothesis gets used when showing $P(k) \Rightarrow P(k+1)$.