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.