Prove that f(n) is a multiple of m for every natural number n.
Use the assumption f(k) = m·M to express f(k+1) as a multiple of m.
Example ① Prove that 5ⁿ + 3 is a multiple of 4.
Solution:n=1: 5+3=8=4·2 OK.
Assume n=k: 5ᵏ+3 = 4M. For n=k+1: 5ᵏ⁺¹+3 = 5·5ᵏ+3 = 5(4M−3)+3 = 20M − 12 = 4(5M−3).
Therefore, it is a multiple of 4.
Solution:n=1: 5+3=8=4·2 OK.
Assume n=k: 5ᵏ+3 = 4M. For n=k+1: 5ᵏ⁺¹+3 = 5·5ᵏ+3 = 5(4M−3)+3 = 20M − 12 = 4(5M−3).
Therefore, it is a multiple of 4.
Key Point
- Set the assumption as “f(k) = m·M,” then connect it to the next step
Practice Problems
- Prove that 3ⁿ − 1 is a multiple of 2.
Solutions and Explanations
- Solution:n=1: 2 OK. Assume 3ᵏ−1=2M. For n=k+1: 3ᵏ⁺¹−1=3(2M+1)−1=6M+2=2(3M+1).