自然数を自然数に移す関数$f(n)=\left\{ \begin{array}{cl}
\displaystyle\frac{n}{2} & (n \text{が偶数のとき}) \\
n+1 & (n \text{が奇数のとき})
\end{array} \right.$について，$f$が$m$を$n$に移すことを，$m \longmapsto \hspace{-9mm} {\phantom{\frac{1}{2}}}^f \hspace{3mm} n$と表す．例えば，
\[ 2 \longmapsto \hspace{-10mm} {\phantom{{2^2}^2}}^f \hspace{2.5mm} 1,\qquad 3 \longmapsto \hspace{-10mm} {\phantom{{2^2}^2}}^f \hspace{3mm} 4 \longmapsto \hspace{-10mm} {\phantom{{2^2}^2}}^f \hspace{3mm} 2 \longmapsto \hspace{-10mm} {\phantom{{2^2}^2}}^f \hspace{3mm} 1 \]
である．$2$以上の自然数$n$を$f$で繰り返し移すとき，$1$に移るまでに必要な最小の移動回数を$a_n$とする．したがって，$a_2=1$，$a_3=3$である．$n$を自然数として，以下の問いに答えよ．

(1)$a_{2n+1}$と$a_{2n+2}$をそれぞれ$a_{n+1}$を用いて表せ．
(2)数列$\{a_2,\ a_3,\ a_4,\ \cdots \}$を次のように，第$n$群の項数が$2^{n-1}$になるように分ける．
\[ a_2 \;|\; a_3,\ a_4 \;|\; a_5,\ a_6,\ a_7,\ a_8 \;|\; a_9,\ a_{10},\ a_{11},\ a_{12},\ a_{13},\ a_{14},\ a_{15},\ a_{16} \;|\; \cdots \]

(i) 第$n$群の初項を$n$を用いて表せ．
(ii) 第$n$群の総和を$S_n$とする．$S_{n+1}$を$n$と$S_n$を用いて表せ．また，$S_n$を$n$を用いて表せ．
(iii) $\displaystyle \sum_{k=2}^{2^n} a_k$を$n$を用いて表せ．