Solution: 2019 Winter Final - 10
Author: Michiel SmidQuestion
The function $f : \mathbb{N} \rightarrow \mathbb{N}$ is recursively defined as follows:
$$
\begin{align}
f(0) &= 2 \\
f(n) &= 3 \cdot f(n - 1) + 1, \text{ if } n \geq 1
\end{align}
$$
Which of the following is true for all integers $n \geq 0$?
(a)
$f(n) = \frac{3}{2} \cdot 3^n - \frac{1}{2}$
(b)
$f(n) = \frac{5}{2} \cdot 3^n - \frac{1}{2}$
(c)
None of the above.
(d)
$f(n) = \frac{5}{2} \cdot 3^n - 1$
Solution
-
Let’s calculat ethe first few values of $f(n)$ to see if we can find a pattern:
$ f(1) = 3 \cdot f(0) + 1 = 3 \cdot 2 + 1 = 7 $
-
Let’s see how the functions behave
- $f(n) = \frac{5}{2} \cdot 3^n - 1$
$ f(1) = \frac{5}{2} \cdot 3^1 - 1 = \frac{5}{2} \cdot 3 - 1 = 7.5 - 1 = 6.5 $ - $f(n) = \frac{3}{2} \cdot 3^n - \frac{1}{2}$
$ f(1) = \frac{3}{2} \cdot 3^1 - \frac{1}{2} = \frac{3}{2} \cdot 3 - \frac{1}{2} = 4.5 - 0.5 = 4 $ - $f(n) = \frac{5}{2} \cdot 3^n - \frac{1}{2}$
$ f(1) = \frac{5}{2} \cdot 3^1 - \frac{1}{2} = \frac{5}{2} \cdot 3 - \frac{1}{2} = 7.5 - 0.5 = 7 $
So the correct answer is the third option. $f(n) = \frac{5}{2} \cdot 3^n - \frac{1}{2}$
- $f(n) = \frac{5}{2} \cdot 3^n - 1$