0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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*}$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Combining our solutions, you can notice that the recursions are the same, so $f_n=g_n$. With matching starting values, you get two for the price of one. $\endgroup$ – Ross Millikan Oct 11 '13 at 13:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.