The Mechanics of Induction Proofs

Mathematical induction is one of those tools that looks deceptively simple until you try to use it on anything non-trivial. The structure is always the same: you prove a base case, assume the statement holds for some arbitrary integer k, and then show it must hold for k+1. That's it mechanically. What trips people up is everything that happens between those two steps. I've spent years grading these, and honestly, the majority of errors come from weak induction hypothesis work. Students write out P(k) correctly but then fumble the algebra when they try to bridge from P(k) to P(k+1). It's not that they don't know the method. It's that they treat the inductive step like a computation problem instead of a logical argument, and the algebra collapses under its own weight. Let me walk through a standard example first before getting into the messier territory. Consider proving that the sum of the first n odd numbers equals n². The statement is: for every positive integer n, 1 + 3 + 5 + ... + (2n - 1) = n². Base case: n = 1. Left side is 1. Right side is 1² = 1. Done. Inductive step: Assume the formula holds for some arbitrary positive integer k. That means 1 + 3 + 5 + ... + (2k - 1) = k². Now I need to show 1 + 3 + 5 + ... + (2k - 1) + (2k + 1) = (k + 1)². Take the left side, group the first k terms using the induction hypothesis, and replace them with k². You get k² + (2k + 1), which factors to (k + 1)². That's the whole thing. Simple on paper. The problem compounds quickly when the formulas get longer or involve products, powers, or divisibility conditions. I've seen students spend forty minutes on a single inductive step because they didn't recognize they could substitute the induction hypothesis early enough in the manipulation.

Common Prove By Mathematical Induction Problems

Beyond the textbook sums, the problems that actually show up in courses and competitive settings tend to fall into a few categories, and each one has its own failure mode. Divisibility proofs are perhaps the most common. You're asked to show that 3 divides n³ - n for all positive integers n, or that 7 divides 4 - 1 for all n 0. The trick here is factoring. In the inductive step, you'll typically arrive at an expression involving f(k+1), and you need to rewrite f(k+1) in terms of f(k) so you can apply the induction hypothesis. For n³ - n, you expand (k+1)³ - (k+1), which gives k³ + 3k² + 3k + 1 - k - 1. Rearrange to (k³ - k) + 3k(k + 1). The first part is divisible by 3 by hypothesis. The second part is divisible by 3 because either k or k+1 is even, making 3k(k+1) divisible by 3. It works. But only if you spot the factorization. Students who just plug in numbers and hope the algebra resolves themselves usually get lost around here. Inequality proofs introduce another layer of difficulty. You might need to show that 2 > n² for all n 5. The base case checks out: 2 = 32 and 5² = 25. The inductive step requires showing 2¹ > (k+1)² assuming 2 > k². Multiply the hypothesis by 2 to get 2¹ > 2k². Now you need 2k² (k+1)², which simplifies to k² - 2k - 1 0. This holds for k 3, so it's fine for our base case of k 5. The subtlety here is that the inequality you're trying to prove isn't strong enough on its own for the inductive step to go through directly. Sometimes you need a stronger induction hypothesis. That's where strong induction comes in. The difference from regular induction is that instead of assuming P(k) implies P(k+1), you assume P(j) holds for all j from the base case up through k, and then prove P(k+1). This matters when the property at k+1 depends on multiple earlier values, not just the immediately preceding one. Fibonacci identities are the classic use case. Proving that F + F + F + ... + F = F requires knowing both F and F from previous steps, so regular induction stalls out and strong induction carries you through. I ran into a real headache last year grading a midterm where students were asked to prove that every integer n 2 can be written as a product of primes. The expected solution used strong induction. One student tried regular induction and got stuck at the step where n+1 was composite, because they only had the induction hypothesis for n, not for any of the smaller factors. I gave partial credit but flagged it in the comments because the structural error was exactly the kind that shows up repeatedly. If the recursive structure of your problem depends on values earlier than k, regular induction won't work. Period.

Where Induction Fails and What to Do Instead

Induction is not a universal proof technique. There are legitimate mathematical claims where it simply cannot be applied, and recognizing those cases saves time that would otherwise be wasted. One common failure mode is when the property you're trying to prove involves irrationality or transcendence. You can't induct over "being irrational" the way you induct over divisibility or equality. The statement "n2 is irrational for all positive integers n" is true, but no amount of induction on n will get you there because the inductive step requires properties of prime factorization and the fundamental theorem of arithmetic, not a recursive algebraic manipulation. Use a direct proof or contradiction instead. Another case is when the property changes direction unpredictably. Suppose you want to prove that n! > 2 for n 4. Base case checks. Inductive step: assume k! > 2, multiply both sides by k+1 to get (k+1)! > 2(k+1). You need 2(k+1) 2¹, which simplifies to k+1 2. That's trivially true for k 4, so the proof works. But flip the inequality and try to prove n! < 2, and you'll hit a wall. The inductive step requires 2(k+1) 2¹, meaning k+1 2, which fails for all k 4. The statement is false anyway, but even if it were true, the inductive step might not be constructible. Not every true statement has a clean inductive proof. Recursive sequences defined by recurrence relations other than simple addition or multiplication also cause trouble. Consider the sequence a = 1, a = a² + 1. You might want to prove something about a, but the squaring makes the inductive step explode into higher-degree polynomials that don't simplify cleanly. Closed-form solutions or generating functions are better tools here. For students who need practice material, I'd point them toward specific resources rather than general advice. Rosen's Discrete Mathematics and Its Applications has a dedicated chapter with about forty graded induction problems ranging from straightforward to genuinely tricky. Stewart's Calculus early chapters include induction proofs for summation formulas that are useful for building algebraic fluency. The Art of Problem Solving's Proofing Book walks through induction across multiple problem types with detailed solutions. If you're working independently, the hardest problems to find well-sourced are the ones involving combinatorial identities like binomial coefficient recurrences — for those, the Dummit and Foote abstract algebra text or the Putnam preparation materials by Spencer et al. have the best collection. The single most useful skill you can develop for induction proofs is learning to manipulate expressions so the induction hypothesis becomes visible. When you see P(k+1) and your brain immediately tries to expand everything from scratch instead of looking for a subexpression that matches P(k), that's the bottleneck. Write out what P(k) says first, then rearrange P(k+1) until a piece of it appears. The algebra does most of the work if you know where to look.