# Mathematical Induction

Mathematics I · Mathematical Language and Reasoning · https://tryals.app/learn/mathematics-i/mathematical-induction

## Proving Infinitely Many Cases

Some statements hold for every natural number, like $1 + 2 + \dots + n = \frac{n(n+1)}{2}$ for all $n \ge 1$. **Mathematical induction** proves infinitely many cases with a finite argument. Think of a line of dominoes: if the first falls and each knocks the next, all fall.

An induction proof relies on two essential parts:

| Part | Role | Action |
| --- | --- | --- |
| **Base case** | Tips the first domino | Prove the statement for the smallest value ($n=1$ or $0$) |
| **Inductive step** | Knocks the next domino | Assume $n=k$ holds, then prove $n=k+1$ |

Both parts are required. **Both** alone leave the chain unstarted or broken.

## Strong Induction & Pitfalls

**Strong induction** is a variant where the inductive step assumes the statement for **all** values from the base up to $k$, not just $k$. This helps when cases depend on multiple earlier ones, such as proving every integer $>1$ has a prime factorization.

To prove $1 + 2 + \dots + n = \frac{n(n+1)}{2}$: the base case $n=1$ gives $1 = \frac{1 \cdot 2}{2}$. Assuming it for $k$, adding $k+1$ yields the formula for $k+1$.

| Pitfall | Consequence |
| --- | --- |
| Omitting **base case** | The chain never starts; all cases could be false |
| Ignored **inductive hypothesis** | Proving $k+1$ from scratch instead of assuming $k$ is invalid |

## Practice questions

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

### 1. Select every statement that is TRUE about mathematical induction.

A. It requires a base case
B. It requires an inductive step
C. It can prove statements about all real numbers
D. The inductive hypothesis assumes the claim for one value k
E. It proves infinitely many cases with a finite argument

**Answer:** A. It requires a base case; B. It requires an inductive step; D. The inductive hypothesis assumes the claim for one value k; E. It proves infinitely many cases with a finite argument

**Why:** Induction needs both obligations, assumes the claim at a single k, and settles infinitely many cases finitely. But it works only over well-ordered discrete sets like the naturals, the reals have no 'next' number, so there is no rung to step to.

Page: https://tryals.app/practice/mathematics-i/mathematical-induction/select-every-statement-that-is-true-about-mathematical-induction

### 2. An inductive step alone, without a base case, is enough to prove a statement for all n.

**Answer:** False

**Why:** False. The claim 'n = n + 1' admits a perfectly valid inductive step, add 1 to both sides, yet is false for every n. Without a base case the implications form a chain anchored to nothing.

Page: https://tryals.app/practice/mathematics-i/mathematical-induction/an-inductive-step-alone-without-a-base-case-is-enough-to-prove-a

### 3. Order the parts of a proof by induction that 1 + 2 + ... + n = n(n+1)/2.

**Answer:**

1. Base case: check the formula holds for n = 1
2. Inductive hypothesis: assume the formula holds for n = k
3. Inductive step: add k+1 to both sides
4. Simplify to the formula with k+1 in place of k
5. Conclude the formula holds for every natural number n

**Why:** Base case anchors the chain, the hypothesis supplies a foothold, the step propagates it from k to k+1, and the conclusion follows for all n. Both obligations are essential, either one alone proves nothing.

Page: https://tryals.app/practice/mathematics-i/mathematical-induction/order-the-parts-of-a-proof-by-induction-that-1-2-n

### 4. Using the formula 1 + 2 + ... + n = n(n+1)/2, compute the sum of the first 10 natural numbers.

**Answer:** 55

**Why:** $\dfrac{10 \times 11}{2} = 55$. Checking a closed form against a value you can verify by hand is the fastest sanity check there is, and it is exactly what the base case does for the proof.

Page: https://tryals.app/practice/mathematics-i/mathematical-induction/using-the-formula-1-2-n-n-n-1-2-compute-the-sum-of-the

### 5. Complete the statement of the inductive step.

**Answer:** The inductive step must prove that if the claim holds for n = k, then it also holds for **n = k + 1**.

**Why:** The step proves the claim for n = k+1 assuming it for n = k. That single link, repeated, reaches every natural number above the base, like toppling a line of dominoes.

Page: https://tryals.app/practice/mathematics-i/mathematical-induction/complete-the-statement-of-the-inductive-step

### 6. An induction proof assumes the very statement it is trying to prove holds for n, then proves it for n+1. Why is that not circular reasoning?

A. Because the inductive hypothesis concerns n while the conclusion concerns n+1, and different values cannot produce circularity.
B. Because assuming a statement to prove it is permitted in mathematics as long as the assumption is later discharged.
C. Because it assumes the statement only for one n, to link consecutive cases.
D. Because induction is an axiom rather than a proof technique, so ordinary standards of circularity do not apply.

**Answer:** C. Because it assumes the statement only for one n, to link consecutive cases.

**Why:** The inductive step does not prove P(n+1); it proves 'if P(n) then P(n+1)', and assuming a premise to prove a conditional is ordinary practice. That leaves a chain with nothing travelling along it until the base case supplies the first true statement. 'n = n + 1' has a perfectly valid step and no base, and is false everywhere.

Page: https://tryals.app/practice/mathematics-i/mathematical-induction/an-induction-proof-assumes-the-very-statement-it-is-trying-to-prove

### 7. A famous fake proof shows all horses are the same colour by induction: true for one horse, and any n+1 horses split into two overlapping groups of n. Where does it break?

A. Nowhere in the logic, the conclusion follows and reveals induction is unreliable
B. At n = 1 → 2, where the two groups of one horse do not overlap
C. At large n, where the overlap becomes too small to bridge
D. At the base case, since one horse cannot establish a colour

**Answer:** B. At n = 1 → 2, where the two groups of one horse do not overlap

**Why:** With two horses the sub-groups are {first} and {second}, sharing nothing, so no horse links the colours. The step holds for every n ≥ 2 and fails at exactly the point the chain must pass through, which is why 'the step works' has to be checked at the base, not just in general.

Page: https://tryals.app/practice/mathematics-i/mathematical-induction/a-famous-fake-proof-shows-all-horses-are-the-same-colour-by