<s>[INST] Solving system of recurrence relations Base Case:
$$
\left\{ 
\begin{array}{c}
T(1) = 1 \\ T(2) = 1 \\T(3) = 4\end{array}
\right. 
$$
I have the system:
$$
\left\{ 
\begin{array}{c}
T(N) = G(N-1) + F(N-1) \\
G(N) = F(N-1) + G(N-1) \\
F(N) = 2H(N-1) + F(N-2) \\
H(N) = H(N-1) + F(N-1)\end{array}
\right. 
$$
I seems $$T(N) = H(N) = G(N)$$ so we now have only two equations:
$$
\left\{ 
\begin{array}{c}
T(N) = T(N-1) + F(N-1) \\
F(N) = 2T(N-1) + F(N-2)\end{array}
\right. 
$$
I figured
$T(N) = T(N-k) + \sum_{i=1}^k F(N-i) $
and
$F(N) = F(N-2) +2T(N-k) + 2\sum_{i=2}^k F(N-i) $
But after mixing these expressions in a similar way, I came unstuck.
I tried following another example but it didn't help.
I would like to find $T(10^{12})$. Probably by using matrix exponentiation.
 [/INST] Note that
$$
\begin{pmatrix}
T_n \\
F_n \\
F_{n - 1}
\end{pmatrix} = \begin{pmatrix}
1 & 1 & 0 \\
2 & 0 & 1 \\
0 & 1 & 0
\end{pmatrix}
\begin{pmatrix}
T_{n-1}\\
F_{n-1}\\
F_{n-2}
\end{pmatrix}.
$$
So starting with $(T_1, F_1, F_0)$ you can find $(T_n, F_n, F_{n-1})$ quickly by matrix exponentiation.  The latter can be done by the squaring method.
</s>