Set6 - Induction and Recursion - Lecture Notes

Induction and Recursion

Themes of the Lecture

• Principle of Mathematical Induction: This is the most important topic, especially concerning the exam, providing a method to prove statements for an infinite number of parameters like all natural numbers.
• Well-Ordering Principle: It is logically equivalent to the principle of mathematical induction. This principle can help to show the principle of mathematical induction is true.
• Sequences and Recursion: They're related to mathematical induction by providing examples where mathematical induction can be applied. This serves as the core motivation.
• Transitive Closure: This topic relates back to lecture two and focuses on relations, ordering relations, and equivalence relations to complete the discussion.

Principle of Mathematical Induction

• Used for theorems involving a statement $s$ that depends on an integer $n$, denoted as $s_n$, to prove it holds for all integers greater than or equal to a starting integer $a$.
• Proves an infinite number of statements by proving just two things:
  • Base Case: Prove the statement holds for the integer $n = a$. This is usually straightforward.
  • Inductive Step: Prove that if the statement holds for $n = m$, then it also holds for $n = m + 1$, i.e., $s<em>m \implies s</em>{m+1}$ for all $m \geq a$.
• After proving the inductive step showing that $s<em>a \implies s</em>{a+1}$, we can show that $s_{a+1}$ holds true.
• Knowing that $s<em>{a+1}$ holds true, as $s</em>{a+1} \implies s<em>{a+2}$, we can argue that $s</em>{a+2}$ holds true.
• Iterating this way, we can prove that $s$ holds for any arbitrary integer $n$.
• The inductive step needs to be iterated $n - a$ times to reach the integer $n$.
• The principle of mathematical induction goes beyond first-order logic.
• Formal Statement: Assuming $s<em>a$ holds true (base case), and for all $m \geq a$, $s</em>m \implies s<em>{m+1}$ (inductive step), then for all $n \geq a$, $s</em>n$ holds true.

Practical Application of Mathematical Induction

1. Base Case: Prove that $s_a$ is true. Often, this is trivial.
2. Inductive Step: For any $m \geq a$, prove that $s<em>m \implies s</em>{m+1}$.
   • Choose an arbitrary $m \geq a$. This is standard.
   • Assume that $s_m$ holds true (Induction Hypothesis or IH).
   • Show that this assumption implies $s_n$ for $n = m + 1$.

Example 1

Prove that $\sum_{k=0}^{n} 2^k = 2^{n+1} - 1$ for all non-negative integers $n$.

• Base Case: For $n = 0$, the sum is just $2^0 = 1$. And $2^{0+1} - 1 = 2 - 1 = 1$.
• Inductive Step:
  • Let $m \geq 0$ be arbitrary.
  • Assume that $\sum_{k=0}^{m} 2^k = 2^{m+1} - 1$ (IH).
  • We want to show that $\sum_{k=0}^{m+1} 2^k = 2^{(m+1)+1} - 1 = 2^{m+2} - 1$.
  • Starting with the left side, we have:
    $\sum<em>{k=0}^{m+1} 2^k = \sum</em>{k=0}^{m} 2^k + 2^{m+1}$
  • Using the induction hypothesis, we replace the sum up to $m$:
    $= (2^{m+1} - 1) + 2^{m+1}$
    $= 2 * 2^{m+1} - 1$
    $= 2^{m+2} - 1$
  • This matches the right side of the desired result.

Example 2

Prove that $\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$ for all integers $n \geq 1$.

• Base Case: For $n = 1$, the sum is just $1$. And $\frac{1(1+1)}{2} = \frac{2}{2} = 1$.
• Inductive Step:
  • Let $m \geq 1$ be arbitrary.
  • Assume that $\sum_{k=1}^{m} k = \frac{m(m+1)}{2}$ (IH).
  • We want to show that $\sum_{k=1}^{m+1} k = \frac{(m+1)((m+1)+1)}{2} = \frac{(m+1)(m+2)}{2}$.
  • Starting with the left side, we have:
    $\sum<em>{k=1}^{m+1} k = \sum</em>{k=1}^{m} k + (m+1)$
  • Using the induction hypothesis, we replace the sum up to $m$:
    $= \frac{m(m+1)}{2} + (m+1)$
    $= \frac{m(m+1) + 2(m+1)}{2}$
    $= \frac{(m+1)(m+2)}{2}$
  • This matches the right side of the desired result.

Well-Ordering Principle

