The Base Case

The Starting Point Is Part of the Proof

In Mathematical Induction, the base case anchors the chain of implications: it verifies the claim at the first integer in the range, before the inductive step carries the claim forward. This tutorial looks more closely at that first obligation. Choosing and checking the base case involves more than testing a convenient small number: the starting value must match the range in the statement, and every expression in the claim must be meaningful there.

A base case is a direct verification of one instance of the claim. If \(P(n)\) is the statement to be proved for every integer \(n\ge m\), then the base case is \(P(m)\). It is not a guess about what might be true, a check of several nearby values in place of a proof, or the inductive step itself. It asks whether the exact statement \(P(m)\) is true at the first index under consideration.

The phrase “the exact statement” matters. For example, if \(P(n)\) asserts an equality between two expressions, the base case requires evaluating both sides at the starting value and checking that they agree. If \(P(n)\) is conditional, its truth at the starting value depends on the entire conditional statement, including its hypothesis. If an expression is not defined at the proposed starting value, then that value cannot serve as the base case for that version of the claim.

Worked Examples: Checking the First Case Carefully

When the Step Skips Integers

Many induction arguments advance from \(n\) to \(n+1\). In that setting, one base case starts the chain. But a step might instead advance from \(n\) to \(n+2\), or more generally from \(n\) to \(n+r\), where \(r\) is a positive integer. Such a step links indices in separate residue classes. For example, repeatedly adding \(2\) to \(0\) reaches \(0,2,4,\ldots\), but never reaches \(1,3,5,\ldots\). One initial case cannot start a chain in a different class of indices.

Proof. Define \(P(n)\) to mean that \(n-m\) is divisible by \(r\); that is, \(n-m=rq\) for some integer \(q\). At \(n=m\), we have \(m-m=0=r\cdot0\), so \(P(m)\) is true. Now let \(n\ge m\) and suppose \(P(n)\). Then \(n-m=rq\) for some integer \(q\). Consequently,

so \(P(n+r)\) is true. The step holds for every \(n\ge m\). However, \(P(m+1)\) is false: if \(1=rq\) for an integer \(q\), then \(q=1/r\), which is not an integer because \(r\ge2\). Thus \(P(m)\) and the step \(P(n)\Rightarrow P(n+r)\) do not imply that \(P(n)\) holds at every integer \(n\ge m\). A starting case is needed in each chain that the step does not connect to the others. \(\square\)

This is not a flaw in induction. It is a mismatch between the step and the range one hopes to cover. The usual step \(n\) to \(n+1\) reaches every integer after the start. A step of size \(r\) reaches only indices congruent to the starting index modulo \(r\), unless additional base cases start the other chains.

Proof. Fix \(j\in\{0,1,\ldots,r-1\}\), and define \(Q_j(k)=P(m+j+kr)\) for \(k\in\mathbb{N}_0\). The assumed initial cases give \(Q_j(0)=P(m+j)\), so \(Q_j(0)\) is true. Suppose \(Q_j(k)\) is true for some \(k\in\mathbb{N}_0\). Then \(P(m+j+kr)\) is true, and \(m+j+kr\ge m\). Applying the assumed step at \(n=m+j+kr\) gives \(P(m+j+(k+1)r)\), which is \(Q_j(k+1)\). The Principle of Mathematical Induction therefore gives \(Q_j(k)\) for every \(k\in\mathbb{N}_0\).

This holds for each \(j\in\{0,1,\ldots,r-1\}\). Every integer \(N\ge m\) can be written as \(N=m+j+kr\) for some \(k\in\mathbb{N}_0\) and some \(j\in\{0,1,\ldots,r-1\}\), by division with remainder applied to \(N-m\). Hence \(P(N)\) is true. Since \(N\ge m\) was arbitrary, the claim holds for every integer \(n\ge m\). \(\square\)

Worked Examples: Initial Blocks for a Two-Step Argument

Common Base-Case Errors

A frequent error is to check a value that is easy to calculate rather than the first value required by the claim. If the range is \(n\ge6\), verifying \(P(0)\) does not verify \(P(6)\). Another error is to prove the claim for several examples and treat those checks as a substitute for the inductive step. A finite list of true cases cannot, by itself, establish infinitely many cases.

It is also important not to confuse the base case with the start of an algebraic manipulation. Write down the statement \(P(m)\), substitute \(m\), and evaluate what is required. For an inequality, verify the resulting comparison; for an identity, compute both sides; for a divisibility claim, exhibit the required integer multiple. If the statement contains a denominator or other restricted expression, check that it is defined at the base value.

Finally, match the number of initial cases to the step. A step from \(n\) to \(n+1\) ordinarily needs one starting case. A step from \(n\) to \(n+r\) requires \(r\) starting cases to cover all indices from \(m\) onward. The key question is not simply “What is the first case?” but also “Which later cases can this step actually reach from it?”