How to solve two recurrences dependent on each other Let
$F_n = a_1*F_{n-1} + b_1*F_{n-2} + c_1*G_{n-3}$
$G_n = a_2*G_{n-1} + b_2*G_{n-2} + c_2*F_{n-3}$
We are given $ a_1,b_1,c_1,a_2,b_2,c_2$ and $ F_0,F_1,F_2,  G_0, G_1,G_2 $. We have to calculate any $F_n$ and $G_n$ with given n. 
Value of n may be as large as 10^9. So we have to calculate it in complexity of O(logn).
 A: If $V_n$ is the column vector $(F_n,G_n)$, then the two equations defining the recurrence can be written as a single "matricial" recurrence:
$$V_n=\begin{bmatrix}a_1 & 0 \\ 0 & a_2 \end{bmatrix}V_{n-1}+\begin{bmatrix}b_1 & 0 \\ 0 & b_2 \end{bmatrix}V_{n-2}+\begin{bmatrix}0 & c_1 \\ c_2 & 0 \end{bmatrix}V_{n-3}\,.$$
Now try to proceed as in the one-dimensional case (for example, look for a solution for the defining recurrence for Fibonacci numbers).
A: Just like the single equation case, imagine that you have a geometric progression with ratio $r$.  Then you have $$F_0r^3=a_1F_0r^2+b_1F_0r+c_1G_0 \\ G_0r^3=a_2G_0r^2+b_2G_0r+c_2F_0\\G_0=\frac {c_2}{r^3-a_2r^2-b_2r}F_0\\r^3=a_ir^2+b_1r+\frac {c_1c_2}{r^3-a_2r^2-b_2r}$$
Unfortunately, this is a sixth degree equation, but you should be able to find the roots (perhaps numerically) and read off the associated $\frac FG$ ratio for each.  Then you have a $6 \times 6$ set of simultaneous equations to feit the given $F$'s and $G$'s
A: Let $F(s)=\sum\limits_{n\geqslant0}F_ns^n$ and $G(s)=\sum\limits_{n\geqslant0}G_ns^n$, then the first recursion (presumably valid for $n\geqslant3$) yields
$$
F(s)=F_0+F_1s+F_2s^2+\sum_{n\geqslant3}(a_1F_{n-1}+b_1F_{n-2}+c_1G_{n-3})s^n,
$$
that is,
$$
F(s)=F_0+F_1s+F_2s^2+a_1s(F(s)-F_0-F_1s)+b_1s^2(F(s)-F_0)+c_1s^3G(s),
$$
or,
$$
(1-a_1s-b_1s^2)F(s)-c_1s^3G(s)=P_1(s),
$$
for some polynomial $P_1(s)$ of degree at most $2$. Likewise,
$$
-c_2s^3F(s)+(1-a_2s-b_2s^2)G(s)=P_2(s),
$$
for some polynomial $P_2(s)$ of degree at most $2$. This is a Cramér linear system in $(F(s),G(s))$ hence $F(s)$ and $G(s)$ are ratios of $2\times2$ determinants. The denominator $D(s)$ is the same for $F(s)$ and $G(s)$ and is
$$
D(s)=(1-a_1s-b_1s^2)(1-a_2s-b_2s^2)-c_1c_2s^6.
$$
The smallest positive root $r$ of $D(s)$ indicates the growth of $F_n$ and $G_n$ in the sense that $r^nF_n$ and $r^nG_n$ converge to finite limits, in general nonzero.
