918 : 漸化式で定義される数列の和

数列 $a_n$ を $a_1 = 1$, $n \geq 1$ について再帰的に次のように定める：

$$\begin{align*} a_{2n} &= 2a_n \\ a_{2n+1} &= a_n - 3a_{n+1} \end{align*}$$

最初の10項は $1,2,-5,4,17,-10,-17,8,-47,34$ である。

$\displaystyle S(N) = \sum_{n=1}^n a_n$ と定義する。$S(10) = -13$ が与えられている。

$S(10^{12})$ を求めよ。