Back to Lesson

Teacher Guide: Mathematical Induction

Learn to prove statements for every positive integer with mathematical induction: base case, inductive hypothesis, inductive step and conclusion.

Present LessonShare to ClassroomView Student Page

Use this lesson with your class

Free, no student accounts needed.

Share with students

Students open the lesson and practise with instant feedback.

Printable worksheet

All practice problems on paper, with a separate answer key.

Worksheet Answer key

Class quiz

10 questions on Mathematical Proofs. Students join with a name, you see everyone's score.

For Teachers

Learning Objectives
  • Explain the domino idea behind mathematical induction
  • Write the base case, inductive hypothesis, inductive step and conclusion of an induction proof
  • Prove sum formulas, divisibility statements and inequalities by induction
  • Find and correct errors in flawed induction proofs
Prerequisites
  • • Introduction to Mathematical Proofs: what a proof is
  • • Direct Proof: proving statements from definitions
  • • Expanding and factoring expressions such as (k+1)2(k+1)^2 and (k+1)3(k+1)^3
  • • Working with exponents, for example 2⋅2k=2k+12 \cdot 2^k = 2^{k+1}
Discussion Starters
  • 1. If you know the first domino falls and each domino knocks over the next one, how do you know the 1000th domino falls?
  • 2. Why is checking a formula for the first 40 values of n not enough?
  • 3. What would go wrong if we skipped the base case?
  • 4. Can you think of a situation in daily life where one step always leads to the next one?
Common Misconceptions

Assuming P(k)P(k) means assuming what we want to prove

Remediation: Stress that we assume P(k)P(k) for ONE value only, to show the link from kk to k+1k+1. The base case is what starts the chain. Use the dominoes: we assume one domino falls only to check that it hits the next one.

The base case is a formality that can be skipped

Remediation: Show the false claim 1+2+⋯+n=n(n+1)2+11 + 2 + \dots + n = \dfrac{n(n+1)}{2} + 1. Its inductive step works perfectly, but the base case fails, so the claim is false for every nn.

Checking several values proves a formula

Remediation: Use n2+n+41n^2 + n + 41, which is prime for n=0n = 0 to 3939 but equals 41241^2 for n=40n = 40. Patterns suggest a formula, only a proof confirms it.

Differentiation Ideas

For Struggling Students:

  • • Give a template with four labeled boxes: base case, hypothesis, step, conclusion
  • • Before the algebra, check P(k)P(k) and P(k+1)P(k+1) with numbers, for example k=4k = 4
  • • Start with sum formulas only, where the next term is easy to see

For On-Level Students:

  • • Prove the odd number sum and the sum of powers of 2 without a template
  • • Find the error in three flawed induction proofs
  • • Prove that n3−nn^3 - n is divisible by 33

For Advanced Students:

  • • Prove 2n>n22^n > n^2 for n≥5n \ge 5 and explain why the base case is 55
  • • Prove 12+22+⋯+n2=n(n+1)(2n+1)61^2 + 2^2 + \dots + n^2 = \dfrac{n(n+1)(2n+1)}{6}
  • • Learn strong induction and prove that every integer n≥2n \ge 2 is a product of primes
Standards Alignment
  • MP3 (CCSS.MATH.PRACTICE.MP3)

    Construct viable arguments and critique the reasoning of others

  • HSA-APR.C.4 (CCSS.MATH.CONTENT.HSA.APR.C.4)

    Prove polynomial identities and use them to describe numerical relationships

  • HSA-SSE.B.4 (CCSS.MATH.CONTENT.HSA.SSE.B.4)

    Derive the formula for the sum of a finite geometric series and use the formula to solve problems

Lesson Resources
  • visualSequence Visualizer

    Set the first term to 1 and the difference to 2: the sum line shows that the first 8 odd numbers add up to 64, which is 8 squared

  • activityDomino Demonstration

    Students set up a row of dominoes and test what happens without a first push or with one gap in the row

  • worksheetFill in the Induction Proof

    Five induction proofs with missing base cases, hypotheses and algebra steps to complete

Lesson Content

Everything students see: definition, examples, common mistakes, applications. Tap to open.

Definition

Mathematical induction is a proof method for statements about every positive integer nn (or every integer from some starting value on). We call the statement P(n)P(n). Instead of checking infinitely many cases one by one, you prove just two things:
  1. 1.Base case: P(1)P(1) is true.
  2. 2.Inductive step: for every k≥1k \ge 1, if P(k)P(k) is true, then P(k+1)P(k+1) is also true. The assumption "P(k)P(k) is true" is called the inductive hypothesis.
