Practice Mathematical Induction in Math

Use these practice problems to test your method after reviewing the concept explanation and worked examples.

Worksheet PDF Free Answer-key PDF Family

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

Showing a random 20 of 50 problems.

Example 1

medium
Inductive step for '3∣(n3−n)3 \mid (n^3 - n) for all n≥0n\ge0'.

Example 2

medium
Prove by induction: 7∣(8n−1)7 \mid (8^n - 1) for all n≥1n\ge 1.

Example 3

easy
For which kind of statement is induction the right tool?

Example 4

medium
Prove by induction: 5∣(n5−n)5 \mid (n^5 - n) for all n≥0n\ge 0.

Example 5

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

Example 6

easy
Verify the base case n=1n=1 for '1+2+⋯+n=n(n+1)21+2+\cdots+n = \frac{n(n+1)}{2}'.

Example 7

easy
For the claim 'n2≥nn^2 \ge n for all integers n≥0n \ge 0,' which base case should you check?

Example 8

medium
Prove by induction: ∑i=1ni⋅2i=(n−1)2n+1+2\sum_{i=1}^n i \cdot 2^{i} = (n-1)2^{n+1}+2 for n≥1n\ge 1.

Example 9

hard
Prove by induction: n2<2nn^2 < 2^n for all n≥5n\ge 5.

Example 10

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

Example 11

hard
Prove by induction: ∑i=1n1i(i+1)=nn+1\sum_{i=1}^n \tfrac{1}{i(i+1)} = \tfrac{n}{n+1} for n≥1n\ge 1.

Example 12

medium
Use strong induction to prove every integer n≥2n\ge 2 has a prime factorization.

Example 13

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

Example 14

easy
Compute both sides of '1+2+3=3⋅421+2+3 = \frac{3\cdot4}{2}' to confirm the formula at n=3n=3.

Example 15

challenge
Prove by induction: n3+2nn^3 + 2n is divisible by 3 for all n≥0n\ge0.

Example 16

hard
Prove by induction: the Fibonacci numbers satisfy Fn+1Fn−1−Fn2=(−1)nF_{n+1}F_{n-1} - F_n^2 = (-1)^n for n≥1n\ge 1 (Cassini's identity).

Example 17

easy
State precisely what the principle of mathematical induction allows you to conclude after verifying the base case P(1)P(1) and the implication P(k)⇒P(k+1)P(k)\Rightarrow P(k+1).

Example 18

medium
Inductive step for '∑i=1n2i−1=2n−1\sum_{i=1}^n 2^{i-1} = 2^n - 1' (sum of powers of 2).

Example 19

medium
Why is the base case here n=5n=5 for '2n>n22^n > n^2' rather than n=1n=1?

Example 20

easy
Write down the inductive hypothesis for proving '3∣(4n−1)3\mid (4^n - 1) for all n≥1n\ge 1.'
← Back to Mathematical Induction Worked Examples