It is also enough to prove P(1) and derive P(k+1) by assuming P(1), P(2), …, P(k).
This is used for properties of the Fibonacci sequence and similar topics.
Example ① For the Fibonacci sequence F_1=F_2=1, F_{n+2}=F_{n+1}+F_n, prove F_n < 2ⁿ.
Solution:n=1,2: 1<2, 1<4 OK.
Assume it holds for n=k and k+1 → F_{k+2} = F_{k+1}+F_k < 2ᵏ⁺¹+2ᵏ = 3·2ᵏ < 4·2ᵏ = 2ᵏ⁺².
Therefore, F_n < 2ⁿ.
Solution:n=1,2: 1<2, 1<4 OK.
Assume it holds for n=k and k+1 → F_{k+2} = F_{k+1}+F_k < 2ᵏ⁺¹+2ᵏ = 3·2ᵏ < 4·2ᵏ = 2ᵏ⁺².
Therefore, F_n < 2ⁿ.
Key Point
- When the recurrence relation skips two terms, use strong induction with two assumptions
Practice Problems
- Define F_n by F_{n+2}=F_{n+1}+F_n, F_1=F_2=1. What are F_3, F_4, and F_5?
Solutions and Explanations
- Solution:F_3=2, F_4=3, F_5=5