Solution: 2018 Winter 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) &= 0, \\ f(n) &= 2 + f(n - 1)\ \; &\mathrm{if}\ n \geq 1, \\ g(0) &= 1, \\ g(n) &= 7 \cdot g(n - 1)\ \; &\mathrm{if}\ n \geq 1. \end{alignat} $$ For any integer $n \geq 0$, what is $g(f(n))$?

(a)

$n^{7}$

(b)

$7^{2n}$

(c)

$(2n)^{7}$

(d)

$7^{n}$

Solution

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

$ f(0) = 0 $

$ f(1) = 2 + f(0) = 2 $

$ f(2) = 2 + f(1) = 4 $

$ f(n) = 2n $

$ g(0) = 1 $

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

$ g(2) = 7 \cdot g(1) = 49 $

$ g(n) = 7^n $

Thus, $ g(f(n)) = 7^{2n} $.