Example ① Prove by induction that a_n = 2ⁿ − 1 for the recurrence relation a_1=1, a_{n+1}=2a_n+1.
Solution:n=1: 2−1=1 OK.
Assume n=k: a_k = 2ᵏ−1. For n=k+1: a_{k+1}=2(2ᵏ−1)+1 = 2ᵏ⁺¹−1.
Solution:n=1: 2−1=1 OK.
Assume n=k: a_k = 2ᵏ−1. For n=k+1: a_{k+1}=2(2ᵏ−1)+1 = 2ᵏ⁺¹−1.
Key Point
- It is also common to predict the general term from the recurrence relation and then verify it by induction
Practice Problems
- Prove by induction, in outline, that 1²+2²+…+n² = n(n+1)(2n+1)/6.
Solutions and Explanations
- Solution:n=1: 1=1 OK. Assume the result, add (k+1)² to both sides, and simplify to (k+1)(k+2)(2k+3)/6.