Mastering Strong and Weak Induction in Mathematics and Programming

Introduction

Mathematical induction is a powerful proof technique that allows us to establish the validity of statements over an infinite domain, particularly integers. It's a cornerstone of theoretical computer science and programming, especially in analyzing recursive algorithms and designing dynamic programming solutions. This article dives into weak induction and strong induction, explaining their differences, when to use each, and providing illustrative examples.

---

What is Weak Induction?

Weak induction, often called "simple induction," is a proof technique where the validity of a statement for $n+1$ depends only on its validity for $n$ . It consists of two steps:

1. Base Case: Prove the statement for the smallest value of $n$ , typically $n = 1$ or another defined starting point.
2. Inductive Step: Assume the statement is true for $n$ (the inductive hypothesis), and use this assumption to prove it for $n+1$ .

Example: Proving the Sum of the First $n$ Natural Numbers

We aim to prove that the sum of the first $n$ natural numbers is:

$S(n) = \frac{n(n+1)}{2}.$

1. Base Case: For $n = 1$ :

$S(1) = \frac{1(1+1)}{2} = 1.$

This matches the sum of the first natural number.

1. Inductive Step: Assume the formula holds for $n = k$ :

$S(k) = \frac{k(k+1)}{2}.$

Now, prove it for $n = k+1$ :

$S(k+1) = S(k) + (k+1).$

Substitute the inductive hypothesis:

$S(k+1) = \frac{k(k+1)}{2} + (k+1).$

Simplify:

$S(k+1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}.$

Thus, the formula holds for $n = k+1$ .

---

What is Strong Induction?

Strong induction builds on the same principle but assumes the statement is true for all previous cases up to $n$ , not just for $n$ itself. This assumption is particularly useful for problems where the current case depends on multiple prior cases.

Steps in Strong Induction:

1. Base Case(s): Prove the statement for the smallest value(s) of $n$ .
2. Inductive Hypothesis: Assume the statement is true for all values from the base case up to $n$ .
3. Inductive Step: Use the inductive hypothesis to prove the statement for $n+1$ .

Example: Fibonacci Numbers

Prove that $F_n < 2^n$ for all $n \geq 1$ , where $F_n$ is the Fibonacci sequence defined as:

$F_1 = 1, \, F_2 = 1, \, F_n = F_{n-1} + F_{n-2} \text{ for } n \geq 3.$

1. Base Cases:

   • For $n = 1$ : $F_1 = 1 < 2^1 = 2$ .
   • For $n = 2$ : $F_2 = 1 < 2^2 = 4$ .

2. Inductive Hypothesis: Assume $F_k < 2^k$ and $F_{k-1} < 2^{k-1}$ for all $k \geq 3$ .

3. Inductive Step: Prove $F_{k+1} < 2^{k+1}$ :

$F_{k+1} = F_k + F_{k-1}.$

By the inductive hypothesis:

$F_k < 2^k \, \text{and} \, F_{k-1} < 2^{k-1}.$

Adding:

$F_{k+1} < 2^k + 2^{k-1}.$

Factorize:

$2^k + 2^{k-1} = 2^{k-1}(2 + 1) = 2^{k-1} \cdot 3 < 2^{k+1}.$

Thus, the inequality holds for $n = k+1$ .

---

When to Use Weak vs. Strong Induction

• Weak Induction: Use when the proof for $(n+1)$ depends only on the result for $(n)$ . Example: Proving closed-form formulas for sums or products.
• Strong Induction: Use when the proof for $(n+1)$ relies on multiple earlier cases. Example: Recurrence relations, dynamic programming problems, or problems like Fibonacci sequences.

---

Dynamic Programming and Induction

Dynamic programming often relies on strong induction because solutions to subproblems are built using results from multiple prior subproblems. Here are two examples:

1. Tiling a $2 \times n$ Board

Problem: Find the number of ways to tile a $2 \times n$ board using $2 \times 1$ tiles.

Recurrence relation:

$T(n) = T(n-1) + T(n-2),$
with base cases $T(1) = 1$ and $T(2) = 2$ . Thus, we know base cases hold for $n = 1$ and $n = 2$

Using strong induction, we assume the recurrence holds for all $k \leq n$ , then prove it for $k+1$ :

Assumption:

$T(k) = 2 \times k$
$T(k-1) = 2 \times (k-1)$

Prove:

$T(k+1) = T(k) + T(k-1),$

Proof:

• If the last tile is vertical, the remaining board is $2 \times k$ , contributing $T(k)$ .

• If the last two tiles are horizontal, the remaining board is $2 \times (k-1)$ , contributing $T(k-1)$ .

Thus, $T(k+1) = T(k) + T(k-1)$ .

---

Exercise

2. Minimum Steps to Reduce $n$ to $1$

Problem: Reduce $n$ to $1$ using the following operations:

• Subtract 1 $(n \to n-1)$ .
• Divide by 2 $(n \to n/2)$ if $n$ is divisible by 2.
• Divide by 3 $(n \to n/3)$ if $n$ is divisible by 3.

Define $dp(n)$ as the minimum steps to reduce $n$ to 1:

---

$dp(n) = 1 + \min($

$$\begin{align} dp(n-1), \\ dp(n/2) \text{ if divisible by 2}, \\ dp(n/3) \text{ if divisible by 3} \\ \end{align}$$

$)$

---

Strong induction ensures $dp(k)$ is valid for all $1 \leq k \leq n$ , allowing us to build $dp(n+1)$ by combining solutions to subproblems.

---

Conclusion
Understanding the differences between weak and strong induction is critical for mathematical proofs and programming applications. While weak induction suffices for simple proofs, strong induction is indispensable for complex problems involving dependencies on multiple previous cases. Mastering these techniques will enhance your problem-solving skills in both mathematics and algorithm design.

Remember