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

Lecture

Recurrence Demonstrations: Principle and Examples

Description

This lecture covers the principle of recurrence demonstrations, showing how to prove that if P(n) is true, then P(u) is also true, with examples illustrating the process step by step, including anchoring the proof at n=0.

Official source

Related concepts (15)

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.

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".

Transfinite induction

Transfinite induction is an extension of mathematical induction to well-ordered sets, for example to sets of ordinal numbers or cardinal numbers. Its correctness is a theorem of ZFC. Let be a property defined for all ordinals . Suppose that whenever is true for all , then is also true. Then transfinite induction tells us that is true for all ordinals. Usually the proof is broken down into three cases: Zero case: Prove that is true. Successor case: Prove that for any successor ordinal , follows from (and, if necessary, for all ).

Structural induction

Structural induction is a proof method that is used in mathematical logic (e.g., in the proof of Łoś' theorem), computer science, graph theory, and some other mathematical fields. It is a generalization of mathematical induction over natural numbers and can be further generalized to arbitrary Noetherian induction. Structural recursion is a recursion method bearing the same relationship to structural induction as ordinary recursion bears to ordinary mathematical induction.

Proof by exhaustion

Proof by exhaustion, also known as proof by cases, proof by case analysis, complete induction or the brute force method, is a method of mathematical proof in which the statement to be proved is split into a finite number of cases or sets of equivalent cases, and where each type of case is checked to see if the proposition in question holds. This is a method of direct proof. A proof by exhaustion typically contains two stages: A proof that the set of cases is exhaustive; i.e.

Related lectures (34)

Cartesian Product and Induction

Introduces Cartesian product and induction for proofs using integers and sets.

Proofs by Induction: Principles and Examples

Explains the induction principle and proofs by induction with examples like 1 + 3 + 5 + ... + (2n-1) = n².

Linear Algebra: Propositions and Sets

Covers propositions indexed by vectors, proof by induction, and Cartesian products of sets.

Geometric Series: Convergence and Applications

Explores the convergence of geometric series and their applications in real-world problems.

Strong Induction: The Power of Mathematical Proof