Question: 2017 Fall Midterm - 12
The functions $f : \mathbb{N}^2 \rightarrow \mathbb{N}$ and $g : \mathbb{N} \rightarrow \mathbb{N}$
are recursively defined as follows:
For any integer $n \geq 0$, what is $f(g(n), g(n))$?
| $f(m, 0)$ | $= m\ \;$ | $\mathrm{if}\ m \geq 0,$ |
| $f(m, n)$ | $= 1 + f(m, n - 1)\ \;$ | $\mathrm{if}\ m \geq 0$ $\mathrm{and}\ n \geq 1,$ |
| $g(0)$ | $= 1,$ | |
| $g(n)$ | $= 5 \cdot g(n - 1)\ \;$ | $\mathrm{if}\ n \geq 1.$ |
(a)
$(5^{n-1})^{2}$
(b)
$(5^{n})^{2}$
(c)
$2 \cdot 5^{n}$
(d)
$2 \cdot 5^{n-1}$