Mathematical Induction Steps

Why This Matters

Mathematical induction is one of the most powerful proof techniques you'll encounter in Discrete Mathematics, and it appears consistently on exams—both 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, making it a gateway to understanding algorithm correctness, recursive definitions, and combinatorial identities.

Here's what you're really being tested on: not just whether you can execute the mechanical steps, but whether you understand why each step is necessary and how they work together to form a valid proof. The inductive step isn't magic—it's a logical domino effect. Don't just memorize the template; know what logical principle each step demonstrates and what happens 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—a statement that takes a natural number 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

Step 2: Establish the Base Case

• Verify P($n_0$) directly—substitute your starting value and show the statement holds through calculation or simple reasoning
• 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$

---

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$

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
• 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 $k \geq 1$"

Step 4: Prove the Inductive Step

• Show that $P(k) \Rightarrow P(k+1)$—this is the heart of the proof, requiring you to connect what you assumed to what you need
• Explicitly use the inductive hypothesis—circle it, underline it, or write "by I.H." when you invoke it; graders look for this
• Bridge the gap algebraically or logically—typically involves starting with P(k+1)'s left side and manipulating until you reach its right side, using P(k) along the way

---

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 "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)

---

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, and can you construct a false statement where this flawed approach would "work"?

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)$.