CHAPTER 14: Mathematical Induction Study Guide

The Concept of Mathematical Induction

Mathematical induction is a powerful proof technique used to prove an infinite list of statements, typically indexed by natural numbers.
Motivation and Conjecture: Consider the conjecture that the sum of the first $n$ odd natural numbers equals $n^2$ . * For $n = 1$ : $1 = 1^2$ * For $n = 2$ : $1 + 3 = 4 = 2^2$ * For $n = 3$ : $1 + 3 + 5 = 9 = 3^2$ * For $n = 4$ : $1 + 3 + 5 + 7 = 16 = 4^2$ * For $n = 5$ : $1 + 3 + 5 + 7 + 9 = 25 = 5^2$
General Formula: The sum is represented as $1 + 3 + 5 + 7 + 9 + 11 + \cdots + (2n - 1) = n^2$ .
The nth Odd Number: The tables indicate that the $n^{th}$ odd natural number (the last term in the sum) is defined by the formula $2n - 1$ . * Example: When $n = 2$ , the second odd number is $2 \times 2 - 1 = 3$ . * Example: When $n = 3$ , the third odd number is $2 \times 3 - 1 = 5$ .
The Domino Analogy: To visualize induction, imagine statements $S_1, S_2, S_3, \dots$ as a row of dominoes. 1. If the first domino $S_1$ is knocked down (proved true). 2. If the falling of any domino $S_k$ (assuming it is true) necessarily causes the next domino $S_{k+1}$ to fall (proving the implication). 3. Conclusion: All dominoes in the sequence will fall (all statements are true).

Outline and Mechanism of Proof by Induction

Formal Outline for Proof by Induction: * Proposition: The statements $S_1, S_2, S_3, S_4, \dots$ are all true. * Proof Procedure: 1. Basis Step: Prove that the first statement $S_1$ is true. (Note: The index can start at values other than $1$ , such as $0$ or any integer $m$ ). 2. Inductive Step: Given any integer $k \ge 1$ , prove that the implication $S_k \Rightarrow S_{k+1}$ is true. 3. Conclusion: By mathematical induction, every $S_n$ is true.
Inductive Hypothesis: The assumption in the inductive step that $S_k$ is true is specifically called the inductive hypothesis.
Direct Proof in Induction: Step (2) is usually carried out using a direct proof: assume $S_k$ is true and demonstrate that this forces $S_{k+1}$ to be true.
Inductive Reasoning vs. Mathematical Induction: * Inductive Reasoning: Reaching a conclusion based on prior observations; the conclusion is "likely" but not certain. * Mathematical Induction: A rigorous mathematical method that provides absolute certainty for an infinite set of cases.

Examples of Proof by Induction

