Solution: 2018 Fall Final - 10

Author: Michiel Smid

Question

The function $T : \mathbb{N} \rightarrow \mathbb{N}$ is recursively defined as follows: $$ \begin{align} T(0) &= 2, \\ T(n) &= 3 \cdot T(n - 1) + 1,\ \ \mathrm{if}\ n \geq 1. \end{align} $$ Which of the following is true for all integers $n \geq 0$?

(a)

$T(n) = \frac{5}{2} \cdot 3^{n} - \frac{1}{2}$

(b)

$T(n) = \frac{3}{2} \cdot 3^{n} - \frac{1}{2}$

(c)

None of the above.

(d)

$T(n) = \frac{5}{2} \cdot 3^{n} - 1$

Solution

Let’s calculate $ T(1) $

$ T(1) = 3 \cdot f(0) + 1 = 3 \cdot 2 + 1 = 7 $

$ T(n) = \frac{5}{2} \cdot 3^{n} - 1 $
$ T(1) = \frac{5}{2} \cdot 3^{1} - 1 = \frac{5}{2} \cdot 3 - 1 = \frac{15}{2} - 1 = \frac{13}{2} $
$ T(n) = \frac{3}{2} \cdot 3^{n} - \frac{1}{2} $
$ T(1) = \frac{3}{2} \cdot 3^{1} - \frac{1}{2} = \frac{3}{2} \cdot 3 - \frac{1}{2} = \frac{9}{2} - \frac{1}{2} = 4 $
$ T(n) = \frac{5}{2} \cdot 3^{n} - \frac{1}{2} $
$ T(1) = \frac{5}{2} \cdot 3^{1} - \frac{1}{2} = \frac{5}{2} \cdot 3 - \frac{1}{2} = \frac{15}{2} - \frac{1}{2} = 7 $
None of the above

We did it, everyone. The answer is C.