• Given a partially ordered set $B$ and a subset $A$ of $B$, an element $b \in B$ is a lower bound for $A$ if $b \leq a$ for all $a \in A$.
• Zero is a lower bound for the set of all positive integers, rational numbers, and real numbers.
• The Well-Ordering Principle states that every non-empty subset $A$ of the set of integers $\mathbb{Z}$ that has a lower bound also has a smallest element.
• The set of rational numbers does not satisfy the well-ordering principle. Zero is a lower bound for the set of all positive rational numbers, but there is no smallest positive rational number.
• The well-ordering principle is logically equivalent to the principle of mathematical induction.

Well-Ordering Implies Mathematical Induction

• Assume the base case $s<em>a$ holds true, and the inductive step $s</em>m \implies s_{m+1}$ is true for all $m \geq a$.
• Define the set $A$ as the set of all integers $n \geq a$ for which $s_n$ is false.
• If A is non-empty, it has a lower bound, $a$. If true then A has a smallest element. Let it be $n$. The n must be greater than $a$.
• Therefore, $s<em>n$ is false, but $s</em>{n-1}$ is true. However, the inductive step states that if $s<em>{n-1}$ is true, then $s</em>n$ must also be true. This is a contradiction.
• Therefore, A must be empty, implying that $s_n$ is true for all $n \geq a$.

Mathematical Induction Implies Well-Ordering

• Assume that every subset of the integers having a lower bound has a smallest element and assume by contradiction that a subset has no smallest element, then we deduce that it must be empty.
• For all integers k < n, and for all integers $n \geq b$, show that k cannot belong to A.
• Prove the base case. In the case where $n = b$, and for all k < n, k will not belong to A because b is the lower bound.
• Apply the inductive step and you can conclude that A has to be empty.

Sequences and Recursion

• A sequence is a function from the set of natural numbers to an arbitrary set A. For any natural number $n$, it assigns an element in the set A.
• A common notation is $t<em>n$, where n is a parameter and $t</em>n$ is the nth term of the sequence.
• Sequences are often defined recursively.
• Geometric Sequence: Defined recursively with a base case $t<em>0 = c$ and $t</em>{n+1} = rt<em>n$, where r is a real number. The closed formula is $t</em>n = cr^n$.
• Factorials: Defined recursively with $t<em>0 = 1$ and $t</em>{n+1} = (n+1)t_n$. This results in multiplying all natural numbers up to n. No closed formula for this, and it is abbreviated by $n!$. $n! = n * (n-1) * (n-2) … 1$

Example: Number of Diagonals of an $n$-gon

• $t_n$ is the number of diagonals of an n-gon.
• Recursive definition:
  • $t<em>3 = 0$, $t</em>4 = 2$, $t_5 = 5$
  • $t<em>{n+1} = t</em>n + n - 1$
• Closed formula: $t_n = \frac{n(n-3)}{2}$

Proof using Mathematical Induction:

• Base Case: For $n=3$, $t_3 = 0$. And $\frac{3(3-3)}{2} = 0$.
• Inductive Step:
  • Let $m \geq 3$ be arbitrary.
  • Assume that $t_m = \frac{m(m-3)}{2}$ (IH).
  • We want to show that $t_{m+1} = \frac{(m+1)((m+1)-3)}{2} = \frac{(m+1)(m-2)}{2}$.
  • Using the recursion formula and the induction hypothesis:
    $t<em>{m+1} = t</em>m + m - 1 = \frac{m(m-3)}{2} + m - 1$
    $= \frac{m^2 - 3m + 2m - 2}{2}$
    $= \frac{m^2 - m - 2}{2}$
    $= \frac{(m+1)(m-2)}{2}$
  • This matches the right side of the desired result.

Transitive Closure

• A binary relation $R$ in a set $A$ is a subset of the Cartesian product of $A$ with itself, $A \times A$.
• The relation $R^n$ is defined recursively by $R^1 = R$ and $R^{n+1} = R^n \circ R$, where $\circ$ denotes the composition of relations.
• $R^n$ represents a path of exactly $n$ steps from $x$ to $y$ in the directed graph representation of $R$.
• The transitive closure of a binary relation $R$, denoted as $R^*$, is the smallest transitive relation containing $R$.
• $R^*$ is defined as the union of all $R^n$ for $n \geq 1$, i.e., there's a path of finite length from $x$ to $y$ in the directed graph.
• If the relation is already transitive, nothing changes.
• If using a Hasse Diagram start by adding the reflexive arrows, that you may have an easier time interpreting it.