数列の問題

$a(1)=2$ とし，$a(2),a(3),a(4),\cdots$ を次の関係で定める。

$$a(2n)=3a(n)+1,\quad a(2n+1)=3a(n)+2\quad(n=1,2,\cdots)$$

以下の問に答えよ。

(1)　$a(7),a(9)$ を求めよ。

(2)　自然数 $n$ に対して，$a(2^n+1)$ は，1または2のいずれかの値をとるような $b_0,b_1,\cdots,b_n$ を用いて，

$$a(2^n+1)=\sum_{k=0}^{n}b_k\cdot3^k$$

と表せる。$b_0,b_1,\cdots,b_n$ をそれぞれ求めよ。

(3)　自然数 $n$ に対して，$\displaystyle\sum_{k=1}^{2^n-1}a(k)$ を求めよ。