Teacher Guide: Mathematical Induction

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

Present LessonView 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$ and $(k+1)^3$
• Working with exponents, for example $2 \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)$ means assuming what we want to prove

Remediation: Stress that we assume $P(k)$ for ONE value only, to show the link from $k$ to $k+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 + \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 $n$ .

Checking several values proves a formula

Remediation: Use $n^2 + n + 41$ , which is prime for $n = 0$ to $39$ but equals $41^2$ for $n = 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)$ and $P(k+1)$ with numbers, for example $k = 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 $n^3 - n$ is divisible by $3$

For Advanced Students:

• Prove $2^n > n^2$ for $n \ge 5$ and explain why the base case is $5$
• Prove $1^2 + 2^2 + \dots + n^2 = \dfrac{n(n+1)(2n+1)}{6}$
• Learn strong induction and prove that every integer $n \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

n

(or every integer from some starting value on). We call the statement

P(n)

. Instead of checking infinitely many cases one by one, you prove just two things:

1.Base case: $P(1)$ is true.
2.Inductive step: for every $k \ge 1$ , if $P(k)$ is true, then $P(k+1)$ is also true. The assumption " $P(k)$ is true" is called the inductive hypothesis.

Together they give the conclusion:

P(n)

is true for every

n \ge 1

P(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)

, then

P(2)

, then

P(3)

, and so on forever.

Worked Examples

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

Base case: check $n = 1$

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

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

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

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

$1 + \dots + k + (k+1) = \dfrac{k(k+1)}{2} + (k+1) = \dfrac{k(k+1) + 2(k+1)}{2}$ → $= \dfrac{(k+1)(k+2)}{2}$

Compare with $P(k+1)$

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

Answer: By induction, $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ for every $n \ge 1$ . For example, $1 + 2 + \dots + 100 = \dfrac{100 \cdot 101}{2} = 5050$ .

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 + \dots + n = \dfrac{n(n+1)}{2} + 1$ has a working inductive step, but for $n = 1$ the left side is $1$ and the right side is $2$ .

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)$ is true for all $n$ " or "assume $P(k+1)$ " is circular: it assumes the conclusion.

Correct: Assume $P(k)$ for ONE value $k$ (the inductive hypothesis) and prove $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 - 1$ instead of $2k + 1$ in the odd number sum, or forgetting to add the new term on one side.

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

Thinking that checking many cases is a proof

Why it's wrong: The formula $n^2 + n + 41$ gives prime numbers for $n = 0, 1, \dots, 39$ , but for $n = 40$ it gives $1681 = 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 $n$ .

Why It Matters

Induction is the main tool for proving facts about infinitely many cases:

Formulas for sums: you can prove that $1 + 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, \dots$ to a running total. Induction proves that after $n$ rounds the total is $\dfrac{n(n+1)}{2}$ .

1Try It Yourself

A program adds the numbers from $1$ to $100$ in a loop.

What total does the program print?

Step 1: Write the mathematical expression

Use $\dfrac{n(n+1)}{2}$ with $n = 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+1$ discs, move the top $k$ discs away, move the largest disc, then move the $k$ discs back on top: $2(2^k - 1) + 1 = 2^{k+1} - 1$ moves.

2Try It Yourself

A tower has $6$ discs. Moving $5$ discs takes $31$ moves.

How many moves do $6$ discs need?

Step 1: Write the mathematical expression

Use moves for 6 discs $= 2 \cdot$ (moves for 5 discs) $+ 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 $3$ squares there are $1 + 2 + 4 = 7 = 2^3 - 1$ grains.

3Try It Yourself

You fill the first $10$ squares. Square $10$ holds $2^9$ grains.

How many grains are on the first $10$ squares together?

Step 1: Write the mathematical expression

Use $1 + 2 + \dots + 2^n = 2^{n+1} - 1$ with $n = 9$ :

Key Takeaways

1Mathematical induction proves a statement $P(n)$ for every integer $n$ from a starting value on
2Base case: show that the first case, usually $P(1)$ , is true
3Inductive hypothesis: assume $P(k)$ is true for one arbitrary $k$
4Inductive step: use the hypothesis to prove $P(k+1)$
5Conclusion: like a row of dominoes, the statement is true for every $n$
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)

. The step with

k = 1

gives

P(2)

, with

k = 2

gives

P(3)

, and so on. Every positive integer is reached after finitely many steps, so no

n

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 = 0

. The statement

2^n > n^2

fails for

n = 2, 3, 4

(for example

2^4 = 16 = 4^2

) and holds for every

n \ge 5

, so that proof uses the base case

n = 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), \dots, P(k)

are all true, not only

P(k)

. It is useful when

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)$ for every integer $n$ from a starting value on, using a base case and an inductive step
Base case: The first case of the statement, usually $P(1)$ , checked directly
Inductive hypothesis: The assumption that $P(k)$ is true for some arbitrary integer $k$
Inductive step: The proof that $P(k)$ implies $P(k+1)$ for every $k$ from the starting value on
P(n): The statement we want to prove, written as a function of the integer $n$
Conclusion: The final sentence of an induction proof: $P(n)$ is true for every $n$ from the starting value on

Formula Card

Principle of induction

P(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 + \dots + n = \dfrac{n(n+1)}{2}

For $n = 5$: $15$

Sum of the first n odd numbers

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

For $n = 5$: $25$

Sum of powers of 2

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

For $n = 6$: $127$

Teacher Guide: Mathematical Induction

Use this lesson with your class

For Teachers

For Struggling Students:

For On-Level Students:

For Advanced Students:

Lesson Content

Definition

Worked Examples

Common Mistakes

Why It Matters

Real World Applications

Checking Computer Programs

The Tower of Hanoi

Rice on a Chessboard

Key Takeaways

Frequently Asked Questions

Glossary

Formula Card

Principle of induction

Sum of the first n integers

Sum of the first n odd numbers

Sum of powers of 2

More in This Topic

Introduction to Mathematical Proofs

Direct Proof

Two-Column Proofs

Paragraph Proofs