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.

Teacher Resources

Mathematical Induction

Q: 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.

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

Advanced30 minLesson

Printable worksheet

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.

Try it now

Which two parts must every proof by mathematical induction contain?

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

Interactive Visual

Sequence Explorer

First Term (a₁ = 1)

Common Difference (d = 2)

11,

13,

, ...

Formula

a_n = 1 + 2(n - 1) = 2n - 1

Sum Formula: S_8 = 8/2 × (2×1 + 7×2) = 64

Partial sums

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

a_1

a_5

a_10

a_20

Sequence Explorer

First Term (a₁ = 1)

Common Ratio (r = 2)

16,

32,

64,

128

, ...

Formula

a_n = 1 × 2^(n-1)

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

Partial sums

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

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

a_1

a_5

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 + \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

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.

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$

Mathematical Induction

Definition

Worked Examples

Common Mistakes

Interactive Visual

Sequence Explorer

Formula

Partial sums

Sequence Explorer

Formula

Partial sums

Interactive Sandbox

Expression Calculator

History

Practice Problems

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