The functions $f : \mathbb{N} \to \mathbb{N}$ and $g : \mathbb{N}^2 \to \mathbb{N}$ are recursively defined as follows:
- $f(0) =1$,
- $f(1) =2$,
- $f(n) = g(f(n − 2),f(n − 1))$ if $n \ge 2$,
- $g(m,0) =2m $ if $m \ge 0$,
- $g(m,n) =g(m,n − 1) + 1$ if $m \ge 0$ and $n \ge 1$.
Solve these recurrences for $f$, i.e., express $f(n)$ in terms of $n$. Justify your answer
Solution: so I got the $g$ pattern and proved it to be right $g(m,n)= 2m+n$ now for $f(n)$ I got $f(n)= 2f(n-1)$. Here I want to get rid of $f(n-1)$, I am stuck here. Can anyone help how to move forward?
Firstly we get closed form of $g$: $$ g(m,n) = g(m, n-1) + 1 = g(m,0) + n = 2m + n,\\ $$ so $f(n) = f(n-1) + 2f(n-2)$. Now one may see that as $f(0) = 1$ and $f(1) = 2 = 2f(0)$ we get $f(2) = 2f(0) + 2f(0) = 2f(1) = 4$, $f(3) = 2f(2) = 8$ etc., i.e. $f(n) = 2^n$ which is easy to prove by induction.
But there is more general approach to solve such kind of recursions. If we denote $f_n = f(n)$, we have the recurrent formula $f_{n+2} - f_{n+1} - 2f_n = 0 $. Each root $\lambda$ of its characteristic equation $x^2 - x - 2 = 0$ solves this recurrent formula by $f_n = \lambda^n$. General solution for recurrence sequence may be represented as linear combination of such "simple" solutions, i.e. if $\lambda_1$ and $\lambda_2$ are roots of characteristic equation, the general solution has the form $f_n = \alpha_1\lambda_1^n + \alpha_2\lambda_2^n$. In our case $\lambda_1 = -1$, $\lambda_2 = 2$, so $f_n = \alpha_1(-1)^n + \alpha_22^n$. To know $\alpha_1$ and $\alpha_2$ we may use initial values of $f_n$: $$ f_0 = \alpha_1 + \alpha_2 = 1, \\ f_1 = -\alpha_1 + 2\alpha_2 = 2, $$ so $\alpha_1 = 0$ and $\alpha_2 = 1$ which gives the same answer $f_n = 2^n$.