I'm working on a problem that ended up with a recursion in two functions, $$f_n= f_{n-1}+ f_{n-2}+ 2g_{n-2}$$ $g$ also has a recurrence dependent on $f$, $$g_n= f_{n-1}+ g_{n-1}$$
Initial conditions $f_0=0=g_0$ and $f_1=1=g_1$, so it appears there is a fibonacci relationship. I'm trying to construct a generating function for $f$, but I'm confused at this point.
Am I going down the wrong path. Does anyone have any ideas?
On
Ross shows a way to get a recurrence for $f_n$. Alternatively, you can get one for $g_n$:
$$\begin{align*} f_n&=f_{n-1}+f_{n-2}+2g_{n-2}\\ &=f_{n-1}+(f_{n-2}+g_{n-2})+g_{n-2}\\ &=f_{n-1}+g_{n-1}+g_{n-2}\\ &=g_n+g_{n-2}\;, \end{align*}$$
so
$$\begin{align*} g_n&=f_{n-1}+g_{n-1}\\ &=(g_{n-1}+g_{n-3})+g_{n-1}\\ &=2g_{n-1}+g_{n-3}\;. \end{align*}$$
Having solved to get a closed form for $g_n$, you can then get one for $f_n$ either by solving Ross’s recurrence or by getting $f_n$ in terms of the $g_k$:
$$\begin{align*} f_n&=g_{n+1}-g_n\\ &=2g_n+g_{n-2}-g_n\\ &=g_n+g_{n-2}\;. \end{align*}$$
If you right shift the first and subtract it from the first, you get $$f_n-f_{n-1}=f_{n-1}-f_{n-3}+2g_{n-2}-2g_{n-3}$$ Now right shift your second by $2$ to get $g_{n-2}-g_{n-3}=f_{n-3}$ and substitute in, getting $$f_n=2f_{n-1}+f_{n-3}$$