Example 1: Sum of First n Odd Numbers * Proposition: If $n \in \mathbb{N}$ , then $1 + 3 + 5 + 7 + \cdots + (2n - 1) = n^2$ . * Basis Step: For $n = 1$ , $1 = 1^2$ is true. * Inductive Step: Suppose $1 + 3 + 5 + 7 + \cdots + (2k - 1) = k^2$ . We examine the sum for $k+1$ : * $1 + 3 + 5 + \cdots + (2k - 1) + (2(k + 1) - 1)$ * $= (1 + 3 + 5 + \cdots + (2k - 1)) + (2k + 1)$ * $= k^2 + 2k + 1$ (using the inductive hypothesis) * $= (k + 1)^2$ . * Thus, the proposition holds for all $n \in \mathbb{N}$ .
Example 2: Divisibility * Proposition: If $n$ is a non-negative integer, then $5 | (n^5 - n)$ . * Basis Step: For $n = 0$ , $5 | (0^5 - 0)$ which is $5 | 0$ , true. * Inductive Step: Suppose $5 | (k^5 - k)$ , meaning $k^5 - k = 5a$ for some integer $a$ . * $(k + 1)^5 - (k + 1) = k^5 + 5k^4 + 10k^3 + 10k^2 + 5k + 1 - k - 1$ * $= (k^5 - k) + 5k^4 + 10k^3 + 10k^2 + 5k$ * $= 5a + 5k^4 + 10k^3 + 10k^2 + 5k = 5(a + k^4 + 2k^3 + 2k^2 + k)$ . * Since this is a multiple of $5$ , the statement holds.
Example 3: Summation with Factorials * Proposition: If $n \in \mathbb{Z}$ and $n \ge 0$ , then $\sum_{i=0}^{n} i \cdot i! = (n + 1)! - 1$ . * Basis Step: For $n = 0$ , $0 \cdot 0! = 0$ and $(0 + 1)! - 1 = 1 - 1 = 0$ . True. * Inductive Step: Assume $\sum_{i=0}^{k} i \cdot i! = (k + 1)! - 1$ . * $\sum_{i=0}^{k+1} i \cdot i! = \left(\sum_{i=0}^{k} i \cdot i!\right) + (k + 1)(k + 1)!$ * $= (k + 1)! - 1 + (k + 1)(k + 1)!$ * $= (k + 1)!(1 + k + 1) - 1 = (k + 1)!(k + 2) - 1 = (k + 2)! - 1$ . True.
Example 4: Inequalities and Inequality Addition * Logic Rule: If $x \le y$ and $a \le b$ , then $x + a \le y + b$ . Also, if $x \le y$ and $b$ is positive, then $x \le y + b$ . * Proposition: $2^n \le 2^{n+1} - 2^{n-1} - 1$ for each $n \in \mathbb{N}$ . * Basis Step: For $n = 1$ , $2^1 \le 2^2 - 2^0 - 1 \Rightarrow 2 \le 4 - 1 - 1 = 2$ . True. * Inductive Step: Suppose $2^k \le 2^{k+1} - 2^{k-1} - 1$ . * Multiply by $2$ : $2^{k+1} \le 2^{k+2} - 2^k - 2$ . * Add $1$ to the larger side: $2^{k+1} \le 2^{k+2} - 2^k - 1$ . * This equals $2^{(k+1)+1} - 2^{(k+1)-1} - 1$ . True.
Example 5: Bernoulli’s Inequality * Proposition: If $n \in \mathbb{N}$ , then $(1+x)^n \ge 1+nx$ for all $x \in \mathbb{R}$ with x > -1. * Basis Step: For $n = 1$ , $(1+x)^1 = 1+x$ , true. * Inductive Step: Assume $(1+x)^k \ge 1 + kx$ . Since x > -1, (1+x) > 0. * $(1+x)^k(1+x) \ge (1+kx)(1+x)$ * $(1+x)^{k+1} \ge 1 + x + kx + kx^2 = 1 + (k+1)x + kx^2$ * Since $kx^2 \ge 0$ , removing it preserves the inequality: $(1+x)^{k+1} \ge 1 + (k+1)x$ .
Example 6: Prime Divisibility of a Product (Proposition 14.1) * Proposition: Let $a_1, a_2, \dots, a_n$ be $n$ integers ( $n \ge 2$ ). If $p$ is prime and $p | (a_1 a_2 a_3 \cdots a_n)$ , then $p | a_i$ for at least one $i$ . * Basis Step ( $n = 2$ ): Suppose $p | a_1 a_2$ . If $p$ does not divide $a_1$ , then $gcd(p, a_1) = 1$ . By identity, $1 = pk + a_1 l$ . Multiplying by $a_2$ gives $a_2 = pka_2 + a_1 a_2 l$ . Since $p$ divides both terms on the right, $p | a_2$ . * Inductive Step: Assume the property holds for $k$ integers. For $k+1$ integers: $p | (a_1 \cdots a_k) a_{k+1}$ . By the basis case, $p | (a_1 \cdots a_k)$ or $p | a_{k+1}$ . If $p | (a_1 \cdots a_k)$ , the inductive hypothesis ensures $p$ divides one of $a_1, \dots, a_k$ .

Induction in Recursive Procedures

Recursion Definition: A procedure is recursive if there is a call to the procedure within its own body.
RFac Procedure Example: Procedure RFac(n) 1 begin 2 if n = 0 then 3 return 1 4 else 5 return n * RFac(n - 1) 6 end 7 end     
Proposition: For a non-negative integer $n$ , RFac(n) returns $n!$ .
Proof by Induction: 1. Basis Step: For $n = 0$ , the code returns $1$ (line 3), which is $0!$ . True. 2. Inductive Step: Assume RFac(k) returns $k!$ . * For RFac(k+1), since $k+1 \ne 0$ , the code executes line 5: returns $(k+1) \times RFac(k)$ . * By hypothesis, this is $(k+1) \times k! = (k+1)!$ . 3. Conclusion: RFac(n) correctly calculates $n!$ for all non-negative $n$ .

Proof by Strong Induction

