Solution: 2018 Fall Midterm - 12

Author: Michiel Smid

Question

The functions $f: \mathbb{N} \rightarrow \mathbb{N}$ and $g: \mathbb{N} \rightarrow \mathbb{N}$ are recursively defined as follows: $$ \begin{alignat}{2} f(0) &= 3, \\ f(n) &= 5 + f(n - 1)\ \; &\mathrm{if}\ n \geq 1, \\ g(0) &= 1, \\ g(n) &= 2 \cdot g(n - 1) &\mathrm{if}\ n \geq 1. \end{alignat} $$ For any integer $n \geq 0$, what is $f(g(n))$?

(a)

$2^{3 + 5n}$

(b)

$5 + 3 \cdot 2^{n}$

(c)

$2^{5 + 3n}$

(d)

$3 + 5 \cdot 2^{n}$

Solution

Let’s find the first few values of $ g(n) $ to find a pattern:

$ g(0) = 1 $

$ g(1) = 2 \cdot g(0) = 2 $

$ g(2) = 2 \cdot g(1) = 4 $

$ g(n) = 2^n $

Now let’s find the formula for $ f(n) $:

$ f(0) = 3 $

$ f(1) = 5 + f(0) = 8 $

$ f(2) = 5 + f(1) = 13 $

$ f(n) = 5n + 3 $

Thus, $ f(g(n)) = 5 \cdot 2^n + 3 $.