答えを \(S_{nm}\) とすると,

\[\begin{align} S_{i+1} &= \begin{cases} S_i + F_{i+1} & (i+1 \equiv 0 \pmod m) \\ S_i & (i+1 \not\equiv 0 \pmod m) \end{cases} \\ F_{i+2} &= F_{i+1}+F_i \end{align}\]

となる. これを行列形式であらわすと,

\(i+1 \equiv 0 \pmod m\) のとき:

\[\begin{pmatrix} S_{i+1} \\ F_{i+2} \\ F_{i+1} \end{pmatrix} = \begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 0 \end{pmatrix} \begin{pmatrix} S_i \\ F_{i+1} \\ F_i \end{pmatrix}\]

\(i+1 \not\equiv 0 \pmod m\) のとき:

\[\begin{pmatrix} S_{i+1} \\ F_{i+2} \\ F_{i+1} \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 0 \end{pmatrix} \begin{pmatrix} S_i \\ F_{i+1} \\ F_i \end{pmatrix}\]

となる. よって, 前者の行列を \(A\), 後者の行列を \(B\) とすると,

\[S_{nm} = (AB^{m-1})^n \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}\]

となる.