Mathematics Lecture 7: Induction and Recursion Study Guide

Principles and Motivation of Mathematical Induction

The concept of mathematical induction is often illustrated through the analogy of climbing an infinite ladder. To successfully reach every rung of an infinite ladder, two conditions must be met. First, one must be able to reach the first rung of the ladder. Second, there must be a rule stating that if a particular rung can be reached, then the subsequent rung (the next one up) can also be reached. By starting at the first rung and repeatedly applying the second rule, one can eventually reach the second rung, then the third, and so on, reaching any specific rung no matter how high it is positioned. This logical progression serves as the foundation for proof by mathematical induction.

To formally prove that a proposition $P(n)$ is true for all positive integers $n$, the Principle of Mathematical Induction requires two distinct steps. The Basis Step involves showing that the proposition $P(1)$ is true. The Inductive Step involves showing that the conditional statement $P(k) ightarrow P(k+1)$ is true for all positive integers $k$. During the inductive step, we assume the inductive hypothesis, which is the assumption that $P(k)$ holds for an arbitrary integer $k$, and then demonstrate that $P(k+1)$ must necessarily be true based on that assumption. In the ladder analogy, the Basis Step corresponds to reaching the first rung, and the Inductive Step corresponds to the physical ability to move from rung $k$ to rung $k+1$. If both are verified, we conclude that we can reach every rung on the ladder.

Structural and Logical Properties of Induction

Mathematical induction is fundamentally a rule of inference where the domain is the set of positive integers. It can be expressed symbolically as $(P(1) \bigwedge orall k(P(k) ightarrow P(k+1))) ightarrow orall n P(n)$. It is critical to understand that a proof by induction does not involve assuming that $P(k)$ is true for all positive integers at the outset. Instead, we show that if the assumption is made for a single arbitrary integer $k$, the truth of the subsequent integer $k+1$ is guaranteed. Furthermore, while many proofs begin at the integer $1$, induction can start at any integer $b$. In such instances, the basis step begins by proving $P(b)$ is true rather than $P(1)$.

The validity of mathematical induction is derived from the well-ordering property, which states that every nonempty subset of the set of positive integers contains a least element. The proof of induction's validity proceeds by contradiction. Suppose that $P(1)$ holds and the implication $P(k) ightarrow P(k+1)$ is true for all $k$, but there exists at least one positive integer $n$ for which $P(n)$ is false. We can then define a set $S$ consisting of all positive integers for which $P(n)$ is false. Since $S$ is non-empty, the well-ordering property dictates it must have a least element, denoted as $m$. We know $m$ cannot be $1$ because $P(1)$ is true. Because $m$ is the smallest element in $S$ and m > 1, the integer $m-1$ must not be in $S$, meaning $P(m-1)$ is true. However, since the conditional $P(k) ightarrow P(k+1)$ holds for all integers, the truth of $P(m-1)$ implies the truth of $P(m)$. This creates a contradiction because $m$ was defined as an element of $S$ (where the proposition is false). Therefore, no such set of counterexamples can exist, and $P(n)$ must be true for all positive integers.

Another helpful visualization of induction is an infinite sequence of standing dominoes labeled $1, 2, 3, ext{…}, n$. If the first domino is knocked down (Basis Step, $P(1)$) and the distance between dominoes is such that whenever the $k ext{-th}$ domino falls, it knocks over the $(k+1) ext{-st}$ domino (Inductive Step, $P(k) ightarrow P(k+1)$), then all dominoes in the sequence will eventually fall. This implies $P(n)$ is true for every positive integer $n$.

Applications in Summation and Divisibility

Mathematical induction is a powerful tool for proving summation formulas. Consider the formula for the sum of the first $n$ positive integers: $rac{n(n+1)}{2}$. To prove this, the Basis Step shows $P(1)$ is true because $rac{1(1+1)}{2} = 1$. For the Inductive Step, we assume the inductive hypothesis: $1 + 2 + ext{…} + k = rac{k(k+1)}{2}$. We then add $(k+1)$ to both sides of the equation to show that the sum up to $k+1$ equals $rac{(k+1)(k+2)}{2}$. Once a conjecture like this is formed, induction serves to verify its correctness definitively.

