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

Understanding Mathematical Induction Reference

Induction is a method for proving a whole family of claims, not for finding the formula in the first place. A pattern may look convincing after checking ten examples, yet it can still fail later. The proof must explain why the pattern cannot break at any later whole number.

It is important to state the exact starting value and the exact set of numbers being considered. A claim that begins at zero needs a different starting check from one that begins at one. Some claims need two or more starting checks because the step moves forward by two positions rather than one.

In a sum proof, the most useful move is to separate the final term from the sum through the current index. This creates a part that matches the assumed formula. Replace that part carefully, then simplify until the proposed formula for the next index appears.

Students often make an algebra error because they substitute the assumed formula into the wrong expression. Keep the left side and right side visible on separate lines. Expand brackets slowly, combine like terms, and factor only when it makes the target form clearer.

The goal is not merely to get a true-looking expression. The final line must be exactly the statement required at the next index.

Divisibility proofs depend on the meaning of divisible. To show that an expression is divisible by a number, rewrite it as that number multiplied by a whole number. The assumed divisibility result may tell you that one part already has the needed factor.

The remaining part must have it too, or the parts must combine to create it. This is why adding and subtracting a useful expression is common in these proofs. In inequality proofs, direction matters.

Adding the same quantity to both sides keeps an inequality valid. Multiplying by a positive quantity keeps its direction, while multiplying by a negative quantity reverses it. Many induction inequalities need one extra fact about the index, such as every index in the range being at least one.

Strong induction is helpful when a new case naturally depends on several earlier cases. This happens with sequences built from previous terms, ways to make an amount from smaller amounts, and statements about factoring whole numbers. The assumption can include every earlier case in the allowed range, but each assumed case still needs a real purpose in the argument.

Induction appears in computer science when proving that a recursive program works for inputs of every size. It appears in number theory, algebra, and counting problems.

When checking your work, look for a genuine starting case, a clearly named next case, and a place where the assumption is actually used. If the assumption never appears, the proof is usually incomplete or using an unjustified shortcut.

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

Understanding Mathematical Induction Reference