Skip to main content

Ordinary Induction Is Sequential Closure

What This Concept Is​

Ordinary (weak) induction is a proof method for statements of the form $\forall n \ge n_0,\ P(n)$ on the integers. It has two obligations:

  • Base case. Prove $P(n_0)$ directly.
  • Inductive step. Prove the implication $\forall n \ge n_0,\ P(n) \rightarrow P(n+1)$.

Once both are established, the statement $\forall n \ge n_0,\ P(n)$ follows. Formally, this is the induction axiom for the natural numbers, which can itself be derived from the well-ordering principle (see concept 17).

The mental model that makes induction click is sequential closure: if truth holds at a starting point and always propagates to the next step, it fills the whole chain.

Domino intuition: if the first domino falls, and every domino that falls knocks over the next, then every domino in the line eventually falls. The base case is the first push; the inductive step is "each domino reliably knocks over the next." Both are required; neither alone is enough. If you skip the base case, the dominoes never start falling. If you skip the step, the first one falls but none of the rest do.

A subtle but essential distinction: the inductive step is an implication, not a standalone claim. Inside the step you get to assume $P(n)$ (the inductive hypothesis, often abbreviated "IH") and your job is only to derive $P(n+1)$. You are not proving $P(n+1)$ from scratch each time; you are proving the one-step progression.

A crisp template every induction proof should follow:

  1. Name $P(n)$ as a specific claim indexed by $n$, with the domain and starting index stated.
  2. Base case: verify $P(n_0)$ by direct computation.
  3. Inductive step: "Let $n \ge n_0$ and assume $P(n)$ (IH). We show $P(n+1)$." Then derive it.
  4. Conclusion: "By induction, $P(n)$ holds for every $n \ge n_0$."

Every bullet is compulsory. Missing one and the proof silently fails.

Notation warning: the index variable in the step (we used $n$) is bound by "Let $n \ge n_0$." Some texts use $k$ to make the bound explicit ("Let $k \ge n_0$ and assume $P(k)$"). Either convention is fine; what matters is that the reader can tell which variable is the arbitrary one carrying the IH and which variable is free in the statement being proved.

Why It Matters Here​

Induction is the proof technique most tightly bound to computing. Many algorithms and data structures are recursive or iterative; proving their correctness means showing that the base case is handled and that every iteration or recursive call preserves a loop invariant. That's ordinary induction, under different names.

Beyond this module, induction powers: correctness of recursive algorithms (Semester 2), correctness of while loops via invariants (Semester 2), proofs about data-structure operations preserving invariants (Semester 3), correctness of state-machine transitions (Semester 5), and inductive arguments on run length in asymptotic analysis.

It also powers counting arguments: sums like $\sum_{k=1}^n k = n(n+1)/2$ are proved by induction, as are bounds like $\sum_{k=1}^n k^2 \le n^3$. Combinatorial identities, Fibonacci-style recurrences, and exponent laws like $2^{n+1} = 2 \cdot 2^n$ all live in this machinery.

If the induction template is not automatic by the end of this concept, every later semester's correctness proof will feel harder than it should. The payoff is disproportionate to the time invested here.

A meta-note: induction is also the cleanest example in this module of the principle "a proof shape is chosen by the theorem's shape." Any statement indexed by $\mathbb{N}$ with self-similar structure is a candidate for induction. Recognising the shape saves you from pointless direct-proof attempts.

Concrete Example​

Claim. For every integer $n \ge 1$, $$1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}.$$

Let $P(n)$ be the statement "$\sum_{k=1}^n k = \frac{n(n+1)}{2}$."

Proof (by induction on $n$).

Base case ($n = 1$). The left-hand side is $1$; the right-hand side is $\frac{1 \cdot 2}{2} = 1$. So $P(1)$ holds.

