Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Recurrence: Induction

Description

This lecture introduces the concept of recurrence, focusing on the principle of induction as a fundamental property of natural numbers. The instructor explains the process of simple recurrence, demonstrating how to prove statements using mathematical induction. The lecture also covers the importance of being cautious when applying induction, illustrated through examples involving divisibility by 9.

Official source

Ontological neighbourhood

Logic

Classical logic: First-order logic

Related concepts (32)

Mathematical proof

A mathematical proof is a deductive argument for a mathematical statement, showing that the stated assumptions logically guarantee the conclusion. The argument may use other previously established statements, such as theorems; but every proof can, in principle, be constructed using only certain basic or original assumptions known as axioms, along with the accepted rules of inference. Proofs are examples of exhaustive deductive reasoning which establish logical certainty, to be distinguished from empirical arguments or non-exhaustive inductive reasoning which establish "reasonable expectation".

Axiom

An axiom, postulate, or assumption is a statement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Ancient Greek word ἀξίωμα (), meaning 'that which is thought worthy or fit' or 'that which commends itself as evident'. The precise definition varies across fields of study. In classic philosophy, an axiom is a statement that is so evident or well-established, that it is accepted without controversy or question.

Mathematical induction

Mathematical induction is a method for proving that a statement is true for every natural number , that is, that the infinitely many cases all hold. Informal metaphors help to explain this technique, such as falling dominoes or climbing a ladder: Mathematical induction proves that we can climb as high as we like on a ladder, by proving that we can climb onto the bottom rung (the basis) and that from each rung we can climb up to the next one (the step). A proof by induction consists of two cases.

Inductive reasoning

Inductive reasoning is a method of reasoning in which a general principle is derived from a body of observations. It consists of making broad generalizations based on specific observations. Inductive reasoning is distinct from deductive reasoning, where the conclusion of a deductive argument is certain given the premises are correct; in contrast, the truth of the conclusion of an inductive argument is probable, based upon the evidence given.

Peano axioms

In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th-century Italian mathematician Giuseppe Peano. These axioms have been used nearly unchanged in a number of metamathematical investigations, including research into fundamental questions of whether number theory is consistent and complete.

Related lectures (53)

Proofs: Logic, Mathematics & Algorithms

Explores proof concepts, techniques, and applications in logic, mathematics, and algorithms.

Mathematical Induction: Principle and Example MOOC: Analysis I (part 1): Prelude, basic concepts, real numbers MOOC: Analysis I

Introduces the principle of mathematical induction through an example.

Ordinary Differential Equations: Definitions and Methods

Explores ordinary differential equations, proof methods, and historical examples from Euclid, emphasizing logical reasoning and step-by-step derivations.

Introduction to Proofs

Introduces informal proofs and their practical applications in computer science and mathematics, emphasizing the importance of proving theorems through direct and indirect methods.