OMC075(C) - 長さの漸化式

　一般に $8$ を $2n\ (n \ge 1)$ とおき，仮定の場合の数を $a_n$ としてこれを求める． 　$$a_1 = {}_3\mathrm P_2 = 6$$ であり，以下では $n \ge 2$ とする．
　まず，$A_1,\ldots, A_{2n-1}$ として考えられる整数の組は $\left(3 \times 2^{2n-2}\right)$ 通りあり，これらを固定すると，$A_{2n}$ は $A_1 = A_{2n-1}$ のときは $2$ 通り，$A_1 \ne A_{2n-1}$ のときは $1$ 通り．$A_1 = A_{2n-1}$ となる $A_1,\ldots, A_{2n-1}$ の総数は，$n-1$ のときに等しいから $$a_n = 3 \times 2^{2n-2} + a_{n-1} \implies a_n = 3 + \sum_{k=0}^{n-1}\left(3 \times 2^{2k}\right) = 2^{2n} + 2 \quad (n \ge 1)$$ を得る．よって答えは $2^8 + 2 = \mathbf{258}$．（potato167 さんの解説にある一般化も可能）