Mathematical Induction

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

Advanced30 min18 problems
Practice Problems

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.

Try it now

Which two parts must every proof by mathematical induction contain?

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.

Interactive Visual

Sequence Explorer

1,
3,
5,
7,
9,
11,
13,
15
, ...

Formula

a_n = 1 + 2(n - 1) = 2n - 1
Sum Formula: S_8 = 8/2 × (2×1 + 7×2) = 64
12345678

Partial sums

S₁ = 1S₂ = 4S₃ = 9S₄ = 16S₅ = 25S₆ = 36S₇ = 49S₈ = 64
12345678
a_1

1

a_5

9

a_10

19

a_20

39

Sequence Explorer

1,
2,
4,
8,
16,
32,
64,
128
, ...

Formula

a_n = 1 × 2^(n-1)
Sum Formula: S_8 = 1 × (1 - 2^8) / (1 - 2) = 255
12345678

Partial sums

S₁ = 1S₂ = 3S₃ = 7S₄ = 15S₅ = 31S₆ = 63S₇ = 127S₈ = 255
12345678

|r| ≥ 1: the partial sums do not settle on one value, so the infinite series has no sum.

a_1

1

a_5

16

a_10

512

a_20

524,288

Interactive Sandbox

Expression Calculator

Try these:

History

No calculations yet

Practice Problems

18 problems
Problem 1 of 18
Easy
Which two parts must every proof by mathematical induction contain?

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

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.
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.
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.
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.
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$

Today's challengeOne problem, three tries

More in This Topic

Introduction to Mathematical Proofs

Advanced25 min

Direct Proof

Advanced25 min

Two-Column Proofs

Intermediate25 min

Paragraph Proofs

Advanced30 min