DEV Community

Cover image for Mastering Strong and Weak Induction in Mathematics and Programming
Piyush Chauhan
Piyush Chauhan

Posted on

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.

Mathematical Induction


What is Weak Induction?

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

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

Example: Proving the Sum of the First nn Natural Numbers

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

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

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

S(1)=1(1+1)2=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=kn = k :

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

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

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

Substitute the inductive hypothesis:

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

Simplify:

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

Thus, the formula holds for n=k+1n = 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 nn , not just for nn 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 nn .
  2. Inductive Hypothesis: Assume the statement is true for all values from the base case up to nn .
  3. Inductive Step: Use the inductive hypothesis to prove the statement for n+1n+1 .

Example: Fibonacci Numbers

Prove that Fn<2nF_n < 2^n for all n1n \geq 1 , where FnF_n is the Fibonacci sequence defined as:

F1=1,F2=1,Fn=Fn1+Fn2 for n3.F_1 = 1, \, F_2 = 1, \, F_n = F_{n-1} + F_{n-2} \text{ for } n \geq 3.

  1. Base Cases:

    • For n=1n = 1 : F1=1<21=2F_1 = 1 < 2^1 = 2 .
    • For n=2n = 2 : F2=1<22=4F_2 = 1 < 2^2 = 4 .
  2. Inductive Hypothesis: Assume Fk<2kF_k < 2^k and Fk1<2k1F_{k-1} < 2^{k-1} for all k3k \geq 3 .

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

Fk+1=Fk+Fk1.F_{k+1} = F_k + F_{k-1}.

By the inductive hypothesis:

Fk<2kandFk1<2k1.F_k < 2^k \, \text{and} \, F_{k-1} < 2^{k-1}.

Adding:

Fk+1<2k+2k1.F_{k+1} < 2^k + 2^{k-1}.

Factorize:

2k+2k1=2k1(2+1)=2k13<2k+1.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+1n = k+1 .


When to Use Weak vs. Strong Induction

  • Weak Induction: Use when the proof for (n+1)(n+1) depends only on the result for (n)(n) . Example: Proving closed-form formulas for sums or products.
  • Strong Induction: Use when the proof for (n+1)(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×n2 \times n Board

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

Recurrence relation:

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

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

Assumption:

T(k)=2×kT(k) = 2 \times k
T(k1)=2×(k1)T(k-1) = 2 \times (k-1)

Prove:

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

Proof:

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

Vertical Last Tile

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

Horizontal Last Two Tiles

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


Exercise

2. Minimum Steps to Reduce nn to 11

Problem: Reduce nn to 11 using the following operations:

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

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


dp(n)=1+min{dp(n1),dp(n/2) if divisible by 2,dp(n/3) if divisible by 3 dp(n) = 1 + \min \begin{cases} dp(n-1), \\ dp(n/2) \text{ if divisible by 2}, \\ dp(n/3) \text{ if divisible by 3} \end{cases}

Strong induction ensures dp(k)dp(k) is valid for all 1kn1 \leq k \leq n , allowing us to build dp(n+1)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

Mathematical Induction Key Points

Top comments (0)