Slides on Induction and Recursion (no pauses)

Prelude

  • Overview of important topics in number theory and mathematical induction, including basic induction, strong induction, and recursion.

  • Presented by Dr. A Havens, University of Massachusetts Amherst.

  • Date: September 24, 2024.

Some Number Theory

The Natural Numbers

  • Definition of 0: Considered a well-defined quantity, representing the cardinality of the empty set (0 := |∅|).

Successor Function

  • Defined for finite sets as:

    1. S(∅) = {∅} (successor of the empty set).

    2. S(A) = A ∪ {A} for nonempty set A.

  • The function builds natural numbers by incrementing: S(n) = n + 1, starting at the empty set.

Building N

  • Natural numbers (N) defined recursively:

    • N := {S(n) : n ∈ N ∧ 0 ∈ N}.

    • Form: {0, S(0), S(S(0)),...} = {0, 1, 2, ...}.

Convention on Natural Numbers

  • The convention 0 ∈ N is not universal; other texts may exclude 0.

  • Positive integers defined as N+ := N {0}.

Well Ordering Principle

  • Principle: Every nonempty subset S ⊆ N has a unique least element.

  • Total ordering of natural numbers is established.

Division and Divisibility

Divisibility Definition

  • For m, n ∈ N, m divides n (m | n) if there exists k ∈ N such that n = mk.

  • Greatest Common Divisor (gcd): gcd(m, n) is the largest natural number dividing both m and n.

  • Special case: If gcd(m, n) = 1, m and n are coprime.

Divisor Sets and Primes

  • Definition of Divisor Sets: Divisors(n) = {m ∈ N+ : m | n}.

  • Definition of Prime Numbers: p > 1 is prime if Divisors(p) = {1, p}.

  • Prime Factorization: n = p1^{e1} · p2^{e2} · ... · pk^{ek} where p1, ..., pk are primes and e1, ..., ek are their respective powers.

Euclid's Lemma

Lemma (First Lemma)

  • If prime p divides the product ab, then p divides either a or b.

Fundamental Theorem of Arithmetic

Theorem

  • Any natural number n > 1 can be factored uniquely into prime powers.

  • Goal: Prove this uniqueness.

Proof Elements

  • Existence Lemma: A prime factorization exists for every n > 1, established via contradiction.

  • Uniqueness Lemma: Unique factorization is proven using contradiction; distinct factorizations imply common prime factors leading to a contradiction.

Principle of Mathematical Induction

Principle Overview

  • For subset T of N satisfying:

    1. 0 ∈ T

    2. If k ∈ T, then k + 1 ∈ T.

  • If both are satisfied, T = N.

Induction as a Proof Algorithm

Steps:

  1. Prove P(0) is true (base case).

  2. Prove P(k) implies P(k + 1) (induction step).

Examples of Mathematical Induction

Summing Consecutive Integers

  • Prove P(n): ( \sum_{i=1}^{n} i = \frac{n(n + 1)}{2} ).

    • Base Case: Show for n = 1.

    • Inductive Step: Assume true for k, prove for k + 1.

Induction with an Inequality

  • Prove that (2^n > n^2) for all n ≥ 5.

    • Base Case: Check true for n = 5.

    • Inductive Step: Assume true for k, prove for k + 1.

Generalized Euclid’s Lemma

Lemma

  • If a prime p divides a product of positive integers, it divides at least one of the integers.

Proof Strategy

  • Use induction on the number of terms in the product.

Recursively Defined Sequences

Definition

  • A sequence is recursively defined if the nth term is defined based on k previous terms.

Example: Factorials

  • n! = n · (n − 1)! with initialization 0! = 1.

  • Computations: 1! = 1, 2! = 2, 3! = 6, …

Strong Principle of Mathematical Induction

  • If T is a subset of N satisfying:

    1. m ∈ T.

    2. P(k) holds for all m ≤ k implies P(k+1).

  • This allows stronger deduction for propositions.

Exercises

  • Prove: 5 | (6n - 1) for all n ∈ N.

  • Prove ( \sum_{i=1}^{n}i^2 = \frac{n(n + 1)(2n + 1)}{6} ).

  • Prove the intersection of intervals yields a single point.

Well Ordering Principle (redux)

  • Proof showing any subset without a minimal element must be empty.