# Mathematical Induction

Computer Science I · Discrete Mathematics · https://tryals.app/learn/computer-science-i/mathematical-induction

## The Domino Principle

**Mathematical induction** proves statements for infinitely many natural numbers all at once, like $1 + 2 + \dots + n = \frac{n(n+1)}{2}$. Think of a line of dominoes: if the first falls, and each falling domino knocks the next, all fall.

Induction requires two strictly enforced parts:

| Part | Role | Action |
| --- | --- | --- |
| **Base case** | Starts the chain | Prove the statement for $n = 1$ (or $0$) |
| **Inductive step** | Spreads the chain | Prove $n = k+1$ assuming $n = k$ |

Neither part alone works: base without step proves only one value; step without base proves nothing.

## Variants and Pitfalls

**Strong induction** lets the inductive step assume the statement for **all** values up to $k$, not just $k$. This mirrors **recursion** in programming, where a base case and smaller step ensure termination.

| Pitfall | Why it fails |
| --- | --- |
| Missing **base case** | Never starts the chain of dominoes |
| Ignoring **inductive hypothesis** | Re-proves $k+1$ from scratch instead of assuming $k$ |

The **inductive hypothesis** is your bridge. You must use the assumption for $k$ to establish $k+1$.

## Practice questions

2 of this lesson's 10 practice questions, with answers. The full set is in the app.

### 1. Proving a recursive function correct and proving a statement by induction are the same argument. Which parts correspond?

A. Base case to base case, inductive hypothesis to the recursive call
B. The recursive call corresponds to the base case, and the termination condition to the step
C. They are unrelated: induction proves statements, recursion computes values
D. The recursion depth corresponds to the number of induction steps, and nothing else matches

**Answer:** A. Base case to base case, inductive hypothesis to the recursive call

**Why:** You assume the recursive call is correct for the smaller input and prove the current case follows, which is the inductive step verbatim. Termination corresponds to reaching the base, which is why a missing base case gives infinite recursion and a missing base case gives a failed induction.

Page: https://tryals.app/practice/computer-science-i/mathematical-induction/proving-a-recursive-function-correct-and-proving-a-statement-by

### 2. Order the parts of a proof by induction that the sum of the first n positive integers equals n(n+1)/2.

**Answer:**

1. Check the base case: for n = 1 the sum is 1 and the formula gives 1
2. Assume as the inductive hypothesis that the formula holds for n = k
3. Consider the sum for n = k + 1, which is the sum for k plus the extra term k + 1
4. Substitute the assumed formula for the sum up to k and simplify
5. Conclude that the formula holds for k + 1, and hence for every n at least 1

**Why:** The base case knocks over the first domino and the step shows each domino knocks the next. The order matters logically, not just presentationally: the step is only meaningful once there is something to assume, and the general conclusion only follows once both parts are in place.

Page: https://tryals.app/practice/computer-science-i/mathematical-induction/order-the-parts-of-a-proof-by-induction-that-the-sum-of-the-first-n