Solution: 2017 Fall Midterm - 12

Author: Michiel Smid

Question

The functions $f : \mathbb{N}^2 \rightarrow \mathbb{N}$ and $g : \mathbb{N} \rightarrow \mathbb{N}$ are recursively defined as follows:

$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.$

For any integer $n \geq 0$, what is $f(g(n), g(n))$?

(a)

$2 \cdot 5^{n-1}$

(b)

$(5^{n})^{2}$

(c)

$2 \cdot 5^{n}$

(d)

$(5^{n-1})^{2}$

Let’s take a look at what $ g(n) $ could be.

$ g(0) = 1 $

$ g(1) = 5 \cdot 1 = 5 $

$ g(2) = 5 \cdot 5 = 25 $

$ g(n) = 5^n $

Now, let’s take a look at what $ f(g(n),g(n)) $ could be.

Because $ f(g(n),g(n)) $ decreases n by 1, the call to $ +1 $ will be called $ g(n) $ times.

Once the second argument reaches 0, the function will add $ g(n) $

So in conclusion, the formula is:

$ [1 + 1 + 1 … + 1] + g(n) $

$ =[1 \cdot g(n)] + [g(n)] $

$ =g(n) + g(n) $

$ =2 g(n) $

$ =2 \cdot 5^n $