A similar process is used for conjecturing and proving the sum of the first $n$ positive odd integers. By examining initial cases—$1=1^2$, $1+3=2^2$, and $1+3+5=3^2$—one can conjecture that $1 + 3 + 5 + ext{…} + (2n-1) = n^2$. To prove this using induction, the Basis Step confirms $P(1)$ since $1 = 1^2$. In the Inductive Step, we assume $P(k)$ holds: $1 + 3 + ext{…} + (2k-1) = k^2$. Adding the next odd integer, $(2k+1)$, to both sides yields $k^2 + 2k + 1$, which factors into $(k+1)^2$, completing the proof.

Induction is also used for divisibility results. For example, to prove that $n^3 - n$ is divisible by $3$ for every positive integer $n$, we define $P(n)$ as the proposition of divisibility. The Basis Step is true because $1^3 - 1 = 0$, which is divisible by $3$. For the Inductive Step, we assume $k^3 - k$ is divisible by $3$. We then examine $(k+1)^3 - (k+1)$, which expands to $k^3 + 3k^2 + 3k + 1 - k - 1$. Reorganizing terms gives $(k^3 - k) + 3(k^2 + k)$. By the inductive hypothesis, the first part is divisible by $3$, and the second part is clearly divisible by $3$ as it is a multiple of $3$. The sum of two integers divisible by $3$ is also divisible by $3$, thus proving the claim for all positive integers $n$.

Recursively Defined Functions and Sequences

A recursive or inductive definition of a function involves two steps. First, the Basis Step specifies the value of the function at zero or its starting point. Second, the Recursive Step provides a rule for finding the function's value at an integer based on its values at smaller integers. This process is equivalent to defining a sequence $a_0, a_1, a_2, ext{…}$ using recurrence relations. For example, if a function is defined as $f(0) = 3$ and $f(n+1) = f(n) + 2$, the values can be found sequentially: $f(1) = 3+2=5$, $f(2) = 5+2=7$, $f(3) = 7+2=9$, and so on. Similarly, the factorial function $n!$ can be defined recursively with the basis step $f(0) = 1$ and the recursive step $f(n+1) = (n+1)f(n)$. Summation of terms $a_i$ can also be defined recursively where the sum of the first $0$ terms is $a_0$ and the sum to $n+1$ is the sum to $n$ plus $a_{n+1}$.

Fibonacci Numbers and Strong Induction

The Fibonacci numbers are a classic example of a recursively defined sequence where the first two terms are fixed and subsequent terms are the sum of the two preceding terms. The definition is given by $f_0 = 0$, $f_1 = 1$, and $f_n = f_{n-1} + f_{n-2}$ for $n ightarrow 2$. This sequence generates values such as $f_2 = 1$, $f_3 = 2$, $f_4 = 3$, $f_5 = 5$, and so on. Fibonacci numbers were originally described by Fibonacci himself to model the population growth of rabbits. The study of these numbers often requires strong induction, a variant of induction where the inductive hypothesis assumes the proposition is true for all integers up to and including $k$ to prove the case for $k+1$.

An example of a result concerning Fibonacci numbers is the inequality f_n > ext{α}^{n-2} for $n ightarrow 3$, where $ext{α} = rac{1 + ext{√}5}{2}$. To prove this, we use strong induction. The basis step must check two initial cases: $P(3)$ holds because $f_3 = 2$ and 2 > ext{α}^{3-2} ext{≈} 1.618; $P(4)$ holds because $f_4 = 3$ and 3 > ext{α}^{4-2} ext{≈} 2.618. For the inductive step, we assume that the inequality f_j > ext{α}^{j-2} holds for all integers $j$ such that $3 ext{≤} j ext{≤} k$. To show it holds for $k+1$, we use the definition $f_{k+1} = f_k + f_{k-1}$. By the inductive hypothesis, f_{k+1} > ext{α}^{k-2} + ext{α}^{k-3}. Factoring out $ext{α}^{k-3}$ gives $ext{α}^{k-3}( ext{α} + 1)$. Since $ext{α}$ is a solution to the quadratic equation $x^2 - x - 1 = 0$, we know that $ext{α}^2 = ext{α} + 1$. Substituting this back into the expression, we get $ext{α}^{k-3} imes ext{α}^2 = ext{α}^{k-1}$. Because $(k+1)-2 = k-1$, it is shown that f_{k+1} > ext{α}^{(k+1)-2}, completing the strong induction proof.