Not sure which lesson to do first? Find your level and get a plan →

Math · Sets & Logic · Grade 9-12

Mathematical Induction

Mathematical induction proves a claim P(n) for every integer n≥n0 by two steps: verify the base case P(n0), then prove the inductive step — assuming P(n) forces P(n+1).


Quick Answer

Mathematical induction proves a claim P(n) for every integer n≥n0 by two steps: verify the base case P(n0), then prove the inductive step — assuming P(n) forces P(n+1). Use it when a statement is about every whole number from some starting point and each case is built from the one before: a sum that gains one term, a staircase that gains one step, a sequence defined by a rule. The base case starts the chain and the step guarantees it never breaks, so together they cover every n.

Why This Matters

Induction is how you prove that a formula such as 1+3+5+⋯+(2n−1)=n2 holds for all n, including values no computer will ever check. It is also the logic behind recursive algorithms and loops: if each pass keeps a statement true, the statement is true at the end. Without it, a pattern seen in ten cases stays a guess.

Intuitive Explanation

Suppose you want to show you can climb every rung of an endless ladder. You need two facts: you can get onto the first rung, and from any rung you can reach the next one. With both, rung 1 gives rung 2, rung 2 gives rung 3, and so on forever. Neither fact is enough alone: without the first you never start, and without the second you might be stuck at rung 5.

In a proof, the base case is the first rung: check P(1), or whatever the starting value is, directly. The inductive step is the climb: assume P(k) for an arbitrary k and use it to prove P(k+1). Take 2n>n. Base: 21=2>1. Step: if 2k>k, then 2k+1=2⋅2k>2k≥k+1 whenever k≥1. The assumption 2k>k is where the step gets its strength; a step that never uses it is not induction.

Checking n=1,2,3,4,5 is not induction: that is five rungs, not a rule for climbing. And not every claim with an n needs induction. "If n is odd, then n+1 is even" is one statement about any odd n, with nothing linking n=7 to n=9, and a direct proof settles it in a line. Induction fits when case k+1 is naturally built from case k.

Think of it like this. Induction is a line of dominoes: push over the first, set them so each falling one hits the next, and the whole line falls. Both parts matter, since a gap anywhere or a first domino nobody pushes stops everything. Real lines of dominoes run out, while induction keeps going through every integer.

Core idea. Mathematical induction proves a statement for all integers by checking a base case and showing that whenever it holds for n it must hold for n+1.


When to Use

Use induction when a claim is about every integer n≥n0 and case n+1 is built from case n: a sum of the first n terms, a power such as 2n, a recursive sequence, a pattern that grows one piece at a time. Write P(n) as a sentence first so you know exactly what to assume and what to prove. If the claim is a single if-then about an arbitrary n, a direct proof is shorter; if P(n+1) needs several earlier cases, use strong induction.

Tip. Ask: Is the claim indexed by all integers n, with each case reachable from the one before it?

How to Recognize It

Before starting, write the claim for a general n and for n+1 side by side, and find the piece that is added when you go from one to the other.

  1. Does case n+1 contain case n plus one extra piece, such as one more term in a sum?

    If yes, induction fits: 1+2+⋯+(n+1) is the sum to n plus one more term. If no case contains the one before, there is no chain, and a direct proof about an arbitrary n fits better.

  2. Is the claim meant to hold from n=1, or only from some larger starting value?

    Use the true starting value as the base case: 2n>n2 holds for every n≥5 but fails at n=3, where 8<9, so a chain begun at n=1 would break.

  3. Does case n+1 need two or more earlier cases, as in the Fibonacci rule Fn+1=Fn+Fn−1?

    If yes, use strong induction, assuming every case up to n, and check enough base cases to start the chain. If only case n is needed, ordinary induction is enough.

  4. Have you only checked a few values, such as n=1,2,3?

    If yes, you have evidence, not a proof; checking examples can only suggest the pattern. The inductive step must show, for an arbitrary n, that assuming P(n) forces P(n+1).

Mathematical Induction compared with Direct proof, Checking examples, and Strong induction

All four rows can support a claim about integers, so they get swapped. Ask how each case is reached: from the one just before, from all earlier ones, without any chain at all, or not reached in general, only tested for a few values.

Mathematical Induction

Meaning
Use this when the claim is 'for all integers n≥n0' and each case can be built from the previous one.
Key test
Is the claim indexed by all integers n, with each case reachable from the one before it?
Example
Prove 1+2+⋯+n=n(n+1)2 for every integer n≥1.

