172
Recursion, Recurrence Relations, and Analysis of Algorithms
7. P(1) = 1
P(n) = n
2
P(n − 1) + (n − 1) for n ≥ 2
8. A(1) = 2
A(n) = nA(n − 1) + n for n ≥ 2
9. M(1) = 2
M(2) = 2
M(n) = 2M(n − 1) + M(n − 2) for n > 2
10. D(1) = 3
D(2) = 5
D(n) = (n − 1)D(n − 1) + (n − 2)D(n − 2) for n > 2
11. W(1) = 2
W(2) = 3
W(n) = W(n − 1)W(n − 2) for n > 2
12. T(1) = 1
T(2) = 2
T(3) = 3
T(n) = T(n − 1) + 2T(n − 2) + 3T(n − 3) for n > 3
In Exercises 13–18, prove the given property of the Fibonacci numbers directly from the definition.
13. F(n + 1) + F(n − 2) = 2F(n) for n ≥ 3
14. F(n) = 5F(n − 4) + 3F(n − 5) for n ≥ 6
15. F(n) = 3F(n − 3) + 2F(n − 4) for n ≥ 5
16. [F(n + 1)]
2
= [F(n)]
2
+ F(n − 1)F(n + 2) for n ≥ 2
17. F(n + 3) = 2F(n + 1) + F(n) for n ≥ 1
18. F(n + 6) = 4F(n + 3) + F(n) for n ≥ 1
In Exercises 19–22, prove the given property of the Fibonacci numbers for all n ≥ 1. (Hint: The first principle
of induction will work.)
19. F(l) + F(2) + c + F(n) = F(n + 2) − 1
20. F(2) + F(4) + c + F(2n) = F(2n + 1) − 1
21. F(1) + F(3) + c + F(2n − 1) = F(2n)
22. [F(1)]
2
+ [F(2)]
2
+ c + [F(n)]
2
= F(n)F(n + 1)
In Exercises 23–26, prove the given property of the Fibonacci numbers using the second principle of induction.
23. Exercise 17
24. Exercise 18
25. F(n) < 2
n
for n ≥ 1
26. F(n) > a
3
2
b
n−1
for n ≥ 6