---

Problem 918

---

Recursive Sequence Summation

The sequence $a_n$ is defined by $a_1=1$, and then recursively for $n\geq 1$:
$$\begin{aligned}
a_{2n} & =2a_n\\
a_{2n+1} & =a_n-3a_{n+1}
\end{aligned}$$
The first ten terms are $1, 2, -5, 4, 17, -10, -17, 8, -47, 34$.

Define $\displaystyle S(N) = \sum_{n=1}^N a_n$. You are given $S(10) = -13$.

Find $S(10^{12})$.

---

递归序列求和

序列$a_n$的定义为：$a_1=1$；对于$n\geq 1$，递归定义：
$$\begin{aligned}
a_{2n} & =2a_n\\
a_{2n+1} & =a_n-3a_{n+1}
\end{aligned}$$
该序列的前十项是$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})$。

---