What is difference between strong and weak induction?

Answer

Padhai · Based on the official syllabus and past papers
Updated 29 Sept 2026

Strong Induction vs. Weak Induction

Feature	Weak Induction	Strong Induction
Base Case	Proves for P(0) or P(1).	Proves for P(0) or P(1).
Inductive Step	Assumes P(k) is true and proves P(k+1).	Assumes P(j) is true for all j ≤ k and proves P(k+1).
Scope	Works for statements where P(k+1) depends only on P(k).	Works for statements where P(k+1) depends on multiple previous cases (e.g., Fibonacci).
Use Case	Linear recurrences (e.g., $P (n) = P (n - 1) + 1$ ).	Non-linear recurrences (e.g., $P (n) = P (n - 1) + P (n - 2)$ ).

Discussion

Loading…