Solve The Recurrence Homework Question

Question

The functions $f:\mathbb{N} \to \mathbb{N}$ and $g:\mathbb{N} \to > \mathbb{N}$ are recursively defined as follows: $$ \begin{array}{lcll} f(0) &= & 1, & \\ f(n) &= & g(n, f(n-1)) & \mbox{if } n \ge 1, \\ g(m,0) &= & 0 & \mbox{if } m \ge 0, \\ g(m,n) &= & m + g(m, n-1) & \mbox{if } m\ge 0 \mbox{ and } n \ge 1 . \end{array} $$ Solve these recurrences for $f$, i.e. express $f(n)$ in terms of $n$. Justify your answer.

Not sure how to go about solving a recurrence for f using the following recursive functions?

Answer 1

Hint: Start figuring out $g$, then replace the $g$ in the definition of $f$.

Answer 2

Hint: $$g(m,2) = m + g(m,1) = m + (m + g(m,0)) = 2m$$ I.E. $$g(m,0) = 0$$ $$g(m,1) = m$$ $$g(m,2) = 2m$$ $$...$$

Answer 3

$$ g(m,j) = m +g(m, j-1)$$

Then:

$$g(m,j)-g(m,j-1)=m$$

Adding up terms from $j=0$ to $j=n$:

$$\sum_{j=1}^n (g(m,j)-g(m,j-1))=\sum_{j=1}^n m$$

Using the telescopic sums:

$$g(m,n)-g(m,0)=mn$$ $$g(m,n)=mn$$

Answer 4

I won’t solve the problem for you, but I will give you a fairly detailed set of suggestions for approaching it.

Clearly you need to figure out what $g$ is doing in order to solve for $f$. Notice that $g(m,\cdot)$ depends only on $g(m,\cdot)$: values of $g$ for one first coordinate don’t depend on values for a different first coordinate. Thus, you can think of $g$ as a collection of one-place functions: for each $m\in\Bbb N$ let

$$g_m:\Bbb N\to\Bbb N:n\mapsto g(m,n)\;.$$

Then the definition of $g$ can be translated as follows: for each $m\in\Bbb N$ the function $g_m$ is defined recursively be

$$\begin{align*} g_m(0)&=0\\ g_m(n)&=m+g_m(n-1)\text{ if }n\ge 1\;. \end{align*}$$

Now solve for each of the functions $g_m$. This is straightforward; if nothing quicker occurs to you, just calculate $g_m(n)$ for $n=0,1,2,3,4$, say, observe an obvious pattern, and prove by induction that it actually holds.

Then you can plug your knowledge of the functions $g_m$ into $f$:

$$\begin{align*} f(0)&=1\\ f(n)&=g_n\big(f(n-1)\big)\text{ if }n\ge 1\;. \end{align*}$$

Here again you can simply calculate the first few values, observe a simple pattern, and use induction to prove that your conjecture is correct.