So You Need To Prove Something For All Natural Numbers
You've probably seen this thing in your discrete math class and thought it was a parlor trick. A way for textbook authors to make simple sums look impressive. I'm going to walk you through how it actually works in practice, not just how it's presented in a proof-writing handbook that nobody actually reads cover to cover. At its core, The Principle Of Mathematical Induction lets you prove a statement P(n) for every natural number n by doing two things: showing P(0) or P(1) is true, and showing that if P(k) is true, then P(k+1) must also be true. That's it. Two steps. That's the entire machinery. Everything else is just applying those two steps to increasingly complicated-looking statements until your head starts to spin.
The Principle Of Mathematical Induction: How It Actually Works In Practice
The inductive step is where people consistently lose points. They write something like "assume P(k)" and then just start manipulating P(k+1) until it looks true. That's backwards reasoning and it's wrong. The correct approach is to start with your assumption P(k) and derive P(k+1) from it, not the other way around. I remember working through a problem where you had to prove that the sum of the first n odd numbers equals n squared. So 1 = 1², 1+3 = 2², 1+3+5 = 3², and so on. The base case is trivial. The inductive step looks straightforward too. You assume the sum of the first k odd numbers is k², then you need to show the sum of the first k+1 odd numbers is (k+1)². You write out the sum, substitute your assumption, add the next odd number which is 2k+1, and suddenly you have k² + 2k + 1, which factors neatly into (k+1)². Done. Here's the thing that doesn't get emphasized enough: the inductive hypothesis isn't just a tool you use once. Sometimes you need to invoke it multiple times, or apply it to a slightly different statement than the one you're directly trying to prove. This shows up a lot in recurrence relation problems.
Let me tell you about a problem that bit me hard once. I was trying to prove that 7 divides 3^(2n) + 4 for all natural numbers n. The base case works fine. For the inductive step, I had 3^(2(k+1)) + 4, which is 9·3^(2k) + 4. The trick is to rewrite 9 as 7 + 2, so you get 7·3^(2k) + 2·3^(2k) + 4. Now you can see the 7·3^(2k) term is divisible by 7 by inspection, and the remaining part 2·3^(2k) + 4 is exactly 2 times your inductive hypothesis expression. Since 7 divides 3^(2k) + 4, it also divides 2(3^(2k) + 4). This is a type of problem where you need to see the hidden structure before you can write the proof cleanly. Another common format is the strong induction variant, where your inductive hypothesis assumes P(j) holds for ALL j k, not just P(k). This matters when the statement about k+1 depends on more than just the immediately preceding case. A classic example is proving that every integer greater than 1 can be written as a product of primes. To handle the case for k+1, if k+1 is composite you need to factor it into smaller pieces, and those pieces might be well below k, so you need the full strength of the strong hypothesis. There's also the issue of shifted base cases, which trips people up because they blindly start at n = 0 when the statement only makes sense for n 2 or some other threshold. A statement like "2^n > n²" is actually false for n = 2 and n = 3, but becomes true for all n 5. The induction still works, but your base case has to be n = 5, not n = 0. You can't just skip the base case because the statement happens to fail for small values.
Get the Full Details
When Induction Fails And What To Do Instead
Induction is powerful but it has real limitations. It only works for statements about well-ordered sets, which in standard practice means the natural numbers or something isomorphic to them. You can't use it directly to prove something about real numbers, for instance. There's no "next real number" after any given real number, so the inductive step has no foothold. Sometimes people try to force induction onto problems where it doesn't naturally fit and end up with circular reasoning or gaps they hand-wave away. A statement that involves continuous quantities, limits, or properties that don't decompose cleanly into a n versus n+1 relationship is a red flag. If you find yourself struggling to express P(k+1) in terms of P(k), that's often a sign that induction isn't the right tool. For inequalities involving continuous variables or statements about all real numbers in an interval, tools like calculus-based arguments or the least upper bound property are more appropriate. For statements about well-ordering itself, you might actually need to appeal to the well-ordering principle as an axiom rather than deriving it from induction, since they're logically equivalent in ZFC set theory.
One nuance that many students miss is that the choice of base case matters for efficiency even when it doesn't affect correctness. Proving a statement for all n 5 by induction with base case n = 5 is valid, but you might also need an extra check at n = 5 if the inductive step only works cleanly for k 5. I once spent twenty minutes on a homework problem realizing my inductive step required k 3, which meant the base case of n = 0 wasn't sufficient to carry the argument forward. I had to add n = 3 as an additional base case and then the proof went through smoothly.
A Few Things That Will Make Your Proofs Less Painful
Write out the statement P(n) explicitly before you start. Not in your head. On paper. When P(n) is a complicated algebraic expression, seeing it laid out prevents you from accidentally substituting the wrong thing into the inductive hypothesis. When you hit a wall in the inductive step, try working backwards first. Algebraic manipulation in proofs is often easier to discover than to construct forward. Find what you need P(k+1) to equal, then see what algebraic moves get you there, and finally verify those moves are legitimate when run in the forward direction. This is standard practice and it's not cheating, it's just how proof writing actually works for most people. Pay attention to whether your problem needs simple induction or strong induction. The difference is subtle but important. Simple induction assumes only P(k). Strong induction assumes P(j) for all j up to k. If your proof requires facts about multiple previous cases, strong induction is the one to reach for. Using simple induction when you need strong induction will leave you with a gap you can't fill.
Also don't forget to state clearly what you're assuming at each step. "By the inductive hypothesis, we have..." is a phrase that belongs in your proofs. Without it, the reader has no idea which part of the argument relies on the assumption and which part is standalone algebra. Graders notice this, and more importantly you'll notice it when you're checking your own work later.
