How do I combine 2 recursive functions into a single one?

Question

I'm trying to find the growth speed of a certain sequence, but its recursive formula requires additional state - resulting in a system of recursive equations:

$$ \begin{cases} F_1(n)=F_1(n-1)+F_2(n-3)\\ F_2(n)=F_1(n-1)+F_2(n-1)\\ \end{cases} $$

Is there a way to collapse these two into a single equation for $F_1$? Or to find how fast it gets bigger in some other way?

Answer 1

I'll write the values of $F_1$ in the first row and $F_2$ in the second row. If you start computing, you'll notice that you need an initial state of the form

$$ \begin{bmatrix} a & b & c \\ d & \cdot & \cdot \end{bmatrix} $$

You can then extend the table to

$$ \begin{bmatrix}a & b & c & c+d \\ d & {a+d} & \cdot & \cdot \end{bmatrix} $$

Forgetting the first row, we see that increasing $n$ by 1 has amounted to applying the mapping

$$ \begin{bmatrix}a & b & c \\ d & \cdot & \cdot\end{bmatrix} \mapsto \begin{bmatrix}b & c & c+d \\ a+d & \cdot & \cdot\end{bmatrix} $$

This is is the linear mapping

$$ \begin{pmatrix} a \\ b \\ c \\ d \end{pmatrix} \mapsto \begin{pmatrix} b \\ c \\ c+d \\ a+d \end{pmatrix} = \begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ \end{pmatrix} \begin{pmatrix} a \\ b \\ c \\ d \end{pmatrix} $$

I'll write this as

$$ \begin{pmatrix} F_1(n)\\ F_1(n+1) \\ F_1(n+2) \\ F_2(n) \end{pmatrix} = M^n \begin{pmatrix} F_1(0)\\ F_1(1) \\ F_1(2) \\ F_2(0) \end{pmatrix}, $$

where $M$ is the matrix above. By diagonalizing $M$, you can get an explicit formula. I notice that the complex eigenvalue with the largest modulus is the golden ratio $\frac{1 + \sqrt{5}}{2}$. So these should grow about like the Fibonacci sequence.

Edit: you can also explicitly isolate a recurrence for $F_1$, if need be:

\begin{align*} F_1(n) &= F_1(n-1) + F_2(n-3) \\&= F_1(n-1) + F_1(n-4) + F_2(n-4) \\&= F_1(n-1) + F_1(n-4) + \big(F_1(n-1) - F_1(n-2)\big) \\&= 2F_1(n-1) - F_1(n-2) + F_1(n-4). \end{align*}

Answer 2

Store them as a vector, then$$ F(n)=\begin{pmatrix}F(n-1)_1+F(n-3)_2\\F(n-1)_1+F(n-1)_2\end{pmatrix}\\ =\begin{pmatrix}1&0\\1&1\end{pmatrix}*F(n-1)+\begin{pmatrix}0&1\\0&0\end{pmatrix}*F(n-3) $$Just as with the field of complex numbers, you can express $F(n)$ in terms of a linear combination of $n$th powers of the matrices that are roots of the characteristic polynomial, $\begin{pmatrix}1&0\\0&1\end{pmatrix}-\begin{pmatrix}1&0\\1&1\end{pmatrix}*x-\begin{pmatrix}0&1\\0&0\end{pmatrix}*x^3$, times vector coefficients. Due to the analytic form for exponentiating $2\times2$ matrices to noninteger powers, each component ($F_1$ and $F_2$) has an analytic form for its function over $n$.

Answer 3

Any such recurrence you can write as a single matrix operation. You need a few extra states to hold recent values: $$ \begin{cases} F_1(n)=F_1(n-1)+F_2(n-3)\\ F_2(n)=F_1(n-1)+F_2(n-1)\\ \end{cases} $$ Becomes: $$ \left[ \begin{matrix} F_1(n)\\ F_2(n)\\ F_2(n-1)\\ F_2(n-2) \end{matrix} \right]= \left[ \begin{matrix} 1 & 0 & 0 & 1\\ 1 & 1 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 \end{matrix} \right] \left[ \begin{matrix} F_1(n-1)\\ F_2(n-1)\\ F_2(n-2)\\ F_2(n-3) \end{matrix} \right] $$ You can find the eigenvalues of that matrix to see how fast the system grows.