Motivation: Regular induction assumes only $S_k$ to prove $S_{k+1}$ . Strong induction is used when Sk alone does not easily imply $S_{k+1}$ . Instead, you may need information from multiple preceding steps.
Mechanism: Assume that all statements from the first up to index $k$ ( $S_1, S_2, \dots, S_k$ ) are true, then show this forces $S_{k+1}$ to be true.
Outline for Strong Induction: 1. Basis Step: Prove the first statement $S_1$ (or first several, if necessary). 2. Inductive Step: Given $k \ge 1$ , prove $(S_1 \wedge S_2 \wedge S_3 \wedge \cdots \wedge S_k) \Rightarrow S_{k+1}$ .
Example 1: Postage Problem * Proposition: Any postage of $8 \text{ cents}$ or more can be achieved using only $3¢$ and $5¢$ stamps. * Basis Case: * $8¢ = 3¢ + 5¢$ * $9¢ = 3¢ + 3¢ + 3¢$ * $10¢ = 5¢ + 5¢$ * Inductive Step: Assume statements $S_8, \dots, S_k$ are all true for $k \ge 10$ . To prove $S_{k+1}$ , consider $S_{k-2}$ . By hypothesis, $k-2 \ge 8$ is true. We can get $(k-2)¢$ postage. Adding one $3¢$ stamp yields $(k-2) + 3 = k+1$ cents.
Example 2: Divisibility by 12 * Proposition: If $n \in \mathbb{N}$ , then $12 | (n^4 - n^2)$ . * Issue with Regular Induction: Expansion results in $12a + 4k^3 + 6k^2 + 6k$ , where $12$ cannot be easily factored out. * Strong Induction Strategy: Use $S_{k-5} \Rightarrow S_{k+1}$ . * Basis Step: Verify for $n = 1, 2, 3, 4, 5, 6$ . * $1^4 - 1^2 = 0$ ; $2^4 - 2^2 = 12$ ; $3^4 - 3^2 = 72$ ; $4^4 - 4^2 = 240$ ; $5^4 - 5^2 = 600$ ; $6^4 - 6^2 = 1260$ . All are multiples of $12$ . * Inductive Step: For $k \ge 6$ , let $k-5 = l$ . If $S_l$ is true, then $l^4 - l^2 = 12a$ . For $k+1 = l+6$ : * $(l+6)^4 - (l+6)^2 = l^4 + 24l^3 + 216l^2 + 864l + 1296 - (l^2 + 12l + 36)$ * $= (l^4 - l^2) + 24l^3 + 216l^2 + 852l + 1260$ * $= 12a + 24l^3 + 216l^2 + 852l + 1260 = 12(a + 2l^3 + 18l^2 + 71l + 105)$ . True.
Example 3: Graph Theory and Trees * Definitions: * Graph: A configuration of points (vertices) and lines (edges). * Cycle: A sequence of distinct edges forming a route that ends where it began. * Tree: A connected graph with no cycles. * Proposition: If a tree has $n$ vertices, then it has $n-1$ edges. * Proof: Strong induction is required because removing an edge from a tree with $k+1$ vertices creates two trees, $T_1$ (with $x$ vertices) and $T_2$ (with $y$ vertices), where x, y < k+1. * Inductive Hypothesis: Trees with $m$ vertices ( $1 \le m \le k$ ) have $m-1$ edges. * Total Edges for k+1 vertices: (Edges in $T_1$ ) + (Edges in $T_2$ ) + (the removed edge $e$ ) * $= (x - 1) + (y - 1) + 1 = (x + y) - 1 = (k+1) - 1 = k$ .

Proof by Smallest Counterexample

Definition: A hybrid of induction and proof by contradiction.
Outline: 1. Verify the basis step $S_1$ . 2. Assume for contradiction that not every $S_n$ is true. 3. Define k > 1 as the smallest integer for which $S_k$ is false. 4. This implies $S_{k-1}$ is true. Use the truth of $S_{k-1}$ and the falsity of $S_k$ to derive a contradiction.
Example: Divisibility * Proposition: If $n \in \mathbb{N}$ , then $4 | (5^n - 1)$ . * Basis Step: $4 | (5^1 - 1) \Rightarrow 4 | 4$ . True. * Contradiction Setup: Let $k$ be the smallest integer such that $4$ does not divide $5^k - 1$ . * Logic: Then $4 | (5^{k-1} - 1)$ , so $5^{k-1} - 1 = 4a$ . * Multiply by $5$ : $5^k - 5 = 20a$ * $5^k - 1 = 20a + 4 = 4(5a + 1)$ . * This shows $4 | (5^k - 1)$ , contradicting the assumption that $S_k$ was false.

The Fundamental Theorem of Arithmetic

