Ch 5. Solutions

1. A sequence is an ordered list of numbers that follow a specific rule of pattern. The Fibonacci sequence is widely used in computing.
3. 1, 3, 5, 7, 9
5. a) valid,    b) not valid,    c) not valid
9. 62
13. A, J, E, K, I
15. 70
17. 3, 5, 7, 9, 11
19. [latex]a_{n} = 7[/latex] for all [latex]n \geq 0[/latex]
21. [latex]t_{n} = 5n + 5[/latex]
23. 1, 2, 4, 8, 16
25. [latex]f_{n} = n f_{n-1}[/latex]
27. [latex]m_{n} = 2n^{2} + 6n[/latex]
31. An algorithm is a finite, well-defined sequence of steps designed to solve a specific problem or perform a computation. An algorithm is formal and rigorous, while a general procedure may be informal or descriptive.
33. Recursive algorithm
35. a → iv, b → ii, c → iii, d → i, e → v
37. 24 estimated operations
39. mystery(n)[latex]= 2^{n-1}[/latex].
41. [latex]t_{n} = \frac{1}{\sqrt{5}} \left( \left( \frac{1+\sqrt{5}}{2} \right) ^{n} - \left( \frac{1 - \sqrt{5}}{2} \right) ^{n} \right)[/latex]
43. [latex]t_{n} = 3 t_{\frac{n}{2}} + cn = n^{\text{log}_{2}3}(t_{1} + 2c) - 2cn[/latex]
45. [latex]t_{1} = c, t_{n} = t_{n-1} + \text{log } n = c + \text{log}(n!)[/latex]
47. The base case is the condition in a recursive algorithm that terminates the recursion. It defined the simplest instance of the problem, which can be solved directly without further recursive calls. It’s essential because it prevents infinite recursion, ensures the algorithm terminates, and provides a foundation for solving larger problems.
49. Big O notation represents the worst-case growth rate of an algorithm.
51. [latex]t_{0} = c, t_{n} = t_{n-1} + c = O(n)[/latex]
55. [latex]t_{n} = t_{n-1} + t_{n-2} + t_{n-3}[/latex], where [latex]t_{0}[/latex], [latex]t_{1}[/latex], [latex]t_{2}[/latex] are constants.
57.  a) [latex]t_{n} = 4 t_{\frac{n}{2}} + cn^{2}[/latex],     b) [latex]O(n^{4})[/latex]
59. a) [latex]c_{n} = c_{n-1} + c_{n-2} + 1[/latex], where [latex]c_{0} = c_{1} = 1[/latex]