No.720 行列のできるフィボナッチ数列道場 (2)

$$A=\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$$

$$F=\begin{bmatrix} 1  \\ 0  \end{bmatrix}$$

としたときの、

$$(A^n+A^{2n}+...+A^{mn})F$$
$$=A^n \frac{E-A^{mn}}{E-A^n} F$$

の第二成分が答え。

testestestさんに教えていただいた解法

フィボナッチ数列の第i項目は

$$\frac{1}{\sqrt 5} \left(\left(\frac{1+\sqrt5}{2}\right)^n-\left(\frac{1-\sqrt5}{2}\right)^n\right)$$

で表されるから、求める和は等比数列の和の差であらわせる。上記の計算はa+b√5の形を持ちながら計算すればよい。