Solution: 2022 Winter Final - 10

Author: Michiel Smid

Question

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

(a)

$T(n)=3(2^{n+1}-1)$

(b)

$T(n)= 3n$

(c)

$T(n)=2(3^{n+1}-1)$

(d)

$T(n)= 3^{n+1}$

(e)

$T(n)= 2^{n+1}+1$

Solution

Let’s just plug in some values and see what happens

$ T(0) = 3 $

$ T(1) = 2 \cdot 3 + 3 = 9 $

$ T(2) = 2 \cdot 9 + 3 = 21 $

$ T(3) = 2 \cdot 21 + 3 = 45 $

Now, we see which one matches

$T(n) = 3n$
$T(1) = 3 \neq 3 \cdot 1 = 3$
$T(n) = 2^{n+1} + 1$
$T(1) = 9 \neq 2^{1+1} + 1 = 5$
$T(n) = 3(2^{n+1} - 1)$
$T(1) = 3(2^2 - 1) = 3(4 - 1) = 9$
$T(2) = 3(2^3 - 1) = 3(8 - 1) = 21$
$T(n) = 2(3^{n+1} - 1)$
$T(1) = 2(9-1) = 16$
$T(n) = 3^{n+1}$
$T(1) = 9$
$T(2) = 27$

Since only c matches, the answer is c