Mathematical Induction Examples: 47 Problems with Answers

Start with the recap, study the fully worked examples, then use the practice problems to check your understanding of Mathematical Induction.

This page combines explanation, solved examples, and follow-up practice so you can move from recognition to confident problem-solving in Math.

Concept Recap

Mathematical induction proves statements indexed by integers by verifying a base case and an inductive step.

Like dominoes: first one falls, and each one knocks over the next.

Read the full concept explanation →

How to Use These Examples

Read the first worked example with the solution open so the structure is clear.
Try the practice problems before revealing each solution.
Use the related concepts and background knowledge badges if you feel stuck.

What to Focus On

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

Common stuck point: The procedure for mathematical induction is the easy part; the trap is forgetting the base case. Asking "Is the claim indexed by all integers $n$ , with each case reachable from the one before it?" first is what keeps a correct-looking calculation from being attached to the wrong concept.

Sense of Study hint: Ask: Is the claim indexed by all integers $n$ , with each case reachable from the one before it?

Worked Examples

Example 1

medium

Use mathematical induction to prove:

1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}

for all

n \ge 1

Answer

1 + 2 + \dots + n = \frac{n (n + 1)}{2} for all n \geq 1

First step

Base case (

n=1

): LHS

= 1

. RHS

= \frac{1 \cdot 2}{2} = 1

. True.

See the full worked solution + why-it-works coaching

SetupKey insightWhy it worksCommon pitfallConnection

Unlock answer keys One Family plan — every worked solution, all subjects

Example 2

hard

Prove by induction:

n! > 2^n

for all integers

n \ge 4

Example 3

medium

Prove by induction that

\sum_{i=1}^n i^3 = \left(\tfrac{n(n+1)}{2}\right)^2

for

n\ge 1

Example 4

medium

Prove by induction:

\sum_{i=1}^n i \cdot 2^{i} = (n-1)2^{n+1}+2

for

n\ge 1

Example 5

medium

Use induction to prove the geometric sum formula

\sum_{i=0}^{n} r^i = \tfrac{r^{n+1}-1}{r-1}

for

r\ne 1

n\ge 0

Example 6

hard

Prove by induction: a

2^n \times 2^n

board with one square removed can be tiled by L-trominoes, for all

n\ge 1

Example 7

challenge

Prove by induction:

\sum_{i=1}^n \tfrac{1}{\sqrt{i}} \ge \sqrt{n}

for all

n\ge 1

Practice Problems

Try these problems on your own first, then open the solution to compare your method.

Example 1

medium

Prove by induction:

1^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}

for all

n \ge 1

Example 2

medium

Prove by induction that

2 + 4 + 6 + \dots + 2 n = n (n + 1)

for all

n \ge 1

Example 3

easy

In induction, what are the two parts you must establish?

Example 4

easy

Verify the base case

n=1

for '

1+2+\cdots+n = \frac{n(n+1)}{2}

Example 5

easy

State the inductive hypothesis for proving '

2^n > n

for all

n\ge 1

Example 6

easy

What goes wrong if you prove the inductive step but skip the base case?

Example 7

easy

In the inductive step you must show

P(k) \Rightarrow

what?

Example 8

easy

For which kind of statement is induction the right tool?

Example 9

easy

Why must the inductive step actually USE the hypothesis

P(k)

Example 10

easy

Compute both sides of '

1+2+3 = \frac{3\cdot4}{2}

' to confirm the formula at

n=3

Example 11

medium

In proving

1+2+\cdots+n=\frac{n(n+1)}{2}

, do the inductive step from

k

k+1

Example 12

medium

Inductive step for '

3 \mid (n^3 - n)

for all

n\ge0

Example 13

medium

Prove the base case AND set up the step for '

2^n \ge n+1

n\ge0

Example 14

medium

Find and fix the flaw: 'All horses are the same color' (induction on group size).

Example 15

medium

Inductive step for '

\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}

Example 16

medium

Why is the base case here

n=5

for '

2^n > n^2

' rather than

n=1

Example 17

medium

State the inductive step you must prove for '

n! > 2^n

for all

n\ge 4

Example 18

medium

Inductive step for '

\sum_{i=1}^n 2^{i-1} = 2^n - 1

' (sum of powers of 2).

Example 19

medium

Inductive step for the inequality '

\sum_{i=1}^n \frac{1}{i^2} \le 2 - \frac{1}{n}

Example 20

challenge

Prove by induction:

\sum_{i=1}^n i = \frac{n(n+1)}{2}

for all

n\ge1

(full proof).

Example 21

challenge

Prove by induction:

n^3 + 2n

is divisible by 3 for all

n\ge0

Example 22

challenge

Prove by induction: a set with

n

elements has exactly

2^n

subsets.

Example 23

easy

State precisely what the principle of mathematical induction allows you to conclude after verifying the base case

P(1)

and the implication

P(k)\Rightarrow P(k+1)

Example 24

easy

For the claim '

n^2 \ge n

for all integers

n \ge 0

,' which base case should you check?

Example 25

easy

Name the two things you must do in an inductive proof.

Example 26

easy

In the inductive step for '

2 \mid n^2 + n

,' which factoring fact about

n^2+n

is the key insight?

Example 27

easy

What is wrong with 'proving' a claim about real numbers by induction on the real number

x

Example 28

medium

Prove by induction:

7 \mid (8^n - 1)

for all

n\ge 1

Example 29

medium

Prove by induction:

5 \mid (n^5 - n)

for all

n\ge 0

Example 30

medium

Prove by induction:

2^n \ge n+1

for all

n\ge 0

Example 31

medium

Prove by induction: a convex

n

-gon (

n\ge 3

) has

\tfrac{n(n-3)}{2}

diagonals.

Example 32

medium

Identify the flaw in this 'inductive' argument: 'Base:

P(1)

holds. Step:

P(k+1)

is similar.'

Example 33

medium

Use strong induction to prove every integer

n\ge 2

has a prime factorization.

Example 34

medium

Prove by induction: the number of subsets of an

n

-element set of size exactly

1

n

Example 35

hard

Prove by induction:

\sum_{i=1}^n \tfrac{1}{i(i+1)} = \tfrac{n}{n+1}

for

n\ge 1

Example 36

hard

Prove by induction: for all

n\ge 1

(1+x)^n \ge 1 + nx

for

x\ge -1

(Bernoulli's inequality).

Example 37

hard

Prove by strong induction: every integer

n\ge 8

is expressible as

3a+5b

for non-negative integers

a,b

Example 38

hard

Prove by induction:

n^2 < 2^n

for all

n\ge 5

Example 39

hard

Prove by induction: the Fibonacci numbers satisfy

F_{n+1}F_{n-1} - F_n^2 = (-1)^n

for

n\ge 1

(Cassini's identity).

Example 40

challenge

Use strong induction to prove every

n\ge 1

can be written uniquely in binary (as a sum of distinct powers of

2

← Back to Mathematical Induction Practice Mode

Related Concepts

Sequence Logical Statement Quantifiers

Background Knowledge

These ideas may be useful before you work through the harder examples.

sequencelogical statementquantifiers