Theorem: Any integer n > 1 has a unique prime factorization.
Existence Proof (Strong Induction): * Basis: $n = 2$ is prime. * Inductive Step: For $n+1$ , if prime, done. If composite, $n+1 = ab$ where a, b < n+1. Since $a, b$ have prime factorizations (by hypothesis), their product is the factorization for $n+1$ .
Uniqueness Proof (Smallest Counterexample): * Assume there is a smallest integer $n$ with two different factorizations: $n = p_1 p_2 \cdots p_k = a_1 a_2 \cdots a_l$ . * $p_1 | n \Rightarrow p_1 | (a_1 a_2 \cdots a_l)$ . By Proposition 14.1, $p_1$ must equal one of the $a_i$ (say $a_1$ ). * Divide both sides by $p_1$ : the remaining product is a smaller number with two different factorizations, contradicting that $n$ was the smallest.

Fibonacci Numbers and Identities

Leonardo Pisano (Fibonacci): Born around $1175$ , Italy. Known for Liber Abaci, promoting Hindu-Arabic numbers.
The Fibonacci Sequence: $1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, \dots$
Recursive Rules: $F_1 = 1, F_2 = 1, F_n = F_{n-1} + F_{n-2}$ .
Fibonacci Identity Proposition: $F_{n+1}^2 - F_{n+1} F_n - F_n^2 = (-1)^n$ . * Example for n=5: $F_6^2 - F_6 F_5 - F_5^2 = 8^2 - (8 \times 5) - 5^2 = 64 - 40 - 25 = -1 = (-1)^5$ . * Proof by Induction: 1. Basis: $(n=1)$ $F_2^2 - F_2 F_1 - F_1^2 = 1^2 - (1 \times 1) - 1^2 = -1 = (-1)^1$ . 2. Inductive Step: Assume true for $k$ . For $k+1$ , use $F_{k+2} = F_{k+1} + F_k$ : * $F_{k+2}^2 - F_{k+2} F_{k+1} - F_{k+1}^2$ * $= (F_{k+1} + F_k)^2 - (F_{k+1} + F_k) F_{k+1} - F_{k+1}^2$ * $= F_{k+1}^2 + 2 F_{k+1} F_k + F_k^2 - F_{k+1}^2 - F_k F_{k+1} - F_{k+1}^2$ * $= -F_{k+1}^2 + F_{k+1} F_k + F_k^2 = -(F_{k+1}^2 - F_{k+1} F_k - F_k^2)$ * $= -(-1)^k = (-1)^{k+1}$ .
Convergence to the Golden Ratio (\Phi): * The ratio $\frac{F_{n+1}}{F_n}$ satisfies the polynomial $x^2 - x - 1 = 0$ as $n \to \infty$ . * The roots are $\frac{1 \pm \sqrt{5}}{2}$ . The positive root is $\Phi = \frac{1 + \sqrt{5}}{2} \approx 1.618033$ . * Example: $\frac{F_{13}}{F_{12}} \approx 1.618025$ . * Relationship: Fibonacci numbers behave like a geometric sequence with ratio $\Phi$ the further the sequence progresses.

Mathematical Induction Exercises

Sum of integers: $1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$ .
Sum of squares: $1^2 + 2^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}$ .
Sum of cubes: $1^3 + 2^3 + \cdots + n^3 = \frac{n^2(n+1)^2}{4}$ .
Product sum: $1 \cdot 2 + 2 \cdot 3 + \cdots + n(n+1) = \frac{n(n+1)(n+2)}{3}$ .
Geometric sum: $2^1 + 2^2 + \cdots + 2^n = 2^{n+1} - 2$ .
Factorial fractions: $\frac{1}{2!} + \frac{2}{3!} + \cdots + \frac{n}{(n+1)!} = 1 - \frac{1}{(n+1)!}$ .
Divisibility: Prove $24 | (5^{2n} - 1)$ for $n \ge 0$ .
Generalized De Morgan’s Laws: ( \overline{A_1 \cup A_2 \cup \dots \cup A_n} = \overline{A_1} \cap \overline{A_2} \cap \dots \cap \overline{A_n} ).
Harmonic Series divergence: $1 + \frac{1}{2} + \dots + \frac{1}{2^n} \ge 1 + \frac{n}{2}$ .
Binet’s Formula: Prove $F_n = \frac{(\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n}{\sqrt{5}}$ .
Plane Division: $n$ straight lines (no two parallel, no three intersecting at a point) divide the plane into $\frac{n^2+n+2}{2}$ regions.