Mathematical Induction
Mathematical induction is a proof method by which we show that a statement holds for every natural number. It is particularly useful in proving formulas for sums, sequences, and divisibility statements.
Steps of Induction
- 1. Base case: verify the statement for the first number (usually n=1).
- 2. Inductive hypothesis: assume the statement holds for n.
- 3. Inductive step: prove that if it holds for n, then it holds for n+1.
Simple Example
Prove that the sum of the first n natural numbers is given by the following formula:
1. Base case: for n=1, left side = 1, right side = 1·(1+1)/2 = 1 → true. 2. Assume it holds for n. 3. Inductive step: adding n+1, the formula holds for n+1 as well. Thus, we have proven the statement for all n.
General Schema
The essence of inductive proof is that we don't need to perform the proof separately for every n: it's enough to prove the base case and the inductive step, and it will automatically hold for all subsequent cases.
When to Use?
- Proving sum formulas.
- Divisibility properties (e.g., a number is always divisible by something).
- Verifying the correctness of recursive definitions.
- Theorems in number theory.
Summary
With the method of mathematical induction, we can show that a statement holds for every natural number. It has two main parts: base case and inductive step. This is one of the most important proof techniques in mathematics.
Practice Exercise
We have reviewed and checked the materials, but errors may still occur. The content is provided for educational purposes only, so use it at your own responsibility and verify with other sources if needed.
✨ Ask Lara — your AI study partner
Unlock personalized learning support. Lara can explain lessons, summarize topics, and answer your study questions — available from the Go plan and above.
Lara helps you learn faster — exclusive to ReadyTools Go, Plus, and Max members.
