The functions f : N → N, g : N 2 → N, and h : N → N are recursively defined as follows:
Solve these recurrences for f, i.e., express f(n) in terms of n.
f(n) = g(n, h(n)) if n ≥ 0,
g(m, 0) = 0 if m ≥ 0,
g(m, n) = g(m, n − 1) + m if m ≥ 0 and n ≥ 1,
h(0) = 1,
h(n) = 2 · h(n − 1) if n ≥ 1.
h(1) = 2.h(0) = 2*1 = 2
h(2) = 2.h(1) = 2*2 = 4 = 2^2
h(3) = 2.h(2) = 2*4 = 8 = 2^3
h(n) = 2^n
g(m,1) = g(m,0) + m = 0 + m = m
g(m,2) = g(m,1) + m = m + m = 2m
g(m,3) = g(m,2) + m = 2m + m = 3m
g(m,n) = nm
Therefore, g(t, h(t)) = g(t, 2^t) = (2^t)*t
So, f(n) = n.2^n