STEP-BY-STEP LESSON · §5.3
Mathematical Induction II: Applications
Apply induction to an inequality and justify each comparison.
Before you begin
Mathematical Induction I: Proving Formulas
P(n) must be a specific statement for every integer n in the stated range.
P(n): 1+2+…+n = n(n+1)/2, n≥1
Verify P(1) separately. Then choose arbitrary k≥1 and temporarily assume P(k).
1 = 1·2/2
Split the sum through k+1 into the known sum through k and the final term.
k(k+1)/2+(k+1)=(k+1)(k+2)/2
Symbols
- ≥
- greater than or equal to
Step by step
Step 1 / 6
Choose the range
An inequality may not hold at every index. Check the specified starting point.
2^n ≥ n+1, n≥0
At n=0 both sides equal 1.
Worked example
Prove 2^n≥n+1 for integers n≥0.
- Base: 2^0=1=0+1.
- For arbitrary k≥0, assume 2^k≥k+1. Then 2^(k+1)=2·2^k≥2k+2.
- Since 2k+2≥k+2, P(k+1) follows. The base and step prove the claim.
Optional self-check
Why is 2k+2≥k+2 when k≥0?
Show answer
The left side minus the right side is k≥0.