No.344

$$(1+\sqrt{3})^n = a_n + b_n\sqrt{3}$$

とおくと, 二項定理より,

$$\begin{align} a_n &= \sum_{i=0}^{n/2} {}_nC_{2i} \cdot 3^i \\ b_n &= \sum_{i=0}^{n/2} {}_nC_{2i+1} \cdot 3^i \end{align}$$

となる. ここで, $(1-\sqrt{3})^n$ を考えると, 上記の $a_n, b_n$ を用いて

$$(1-\sqrt{3})^n = a_n - b_n\sqrt{3}$$

となる. よって,

$$(1+\sqrt{3})^n + (1-\sqrt{3})^n = 2a_n$$

となり,

$$(1+\sqrt{3})^n = 2a_n - (1-\sqrt{3})^n$$

となる. $\vert 1-\sqrt{3} \vert \lt 1$ であるので, $\vert (1-\sqrt{3})^n \vert \lt 1$ となるので,

$$\begin{eqnarray} \lfloor(1+\sqrt{3})^n\rfloor = \begin{cases} 2a_n & (n {\rm \ is \ odd}) \\ 2a_n-1 & (n {\rm \ is \ even}) \end{cases} \end{eqnarray}$$

となる.

$a_n$ の求め方であるが,

$$\begin{align} (1+\sqrt{3})^{n+1} &= (a_n+b_n\sqrt{3})(1+\sqrt{3}) \\ &= (a_n+3b_n)+(a_n+b_n)\sqrt{3} \end{align}$$

となるので,

$$\begin{pmatrix} a_{n+1} \\ b_{n+1} \end{pmatrix} = \begin{pmatrix} 1 & 3 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} a_n \\ b_n \end{pmatrix}$$

とあらわせる. これを行列の繰り返し2乗法で解けば $a_n$ を求めることができる.