Inductive step. Let $n \ge 1$ and assume $P(n)$: $\sum_{k=1}^n k = \frac{n(n+1)}{2}$ (IH). We show $P(n+1)$, i.e., $\sum_{k=1}^{n+1} k = \frac{(n+1)(n+2)}{2}$.

Compute:

$$\sum_{k=1}^{n+1} k \ =\ \underbrace{\sum_{k=1}^n k}_{\text{apply IH}} + (n+1) \ =\ \frac{n(n+1)}{2} + (n+1) \ =\ \frac{n(n+1) + 2(n+1)}{2} \ =\ \frac{(n+1)(n+2)}{2}.$$

This establishes $P(n+1)$.

Conclusion. By ordinary induction, $P(n)$ holds for every $n \ge 1$. $\blacksquare$

Second worked example (divisibility). Claim: for every integer $n \ge 1$, $3^n - 1$ is divisible by $2$.

Let $P(n)$ be "$2 \mid (3^n - 1)$." Base $n = 1$: $3^1 - 1 = 2$; $2 \mid 2$. Step: assume $2 \mid (3^n - 1)$, i.e., $3^n - 1 = 2k$ for some integer $k$. Then $3^{n+1} - 1 = 3 \cdot 3^n - 1 = 3(2k + 1) - 1 = 6k + 2 = 2(3k + 1)$, which is divisible by $2$. So $P(n+1)$ holds. By induction, $P(n)$ holds for every $n \ge 1$. $\blacksquare$

Observe that the inductive step rewrote $3^{n+1}$ in terms of $3^n$ exactly to expose the inductive hypothesis. Rewriting to expose IH is the core algebraic maneuver.

A fake induction to spot. Consider: "Every finite set of horses is the same colour." Base $n = 1$: a set of one horse is trivially the same colour as itself. Step: given $n$ horses $h_1, \ldots, h_{n+1}$, the subset ${h_1, \ldots, h_n}$ is monochromatic (by IH); the subset ${h_2, \ldots, h_{n+1}}$ is also monochromatic (by IH); they overlap in ${h_2, \ldots, h_n}$, so they share a colour. So all $n+1$ horses share it. The bug is in the step when $n = 1$: the two subsets ${h_1}$ and ${h_2}$ do not overlap, so the argument fails for the base-to-next transition. Induction does not repair this gap; the base case needs to be strong enough for the step to reach from it.

Common Confusion / Misconception​

  1. Circular reasoning: assuming $P(n+1)$ in the step. The inductive hypothesis is $P(n)$, not $P(n+1)$. A proof that starts "assume $P(n+1)$" and then derives something is not an induction; it is a restatement of the goal. The discipline: label the IH explicitly and check that your manipulations only invoke $P(n)$.
  2. Missing or wrong base case. If you claim $P(n)$ for $n \ge 1$ but verify $P(0)$, the chain starts in the wrong place. A classic fraud is the proof that "all horses are the same colour" -- the inductive step is almost correct but the base case breaks for $n = 2$, invalidating the whole chain. Always verify the base case at the exact index you claim the statement starts from.
  3. Skipping "let $n \ge n_0$" in the step. Starting the inductive step with just "assume $P(n)$" leaves the quantifier on $n$ implicit. Writing "Let $n \ge n_0$ and assume $P(n)$" makes the universal quantification explicit and flags that $n$ is arbitrary, not specific.
  4. Using the IH in a way that requires a stronger hypothesis. If in the step you find yourself needing $P(n-3)$ or "$P(k)$ for every $k \le n$," you are past ordinary induction and need strong induction (concept 17). Switching methods midway is fine; pretending ordinary induction handles the stronger claim is not.
  5. Proving $P(n+1)$ directly without invoking the IH. That is not an error per se, but it signals either the IH is not needed (in which case induction is not the right tool -- try direct proof), or you missed the spot where the IH would simplify the algebra.

How To Use It​

