Mathematical induction

Mathematical statement

For a proposition family P(n) starting at 0, if P(0) holds and every natural number n satisfies P(n) implies P(n+1), then P(n) holds for every natural number n.

Representative formula (exact TeX)

P(n)

Assumptions

• P is a well-formed family of propositions indexed by a natural number n.
• This entry uses the OCME convention that natural numbers begin at 0.
• The base case and induction step must each be proved in their explicitly stated scope.

Symbol scope

• P — family of propositions
• n — natural-number index

Intuition, definition, and misconceptions

The base case establishes the proposition at the first index. The induction step proves that whenever it holds at one index, it holds at the next. Together they cover all natural numbers along the successor chain.

The induction hypothesis P(n) may be used only while proving P(n+1); it is not an unconditional assumption of the entire desired conclusion. The scopes of the induction variable and other parameters must also remain distinct.

If the proposition begins at 1, at some k, or on another structure, the base case and induction principle must be adjusted. The notation P(n) here represents a proposition family rather than a complete logical formula.

A common mistake is to check only a few initial cases and claim induction is complete, or to use the induction hypothesis unconditionally outside the induction step.

Prerequisites

• Natural number — The natural-number structure of zero and successor supplies the induction order.
• Proposition — Induction acts on a family of propositions varying with a natural-number index.

Verification boundary

This entry describes the induction principle but does not yet register Lean formal-proof Evidence bound to the scope of the encyclopedia statement.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.

Next obligation

Use Nat.rec or the induction tactic to construct a minimal proof with explicit base and step obligations, preserving its exact statement and content address.

Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.