Sign inSign in

Proof by induction

A proof technique used to establish that a statement holds for all natural numbers by showing a base case and an inductive step.
as Tom Leighton defines itMITThe wording closest to all 8 definitions
Watch it explained

Know first

Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.

Opens up

Concepts that name this one as a prerequisite.

Lecturers

6

Each in their own terms, from the easiest level.

  • Tom Leighton

    MIT · Undergraduate

  • Vicky Neale

    University of Oxford · Undergraduate

    A proof method useful for proving statements indexed by the natural numbers.
    • 17:18Constructing Statements and Proofs
  • Erik Demaine & Srini Devadas

    MIT · Undergraduate

    A mathematical proof technique used to prove a statement for all natural numbers by showing it holds for a base case and that if it holds for one case, it holds for the next.
    • 41:57Course Overview, Interval Scheduling
  • Ben Polak

    Yale University · Undergraduate

    A method of mathematical proof that establishes a statement for a base case and then shows that if it holds for a case N, it must also hold for the case N+1.
    • 10:49Backward Induction: Chess, Strategies, and Credible Threats
  • Eric Grimson

    MIT · Undergraduate

    A proof method showing a base case holds and that if a property holds for n, it holds for n+1.
    • 29:44Procedures and Processes
  • Marten van Dijk

    MIT · Undergraduate

    A proof technique establishing a statement for all natural numbers by showing a base case and an inductive step.

Lectures that assume it

1

Connections

15

The lectures that define it or assume it, and the concepts next to it.

6 lecturers. Definitions are written by AI from each lecture’s transcript. A time with a play mark starts the lecture at the moment the lecturer says it.