Direct proof

Meaning
Proves a single P⇒Q by forward reasoning, with no base case or step-to-step chain.
Key test
Use when the claim is about one arbitrary object, not a sequence of integer-indexed cases.
Formula
P⇒Q
Example
Assume n even, show n2 even — one case, no induction

Checking examples

Meaning
Verifies the claim for several specific n but never proves the general step.
Key test
Use only to GUESS a pattern; it never proves a 'for all n' statement.
Example
Computing the sum for n=1,2,3 and noticing a pattern

Strong induction

Meaning
Assumes P holds for ALL values up to n (not just n) to prove P(n+1).
Key test
Use when P(n+1) depends on earlier cases, not only the immediately previous one.
Formula
Assume P(1),…,P(n) to get P(n+1)
Example
Prove every integer >1 has a prime factorization

Formula & Notation

How to read it: Base case + inductive hypothesis + inductive conclusion.

Worked Examples

Example 1 — Sum of first n integers

Easy

Prove 1+2+⋯+n=n(n+1)2 for every integer n≥1.
Show the steps and the answer
  1. State P(n): "1+2+⋯+n=n(n+1)2".

    Writing the statement out shows exactly what will be assumed for k and proved for k+1.

  2. Base case n=1: the left side is 1 and the right side is 1⋅22=1.

    The two sides agree, so the first case holds and the chain has a start.

  3. Inductive hypothesis: assume 1+2+⋯+k=k(k+1)2 for some integer k≥1.

    This is not yet known to be true; the aim is to show that if it holds for k, it holds for k+1.

  4. Add the next term: 1+⋯+k+(k+1)=k(k+1)2+(k+1)=k(k+1)+2(k+1)2=(k+1)(k+2)2.

    The hypothesis replaced the first k terms, and factoring out (k+1) gives exactly the formula with n=k+1.

  5. Conclude: P(1) is true and P(k) implies P(k+1), so P(n) holds for every n≥1.

    The base case and the step together reach every positive integer; for n=4, 1+2+3+4=10=4⋅52.

Answer: True for all n≥1

Takeaway: Use the hypothesis to replace the first k terms, add the (k+1)th term, and rearrange into the formula with k+1 in place of n.

Example 2 — One case, not a chain

Standard

Prove: if n is odd then n+1 is even. Should you use induction because there's an n?
Show the steps and the answer
  1. Ask whether case n+1 is built from case n: knowing the claim for n=7 adds nothing to the case n=9.

    Each odd n stands on its own, so there is no chain of cases to climb.

  2. Prove it directly: n odd means n=2k+1, so n+1=2k+2=2(k+1), which is even.

    One line covers every odd n at once, with no base case needed.

  3. Compare the cost: an induction proof would need a base case, a hypothesis and a step to say the same thing.

    Induction is a tool for chains; on a single if-then it adds work and no insight.

Answer: Direct proof, not induction

Takeaway: Induction pays off only when each case leans on the one before; a single if-then about any odd n is a direct proof.

Example 3 — Find the mistake: the missing first domino

Application

Sam claims 2+4+⋯+2n=n2+n+1 for every n≥1. He writes: "Assume 2+4+⋯+2k=k2+k+1. Adding 2(k+1) gives k2+3k+3=(k+1)2+(k+1)+1. The step works, so the formula is true." Find the mistake and correct it.
Show the steps and the answer
  1. Check Sam's step: k2+k+1+2k+2=k2+3k+3, and (k+1)2+(k+1)+1=k2+2k+1+k+1+1=k2+3k+3.

    The algebra is right: if the formula held for some k, it would hold for k+1.

  2. Test the base case Sam skipped: n=1 gives a left side of 2 and a right side of 1+1+1=3.

    The first domino doesn't fall, so the valid step has nothing to pass along.

  3. Test another value: n=2 gives 2+4=6 against 4+2+1=7; the formula is always 1 too big.

    A step that preserves an error carries it to every n, and only the base case catches it.

  4. Correct the formula to 2+4+⋯+2n=n2+n. Base: 2=1+1. Step: k2+k+2(k+1)=k2+3k+2=(k+1)2+(k+1).

    Now both parts hold, so the corrected formula is proved for every n≥1.

Answer: The base case fails (2≠3), so Sam's formula is false; the correct result is 2+4+⋯+2n=n2+n.

