Virtual laboratory/Mathematics/Number theory/Mathematical Induction — the domino effect

Mathematical Induction — the domino effect

An extension of the topic of inductive proof and sequences. Mathematical induction proves statements for all natural numbers: if a statement holds for n=1 (the base step) and "n implies n+1" (the inductive step), then it holds for all n — like an infinite row of dominoes. The method was used rigorously by Maurolico (1575) and Pascal (1654); it was formalized as an axiom by Peano (1889).

Mathematical Induction — the domino effect
Mathematics · Number theory · Mathematical induction — the domino effect (1654)
Which domino the wave reaches nn6
Reach of the inductive step T(n)⇒T(n+1)T(n)\Rightarrow T(n{+}1)1.15 × spacing
To prove a theorem for all nn natural numbers, you need:
step n
6
toppled
6
sum 1..6
21
∀ n ∈ ℕ
yes
🎯 Challenge: does the proof work?
streak: 0

I'll give you a set of proof steps — decide whether it is enough for the theorem to hold for all n∈Nn \in \mathbb{N}.

What just happened?

A row of dominoes topples completely only when you push the first domino and each toppled one reaches the next. Remove the start or make too large a gap — the avalanche never begins or it stops. This is exactly how an inductive proof works.

The principle of mathematical induction:

To prove that a statement T(n)T(n) holds for all n∈Nn \in \mathbb{N}, it is enough to show two things:

T(1)⏟base stepand(T(n)⇒T(n+1))⏟inductive step    ⟹    ∀ n∈N  T(n)\underbrace{T(1)}_{\text{base step}} \quad\text{and}\quad \underbrace{\big(T(n) \Rightarrow T(n+1)\big)}_{\text{inductive step}} \;\;\Longrightarrow\;\; \forall\, n\in\mathbb{N}\; T(n)

The base step is “toppling the first domino”, and the inductive step is the guarantee that “every toppled domino topples the next”. Together they cover infinitely many cases with finite reasoning.

A classic example — the sum of consecutive numbers:

1+2+⋯+n=n(n+1)21+2+\dots+n=\dfrac{n(n+1)}{2}

Base step (n=1)(n=1):

1=1⋅22=1✓1 = \dfrac{1\cdot 2}{2} = 1 \quad\checkmark

Inductive step — we assume T(n)T(n) and prove T(n+1)T(n+1):

(1+⋯+n)⏟= n(n+1)2+(n+1)=n(n+1)2+(n+1)=(n+1)(n+2)2\underbrace{(1+\dots+n)}_{=\,\frac{n(n+1)}{2}}+(n+1)=\dfrac{n(n+1)}{2}+(n+1)=\dfrac{(n+1)(n+2)}{2}

This is exactly the formula T(n+1)T(n+1). The truth “carried over” from nn to n+1n+1 — and since it starts at n=1n=1, it covers all the natural numbers.

Why are a few cases not enough?

Even checking the first thousand nn proves nothing about n=106+1n = 10^6+1. There are infinitely many dominoes — you must prove the implication T(n)⇒T(n+1)T(n)\Rightarrow T(n+1), which holds always, not just for selected examples.

Why this matters for your exam:

Induction is the foundation of proofs of formulas for sums of sequences, inequalities and divisibility — required on the extended exam. The scheme is always the same: check T(1)T(1), assume T(n)T(n), derive T(n+1)T(n+1).

The first rigorous uses of this method were by Francesco Maurolico (1575) and Blaise Pascal in the “Traité du triangle arithmétique” (1654); it was formalized as an axiom of the natural numbers by Giuseppe Peano (1889).

Remember: topple the first domino (the base step) and make sure each one topples the next (the inductive step) — and they will all fall. Both conditions are necessary.

Illustrative model · NexTutor Virtual Laboratory

Enjoyed the experiment? Share it.

It's free — send it to friends from school.

Theory & formulas

The principle of induction

To prove a statement T(n)T(n) for all n≥1n\ge 1, it is enough to show:

  • the base step: T(1)T(1) is true,
  • the inductive step: T(n)⇒T(n+1)T(n)\Rightarrow T(n+1).

The domino effect

The first tile falls (the base), and each one knocks over the next (the step) — so they all fall.

Example

1+2+⋯+n=n(n+1)21+2+\cdots+n=\frac{n(n+1)}{2} is proved by induction. Merely checking a few cases is not enough.

Notation: T(n)T(n) a statement depending on nn, nn a natural number.

Frequently asked questions

›

What does an inductive proof require?

A base step (the statement for n=1) and an inductive step (its truth for n implies its truth for n+1).

›

Is checking a few cases enough?

No — you must prove that the implication "n implies n+1" always holds.

›

What is mathematical induction used for?

For proving formulas for sums of sequences, inequalities and divisibility for all natural numbers.

Teaching? Embed this experiment on your site.

Free widget — paste it on your school site, blog or notes. It links to the full version.

Teaching a class or tutoring? Guide students in NexTutor →

Related experiments

The Collatz problem (3n+1) →Pascal’s triangle →Gödel's Incompleteness Theorem →