Mathematical Induction Reference Cheat Sheet

Mathematical induction is a proof method used to show that a statement is true for every integer in an infinite sequence, usually all $n \geq 1$ . Students need this cheat sheet because induction has a strict structure that is easy to confuse with ordinary algebra. It helps organize the base case, inductive hypothesis, and inductive step clearly.

This method is especially useful for proving formulas, divisibility patterns, inequalities, and recursive results.

The main idea is to prove the first case, then prove that one true case forces the next case to be true. If $P(1)$ is true and $P(k) \Rightarrow P(k+1)$ for every integer $k \geq 1$ , then $P(n)$ is true for all integers $n \geq 1$ . Strong induction is similar, but it allows the proof of $P(k+1)$ to use all earlier cases $P(1), P(2), \ldots, P(k)$ .

Clear notation and careful substitution are the key skills for writing valid induction proofs.

Key Facts

The basic induction structure is: prove $P(n_0)$ is true, assume $P(k)$ is true for $k \geq n_0$ , then prove $P(k+1)$ is true.
The conclusion of ordinary induction is that $P(n)$ is true for every integer $n \geq n_0$ .
The inductive hypothesis is the temporary assumption that $P(k)$ is true, and it must be used to prove $P(k+1)$ .
For a summation formula, the inductive step often uses $\sum_{i=1}^{k+1} a_i = \sum_{i=1}^{k} a_i + a_{k+1}$ .
For divisibility, prove a statement like $m \mid f(k+1)$ by rewriting $f(k+1)$ as $f(k) + m \cdot q$ or another expression known to be divisible by $m$ .
For inequalities, after assuming $P(k)$ , use valid inequality rules to show the next statement $P(k+1)$ is true.
Strong induction assumes $P(n_0), P(n_0+1), \ldots, P(k)$ are all true in order to prove $P(k+1)$ .
A proof by induction fails if the base case is missing, because the chain $P(k) \Rightarrow P(k+1)$ needs a true starting point.

Vocabulary

Mathematical induction: A proof method that shows a statement $P(n)$ is true for all integers $n \geq n_0$ by proving a starting case and a next-case rule.
Base case: The first value, such as $n = 1$ or $n = n_0$ , that is checked directly to start the induction proof.
Inductive hypothesis: The assumption that $P(k)$ is true for some arbitrary integer $k \geq n_0$ .
Inductive step: The part of the proof where the inductive hypothesis is used to prove $P(k+1)$ .
Strong induction: A form of induction that assumes all statements $P(n_0)$ through $P(k)$ are true before proving $P(k+1)$ .
Universal statement: A statement that claims something is true for every value in a set, such as all integers $n \geq 1$ .

Common Mistakes to Avoid

Skipping the base case is wrong because the implication $P(k) \Rightarrow P(k+1)$ does not prove that any first statement is actually true.
Assuming what you need to prove is wrong because the inductive hypothesis is only $P(k)$ , not $P(k+1)$ .
Using a specific value like $k = 5$ in the inductive step is wrong because the proof must work for an arbitrary integer $k \geq n_0$ .
Forgetting to add the next term in a summation proof is wrong because $\sum_{i=1}^{k+1} a_i$ equals $\sum_{i=1}^{k} a_i + a_{k+1}$ , not just the old sum.
Changing the starting value without checking it is wrong because a statement true for all $n \geq 1$ may require a different base case than a statement true for all $n \geq 0$ .

Practice Questions

1 Use induction to prove that $1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$ for all integers $n \geq 1$ .
2 Use induction to prove that $3 \mid (4^n - 1)$ for all integers $n \geq 1$ .
3 Use induction to prove that $2^n \geq n+1$ for all integers $n \geq 1$ .
4 Explain why proving only $P(k) \Rightarrow P(k+1)$ is not enough to prove that $P(n)$ is true for every integer $n \geq 1$ .

Sign in to save

Sign in to save

Mathematical Induction Reference Cheat Sheet

Related Tools

Related Labs

Related Worksheets

Related Infographics

Study as Flashcards

Key Facts

Vocabulary

Common Mistakes to Avoid

Practice Questions