Together they give the conclusion: P(n)P(n) is true for every n≥1n \ge 1.
P(1) and (P(k)⇒P(k+1)) ⟹ P(n) for all n≥1P(1) \ \text{and} \ \big(P(k) \Rightarrow P(k+1)\big) \ \Longrightarrow \ P(n) \text{ for all } n \ge 1
Think of an endless row of dominoes. The base case knocks over the first domino. The inductive step guarantees that every falling domino knocks over the next one. So every domino falls: P(1)P(1), then P(2)P(2), then P(3)P(3), and so on forever.

Worked Examples

Prove that 1+2+3+⋯+n=n(n+1)21 + 2 + 3 + \dots + n = \dfrac{n(n+1)}{2} for every n≥1n \ge 1.
1

Base case: check n=1n = 1

Left side: 11. Right side: 1⋅22=1\dfrac{1 \cdot 2}{2} = 1 → P(1)P(1) is true
2

Inductive hypothesis: assume P(k)P(k) for some k≥1k \ge 1

Assume 1+2+⋯+k=k(k+1)21 + 2 + \dots + k = \dfrac{k(k+1)}{2} → We may use this equation
3

Inductive step: add the next term k+1k+1 to both sides

1+⋯+k+(k+1)=k(k+1)2+(k+1)=k(k+1)+2(k+1)21 + \dots + k + (k+1) = \dfrac{k(k+1)}{2} + (k+1) = \dfrac{k(k+1) + 2(k+1)}{2} → =(k+1)(k+2)2= \dfrac{(k+1)(k+2)}{2}
4

Compare with P(k+1)P(k+1)

P(k+1)P(k+1) says the sum equals (k+1)((k+1)+1)2=(k+1)(k+2)2\dfrac{(k+1)\big((k+1)+1\big)}{2} = \dfrac{(k+1)(k+2)}{2} → P(k+1)P(k+1) is true

Common Mistakes

Skipping the base case

Why it's wrong: The inductive step alone proves nothing: it only says IF one domino falls, the next one falls too. Example: the false claim 1+2+⋯+n=n(n+1)2+11 + 2 + \dots + n = \dfrac{n(n+1)}{2} + 1 has a working inductive step, but for n=1n = 1 the left side is 11 and the right side is 22.

Correct: Always check the first case explicitly. Without a first falling domino, nothing falls.

Assuming what you want to prove

Why it's wrong: Writing "assume P(n)P(n) is true for all nn" or "assume P(k+1)P(k+1)" is circular: it assumes the conclusion.

Correct: Assume P(k)P(k) for ONE value kk (the inductive hypothesis) and prove P(k+1)P(k+1) from it.

Wrong algebra in the inductive step

Why it's wrong: A common slip is adding the wrong next term, for example adding 2k−12k - 1 instead of 2k+12k + 1 in the odd number sum, or forgetting to add the new term on one side.

Correct: Write out P(k+1)P(k+1) in full first (replace every nn by k+1k+1), then work toward exactly that expression.

Thinking that checking many cases is a proof

Why it's wrong: The formula n2+n+41n^2 + n + 41 gives prime numbers for n=0,1,…,39n = 0, 1, \dots, 39, but for n=40n = 40 it gives 1681=4121681 = 41^2, which is not prime.

Correct: Examples help you guess a formula. Only the base case plus the inductive step proves it for every nn.

Why It Matters

Induction is the main tool for proving facts about infinitely many cases:
  • Formulas for sums: you can prove that 1+2+⋯+100=50501 + 2 + \dots + 100 = 5050 follows from a general formula, not from luck
  • Computer science: programmers prove that loops and recursive functions give the right result for every input size
  • Patterns that look true: a pattern that holds for 40 cases can still fail at case 41; induction tells you when a pattern really holds forever
  • Puzzles and games: the Tower of Hanoi, tiling problems and many competition questions are solved by induction
  • Higher mathematics: almost every area of mathematics uses induction somewhere
In the earlier lessons you learned direct proofs. Induction adds a powerful new idea: prove one step, and let it repeat forever.

Real World Applications

Checking Computer Programs

Programmers use induction to prove that a loop gives the right answer after any number of rounds: if it is correct after $k$ rounds, it is correct after $k+1$ rounds.

Example:

A loop adds 1,2,3,…1, 2, 3, \dots to a running total. Induction proves that after nn rounds the total is n(n+1)2\dfrac{n(n+1)}{2}.

1Try It Yourself

A program adds the numbers from 11 to 100100 in a loop.

What total does the program print?

Step 1: Write the mathematical expression