Takeaway: A working inductive step proves nothing until the base case is checked; always test the first value.

Where You'll See It

  • Moves in the Tower of Hanoi

    To move n discs, move the top n−1 out of the way, move the largest disc, then move the n−1 back on top. If n−1 discs take 2n−1−1 moves, then n discs take 2(2n−1−1)+1=2n−1. With one disc taking 1 move, induction gives 255 moves for 8 discs.

  • A savings balance year by year

    Each year the balance is multiplied by 1+r, so Bn+1=Bn(1+r). If Bn=P(1+r)n, then Bn+1=P(1+r)n+1, and B0=P starts the chain. So $1,000 at 5% grows to 1000(1.05)3≈$1,157.63 after 3 years.

Common Mistakes

  1. The slip: Forgetting the base case

    Instead: without tipping the first domino, the chain proves nothing even if the step is valid.

  2. The slip: Proving only specific cases instead of the general step

    Instead: you must show P(n)⇒P(n+1) for an arbitrary n, not for n=1,2,3.

  3. The slip: Failing to actually use the inductive hypothesis

    Instead: the step must invoke 'assume P(n)' to derive P(n+1), or it is not an induction proof.


Mini Practice

Try these on your own. Tap Reveal when you want to check.

  1. Prove by induction that 1+3+5+⋯+(2n−1)=n2 for all n≥1.

    Hint: Check n=1. Then add the next odd number, 2n+1, to n2.

  2. Prove by induction that 2n≥n+1 for all integers n≥0.

    Hint: In the step, 2n+1=2⋅2n. Use the inductive hypothesis on 2n.

  3. Prove by induction that n3−n is divisible by 3 for all n≥1.

    Hint: Expand (n+1)3−(n+1) and look for n3−n inside it.

  4. Prove by induction that n!>2n for all n≥4.

    Hint: Check n=4 first. In the step, (n+1)!=(n+1)⋅n!.

  5. Claim: "Every integer n≥2 is a product of primes." For n=12, can you get the result from the case n=11 alone, or do you need strong induction?

    Hint: Which smaller numbers does 12 actually break into?

  6. Ty "proves" n+1<n for all n: "Assume n+1<n. Adding 1 gives n+2<n+1. Done." Correct his proof.

    Hint: Did he check any starting case? Try n=1.

Want the full set?

50 practice questions for this concept — free to try, every one with a complete worked solution showing the why, not just the answer.

Frequently Asked Questions

Isn't assuming P(n) the same as assuming what I want to prove?

No, and this is the most common worry about induction. You are not assuming the claim for all nn; you are proving a conditional: if it holds for some particular nn, then it holds for n+1n + 1. That link alone proves nothing. Joined to the base case, it starts a chain: P(1)P(1) gives P(2)P(2), which gives P(3)P(3), and so on without end.

Can a careless induction prove something false?

Yes. A famous joke argument claims all horses are the same colour: in any group of n+1n + 1 horses, remove one and the rest match, remove a different one and the rest match, and the two groups overlap, so all match. The step fails going from 1 horse to 2, because removing one horse from two leaves groups of one horse each that do not overlap. One broken link breaks the whole chain.

Does induction work for things other than sums?

Yes. It proves divisibility, such as 3 dividing 4n−14^n - 1 for every n≥1n \ge 1; inequalities, such as 2n>n2^n > n; and facts about shapes, such as the interior angles of a convex polygon with nn sides adding to (n−2)×180∘(n - 2) \times 180^\circ. Programmers use the same idea to show that a loop gives the right result after every pass, and therefore when it finishes.

Why is it called induction if it is a proof?

The name is a historical accident. In science, induction means guessing a general rule from many examples, which never gives certainty. Augustus De Morgan named the method 'mathematical induction' in 1838 because it also moves from particular cases to all cases. But it uses a proved step, so it is fully rigorous, a form of deductive reasoning. The shared word still confuses students every year.

Learning Path

Mathematical Induction

You are here

Next →

Nothing after this yet
You need Sequence (terms indexed by n), Logical Statement and Quantifiers ("for all n≥1") first. Induction adds a way to prove infinitely many statements with two finite checks: a base case and a step from n to n+1. It leads to strong induction, proofs about recursive sequences such as the Fibonacci numbers, formulas for sums, and proofs that algorithms and loops give correct results.

See Also