On this page
Mathematical induction is a method for proving that a statement is true for every natural number. Wikipedia's article on mathematical induction explains it with a ladder: prove you can get onto the bottom rung, prove you can climb from any rung to the next, and you can climb as high as you like. The same article notes that Francesco Maurolico used it in 1575 to show that the sum of the first n odd numbers is n².
What are the parts of a proof by induction?
The course notes Mathematics for Computer Science, by Eric Lehman, F. Thomson Leighton and Albert R. Meyer and published on MIT OpenCourseWare, give a template for induction proofs with five components. In plain terms:
Say the proof uses induction.
Define the statement. Write P(n) for the claim and say which n it starts from. The notes call P(n) the induction hypothesis.
Base case. Prove P at the first value directly, with no assumptions.
Inductive step. Assume P(k) is true for some k at or above the start, and use that assumption to prove P(k+1). The argument must work for every such k.
Invoke induction. By the principle of induction, P(n) is true for every n from the start onwards.
The same notes advise: "Always be sure to explicitly label the base case and the inductive step."
How do you prove a sum formula by induction?
Claim: 1² + 2² + ... + n² = n(n+1)(2n+1)/6 for every n ≥ 1.
Base case, n = 1: the left side is 1, and the right side is 1·2·3/6 = 1. True.
Assumption: 1² + ... + k² = k(k+1)(2k+1)/6 for some k ≥ 1.
Inductive step: add the next term, (k+1)², to both sides. The right side becomes k(k+1)(2k+1)/6 + (k+1)². Take out (k+1)/6 to get (k+1)[k(2k+1) + 6(k+1)]/6 = (k+1)(2k²+7k+6)/6 = (k+1)(k+2)(2k+3)/6.
That is the formula with n = k+1, so P(k+1) holds and the result follows by induction.
Write out P(k+1) as your target before the algebra, so you know what shape to factor towards.
How do you prove divisibility by induction?
Claim: 7^n − 3^n is divisible by 4 for every n ≥ 1.
Base case, n = 1: 7 − 3 = 4. True.
Assumption: 7^k − 3^k = 4m for some whole number m.
Inductive step: 7^(k+1) − 3^(k+1) = 7·7^k − 3·3^k. Subtract and add 7·3^k to get 7(7^k − 3^k) + 4·3^k = 7·4m + 4·3^k = 4(7m + 3^k), a multiple of 4.
The general trick: rearrange the k+1 expression until the k expression appears inside it, then use your assumption.
How do you prove an inequality by induction?
Claim: 2^n > n² for every n ≥ 5.
Base case, n = 5: 32 > 25. True. The claim fails at n = 4 (both sides are 16) and at n = 3 (8 < 9), so the starting value matters.
Assumption: 2^k > k² for some k ≥ 5.
Inductive step: 2^(k+1) = 2·2^k > 2k². Now you need 2k² ≥ (k+1)², which rearranges to k² ≥ 2k+1. For k ≥ 5, k² ≥ 5k = 2k + 3k > 2k+1. So 2^(k+1) > (k+1)².
Which mistakes make an induction proof invalid?
No base case. Take P(n): n = n+1. If k = k+1, adding 1 gives k+1 = k+2, so the step seems to work, yet the statement is never true.
Assuming the conclusion. Write "assume P(k) for some k", not "assume P(n) for all n", which assumes what you are proving.
A step that breaks for small k. The MIT notes give a false proof that all horses are the same colour. Its step fails going from one horse to two, because the two groups it compares no longer overlap. Your step must work for every k from the base case up.
Checking cases instead of proving. n² + n + 41 is prime for n = 0 to 39, but at n = 40 it equals 1681 = 41². A pattern is a guess, not a proof.
Working backwards from P(k+1). Simplifying the equation you want down to 0 = 0 proves nothing unless every step reverses. Start from one side and reach the other.
A checklist before you hand it in
P(n) stated, with its starting value.
Base case checked at that value and labelled.
Assumption written for "some k" at or above the start.
The line where you use the assumption is marked.
Your final expression matches P(k+1) exactly.
A one-line conclusion.
If your step stalls, the Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning rather than printing an answer. Our guide to the method of differences for summing series shows how such formulas are found before induction confirms them, and our guide to writing full proofs for INMO covers what olympiad graders expect on the page. For history, read about Al-Karaji and early induction.
