Exercises: Mathematical Induction

These build from mechanical warm-ups to full proofs, code, and modeling. Difficulty: ⭐ foundational, ⭐⭐ intermediate, ⭐⭐⭐ challenging. Worked solutions to the starred-with-a-dagger (†) and odd-numbered problems are in the appendix answers-to-selected.md; do them before you peek.

Part A — Warm-ups (⭐)

6.1 † Identify the base case and write out the inductive hypothesis (you don't need to finish the proof) for the claim: for all $n \ge 1$, $\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$.

6.2 For the claim "$2^n > n^2$", compute both sides for $n = 1, 2, 3, 4, 5$. At which $n$ does the claim first become true and stay true? What does this tell you about the base case?

6.3 † Rewrite the statement "$5 \mid (n^5 - n)$ for all $n \ge 0$" with the divisibility unpacked into an equation (i.e., state what "$5 \mid (n^5 - n)$" means using an integer $m$).

6.4 In the proof that $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$, point to the exact line where the inductive hypothesis is used.

Part B — Prove it (⭐⭐)

6.5 † Prove by induction: for all $n \ge 1$, $\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$.

6.6 Prove by induction: for all $n \ge 1$, $\sum_{i=1}^{n} i^3 = \left(\frac{n(n+1)}{2}\right)^2$. (Note the lovely consequence: the sum of the first $n$ cubes is the square of the sum of the first $n$ integers.)

6.7 † (Scaffolded.) Prove that for all $n \ge 1$, the geometric sum $\sum_{i=0}^{n-1} 2^i = 2^n - 1$. Fill in the blanks: - Base case ($n=1$): the left side is $\sum_{i=0}^{0} 2^i = \underline{\hphantom{xx}}$; the right side is $2^1 - 1 = \underline{\hphantom{xx}}$. - Inductive step: assume $\sum_{i=0}^{k-1} 2^i = 2^k - 1$. Then $\sum_{i=0}^{k} 2^i = \left(\sum_{i=0}^{k-1} 2^i\right) + \underline{\hphantom{xxxx}} = (2^k - 1) + \underline{\hphantom{xxxx}} = \underline{\hphantom{xxxx}}$, which is the formula at $n = k+1$.

6.8 Prove that for all $n \ge 1$, $6 \mid (n^3 - n)$.

6.9 † Prove that for all $n \ge 4$, $2^n < n!$. (Find the right base case first.)

6.10 Prove that a set with $n$ elements has exactly $2^n$ subsets, by induction on $n$. (This is a preview of Chapter 8; use the idea that each element is either in or out of a subset.)

Part C — Implement it (⭐⭐)

Write Python for each. Do not run it on the grader's machine — hand-trace and include an # Expected output: comment, matching the book's convention.

6.11 † Write both a recursive and an iterative function to compute $\sum_{i=1}^{n} i^2$. For the iterative one, state the loop invariant.

6.12 Implement power(base, exp) for exp >= 0 recursively (no **). State the claim you would prove by induction to show it's correct, and identify the base case and recursive (hypothesis) step.

6.13 † Using the Toolkit's check_identity from this chapter, write three lines that test the identity in Exercise 6.6 ($\sum i^3 = (\sum i)^2$) for $n$ up to 30. What output confirms the identity held on every tested case? Why is that not a proof?

Part D — Find the error (⭐⭐)

Each "proof" below is wrong. State precisely which part fails and why.

6.14 † Claim: for all $n \ge 1$, $\sum_{i=1}^{n} i = \frac{n^2 + n + 1}{2}$. "Proof": assume it holds for $k$; then $\sum_{i=1}^{k+1} i = \frac{k^2+k+1}{2} + (k+1) = \frac{k^2+3k+3}{2} = \frac{(k+1)^2 + (k+1) + 1}{2}$, completing the induction. ∎ — Find the flaw. (Hint: check the base case.)

6.15 Claim: every positive integer equals every other positive integer. "Proof": by strong induction on $\max(a,b)$ … (a deliberately bogus argument). Without reconstructing the whole thing, explain the category of error such "proofs" rely on, referencing the all-horses example.

6.16 † A student proves "$P(k) \rightarrow P(k+1)$ for all $k \ge 1$" correctly but never checks any base case, and concludes $P(n)$ holds for all $n$. Give a concrete $P(n)$ for which their inductive step is valid yet the conclusion is false.

Part E — Model it & Conjecture and test (⭐⭐⭐)

6.17 † (Conjecture and test, then prove.) Consider $f(n) = 1 + 3 + 5 + \dots + (2n-1) + \dots$ no — consider the number of regions a circle is divided into by $n$ chords in "general position." Look up small cases or reason them out for $n = 0,1,2,3$, conjecture a formula, test it with code on a few more cases, then attempt a proof. Where does naive pattern-matching mislead you? (This is a famous trap; report what you find.)

6.18 (Model it.) You're reviewing a recursive function merge_count(lst) that someone claims returns the number of elements in a list. Translate "this function is correct" into a statement $P(n)$ about lists of length $n$, then outline the induction (base case + inductive step) you'd use to verify it. You don't need the function's code — just the proof structure.

6.19 † Prove that the recursive triangle function from §6.4, called on input $n$, makes exactly $n+1$ calls to itself (including the initial call). Set up $P(n)$ and prove it by induction.

6.20 Prove the Tower of Hanoi move count: moving a tower of $n$ disks takes exactly $2^n - 1$ moves. Model the recursive strategy first, derive the recurrence $T(n) = 2T(n-1) + 1$, then prove the closed form by induction. (We'll solve such recurrences systematically in Chapter 18.)

Part F — Interleaved & Deep Dive

Mixing techniques from earlier chapters keeps them sharp.

6.21 † (Ch. 5 + 6.) The justification of induction uses a "smallest counterexample" argument. Write that argument as a clean proof by contradiction: assume the set of $n$ for which $P(n)$ fails is non-empty, and derive a contradiction from the base case and inductive step.

6.22 (Ch. 2 + 6.) Express the principle of mathematical induction itself as a single logical formula using quantifiers over $n$ and the predicate $P$. Which quantifier governs the inductive step?

6.23 † (Ch. 1 + 6.) Prove by induction that a propositional formula built from $n$ distinct variables has a truth table with exactly $2^n$ rows.

6.24 (Deep Dive.) Prove that the principle of mathematical induction and the well-ordering principle each imply the other. (You may use Chapter 7's statement of well-ordering; this previews it.)

6.25 (Deep Dive.) Find a statement $P(n)$ such that $P(1), P(2), \dots, P(40)$ are all true but $P(41)$ is false. Use it to argue, in one paragraph, why "I tested it up to 40" is not a proof — connecting to theme four of the book.

Solutions to † and odd-numbered exercises: see appendices/answers-to-selected.md. For each proof, the rubric rewards: a clearly stated $P(n)$, a correct base case at the right starting value, explicit use of the inductive hypothesis, and a clean conclusion.