Mathematical induction
A base case and general successor step establish a predicate on all nonnegative integers.
Key knowledge
If P(0) holds and P(n) implies P(n+1) for every nonnegative integer n, mathematical induction establishes P(n) for every nonnegative integer n.
Conditions and scope
- Prove the base case and the successor implication for arbitrary n.
- Checking finitely many examples is not an inductive step.
Sources · 3
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
Massachusetts Institute of Technology2 sources
- Mathematics for Computer Science (2015), §5.1.1: The induction principleEric Lehman, F. Thomson Leighton and Albert R. Meyer; MIT OpenCourseWareTextbook chapter · PDF
- Mathematics for Computer Science, Spring 2015Eric Lehman, F. Thomson Leighton and Albert R. Meyer / MIT OpenCourseWareTextbook chapter · PDF
- Discrete Mathematics II · Set theory for computer scienceGlynn Winskel, University of CambridgeTeaching resource · PDF
Evidence and review
Ordinary induction on nonnegative integers.
2026-10-10 · Checked the proof rule; no new theorem is proved by this record.
Foundational review
2026-10-10 · Fresh primary-source inspection of the complete compact record, including every statement, equation, quantity and material condition, followed by independent AI editorial review. This check does not certify all linked lessons or every passage of every cited publication.
Sources from other places
Agreement within this scope
Base case at zero and an arbitrary successor implication establish all nonnegative integer cases.
A successor proof is stronger than a finite list of examples.
University of Cambridge, Computer Laboratory
- Discrete Mathematics II · Set theory for computer science United KingdomEnglish
§1.1.1 Patterns of proof: mathematical induction, pp.12–13
- Discrete Mathematics II · Set theory for computer science
Entry details
Permanent link to this entry ↗- Record identity
- math-induction
- Revision
- core.1
- Structured reference record
- Essential core · first collection