Operational checklist for an induction proof:

  1. State the index domain. "For every integer $n \ge 1$…" or "For every $n \in \mathbb{N}$…" -- be precise about the lowest $n$.
  2. Define $P(n)$. Write the claim as a named statement indexed by $n$. This makes the IH quotable.
  3. Verify the base case at the stated lowest $n$. Direct computation; no clever moves.
  4. Write the inductive step opening. "Let $n \ge n_0$ and assume $P(n)$ (IH)."
  5. Write the goal. "We show $P(n+1)$, i.e., …" -- state it explicitly so you know what you are aiming for.
  6. Algebraic bridge. Manipulate the $n+1$ expression to expose a $P(n)$ structure; apply the IH; simplify to the target form.
  7. Close. "This establishes $P(n+1)$. By induction, $P(n)$ holds for every $n \ge n_0$."
  8. Sanity check. Plug in $n = n_0 + 1$ into your step's algebra and confirm it lines up with what you'd get by direct computation.

Check Yourself​

  1. Why is the base case logically necessary? Give a false statement for which the "inductive step" holds but the base case fails.
  2. What exactly are you allowed to assume inside the inductive step? What are you trying to prove?
  3. Rewrite the proof of $1 + 2 + \cdots + n = n(n+1)/2$ to start from $n_0 = 0$ instead of $n_0 = 1$. What changes?
  4. Find the bug in the "all horses are the same colour" fake induction. Which of the five proof discipline points above does it violate?
  5. When is induction the wrong tool, even for a statement indexed by $n$? Give an example where direct proof is simpler.
  6. Why must you say "Let $n \ge n_0$" in the inductive step rather than just "Assume $P(n)$"?

Mini Drill or Application​

Prove each of the following by ordinary induction. For each, define $P(n)$ explicitly, verify the base case, state the IH, and write the inductive step with the algebraic bridge visible:

  1. For every integer $n \ge 1$: $2 + 4 + 6 + \cdots + 2n = n(n+1)$.
  2. For every integer $n \ge 1$: $1^2 + 2^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}$.
  3. For every integer $n \ge 1$: $2 \mid (3^n - 1)$ (redo this one carefully, not by copy-pasting).
  4. For every integer $n \ge 4$: $n! \ge 2^n$. (Notice the base case is $n = 4$, not $1$.)
  5. For every integer $n \ge 1$: the number of subsets of an $n$-element set is $2^n$.
  6. For every integer $n \ge 0$: $\sum_{k=0}^n 2^k = 2^{n+1} - 1$.

At least three of these should be written out in full with each template step labelled. The goal is to make the template feel automatic.

Transfer / Where This Shows Up Later​

  • Semester 2 (algorithms). Loop invariants are proved by induction on iteration count: "the invariant holds on entry, and if it holds at iteration $k$ it holds at iteration $k+1$, therefore it holds on exit." Every termination proof pairs an invariant induction with a descent argument.
  • Semester 3 (software design). Class hierarchies and data structure invariants are preserved by each operation; proving preservation is ordinary induction on operation count.
  • Semester 4 (systems). Protocol correctness proofs often induct on the number of messages exchanged or on the round number in a multi-round protocol.
  • Semester 6 (distributed systems). Consensus protocol correctness is proved by induction on round count; invariants preserved across rounds are the standard proof structure.
  • Semester 9+ (PL theory / verification). Proofs by induction on the syntax tree of a program (structural induction -- concept 18) generalise ordinary induction to tree-shaped data. Type soundness theorems are induction on typing derivations.

Read This Only If Stuck​

Closing Note​

Ordinary induction is one of the two or three most-reused proof templates in all of computer science. Treat the five-step template -- name $P(n)$, base, IH, step, conclude -- as a reflex you can execute on autopilot.

The payoff is that every later correctness argument about a recursive algorithm, a loop, a data-structure operation, or a protocol round will snap into a shape you already know how to write. Concepts 17 and 18 generalise the pattern to strong induction and structural induction; the scaffolding here is the prerequisite for both.