COMP3220 Foundations of Computing - Lecture 5: Mathematical Induction

Flashcards summarizing key concepts from the lecture on mathematical induction.

Proof

A method of establishing the correctness of a mathematical statement.

Mathematical induction

A technique used to prove statements that hold for all natural numbers.

Base case

The initial step in a proof by induction where the statement is shown to be true for the first natural number.

Induction step

The part of a proof by induction where it is shown that if the statement holds for some natural number k, then it holds for k + 1.

Natural numbers (ℕ)

The set of positive integers starting from 1, 2, 3, and so on.

LHS (Left-Hand Side)

The left side of an equation used in proofs, which we aim to show equals the RHS.

RHS (Right-Hand Side)

The right side of an equation in a proof that we demonstrate matches the LHS.

Domino effect

An analogy used in induction where proving one statement leads to proving the next, similar to falling dominoes.

Induction hypothesis

The assumption made in the induction step that the statement is true for n = k.

Induction conclusion

The final statement that arises after completing both the base case and induction step, proving the original assertion for all natural numbers.