Use n(n+1)2\dfrac{n(n+1)}{2} with n=100n = 100:

The Tower of Hanoi

In this puzzle you move a stack of discs to another peg, one disc at a time, never putting a larger disc on a smaller one. Induction proves that $n$ discs need $2^n - 1$ moves.

Example:

To move k+1k+1 discs, move the top kk discs away, move the largest disc, then move the kk discs back on top: 2(2k−1)+1=2k+1−12(2^k - 1) + 1 = 2^{k+1} - 1 moves.

2Try It Yourself

A tower has 66 discs. Moving 55 discs takes 3131 moves.

How many moves do 66 discs need?

Step 1: Write the mathematical expression

Use moves for 6 discs =2⋅= 2 \cdot (moves for 5 discs) +1+ 1:

Rice on a Chessboard

An old legend: put $1$ grain of rice on the first square, $2$ on the second, $4$ on the third, doubling each time. The sum of powers of 2 tells you the total.

Example:

On the first 33 squares there are 1+2+4=7=23−11 + 2 + 4 = 7 = 2^3 - 1 grains.

3Try It Yourself

You fill the first 1010 squares. Square 1010 holds 292^9 grains.

How many grains are on the first 1010 squares together?

Step 1: Write the mathematical expression

Use 1+2+⋯+2n=2n+1−11 + 2 + \dots + 2^n = 2^{n+1} - 1 with n=9n = 9:

Key Takeaways

  • 1Mathematical induction proves a statement P(n)P(n) for every integer nn from a starting value on
  • 2Base case: show that the first case, usually P(1)P(1), is true
  • 3Inductive hypothesis: assume P(k)P(k) is true for one arbitrary kk
  • 4Inductive step: use the hypothesis to prove P(k+1)P(k+1)
  • 5Conclusion: like a row of dominoes, the statement is true for every nn
  • 6Both parts are needed: a working step without a base case, or a few checked cases without a step, prove nothing

Frequently Asked Questions

Why does induction really prove the statement for ALL n?

The base case gives P(1)P(1). The step with k=1k = 1 gives P(2)P(2), with k=2k = 2 gives P(3)P(3), and so on. Every positive integer is reached after finitely many steps, so no nn is left out.

Does the base case always have to be n = 1?

No. Start at the first value from which the statement should hold. The sum of powers of 2 starts at n=0n = 0. The statement 2n>n22^n > n^2 fails for n=2,3,4n = 2, 3, 4 (for example 24=16=422^4 = 16 = 4^2) and holds for every n≥5n \ge 5, so that proof uses the base case n=5n = 5.

Is mathematical induction the same as inductive reasoning in science?

No. Inductive reasoning guesses a general rule from examples and can be wrong. Mathematical induction is a deductive proof: once the base case and the step are proven, the result is certain.

What is strong induction?

In strong induction the hypothesis assumes P(1),P(2),…,P(k)P(1), P(2), \dots, P(k) are all true, not only P(k)P(k). It is useful when P(k+1)P(k+1) depends on several earlier cases, for example in proofs about prime factorizations.

Glossary

Mathematical induction
A proof method that proves P(n)P(n) for every integer nn from a starting value on, using a base case and an inductive step
Base case
The first case of the statement, usually P(1)P(1), checked directly
Inductive hypothesis
The assumption that P(k)P(k) is true for some arbitrary integer kk
Inductive step
The proof that P(k)P(k) implies P(k+1)P(k+1) for every kk from the starting value on
P(n)
The statement we want to prove, written as a function of the integer nn
Conclusion
The final sentence of an induction proof: P(n)P(n) is true for every nn from the starting value on

Formula Card

Principle of induction

P(1) and (P(k)⇒P(k+1))⇒P(n) for all n≥1P(1) \text{ and } \big(P(k) \Rightarrow P(k+1)\big) \Rightarrow P(n) \text{ for all } n \ge 1

Base case plus inductive step proves the statement for every $n$

Sum of the first n integers

1+2+⋯+n=n(n+1)21 + 2 + \dots + n = \dfrac{n(n+1)}{2}

For $n = 5$: $15$

Sum of the first n odd numbers

1+3+⋯+(2n−1)=n21 + 3 + \dots + (2n-1) = n^2

For $n = 5$: $25$

Sum of powers of 2

1+2+4+⋯+2n=2n+1−11 + 2 + 4 + \dots + 2^n = 2^{n+1} - 1

For $n = 6$: $127$

More in This Topic

Introduction to Mathematical Proofs

Advanced25 min

Direct Proof

Advanced25 min

Two-Column Proofs

Intermediate25 min

Paragraph Proofs

Advanced30 min