Solution: 2015 Fall Final - 8
Author: Michiel SmidQuestion
Consider the following recursive function:
Which of the following is true?
| $f(0) = $ | $7,$ |
| $f(n) = $ | $2 \cdot f(n - 1) + 1\; \ \text{for all}$ $\text{integers}\ n \geq 1.$ |
(a)
$f(n) = 8n + 7$
(b)
None of the above.
(c)
$f(n) = 4n^{2} + 4n + 7$
(d)
$f(n) = 2^{n+3} - 1$
Solution
Calculate $ f(1) $
$ f(1) = 2 \cdot f(0) + 1 = 2 \cdot 7 + 1 = 15 $
- $ f(n) = 8n + 7 $
$ f(1) = 8 \cdot 1 + 7 = 15 $ - $ f(n) = 4n^{2} + 4n + 7 $
$ f(1) = 4 \cdot 1^{2} + 4 \cdot 1 + 7 = 15 $ - $ f(n) = 2^{n+3} - 1$
$ f(1) = 2^{1+3} - 1 = 15 $ - None of the above
$ f(n) = 2^{n+3} - 1$ is true.