피보나치 수열이란 첫번째 항과 두번째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 편의상 0번째 항을 0으로 나타내기도 한다. 피보나치 수열을 수식으로 나타내면 아래와 같다.
$$F_{0}=0,\;F_{1}=1,\;\;F_{n}=F_{n-1}+F_{n-2}\;(n\geq 2)$$
이때 점화식 $F_{n}=F_{n-1}+F_{n-2}\;(n\geq 2)$ 을 아래와 같이 행렬로 나타낼 수 있다.
$$\begin{bmatrix}
0 & 1 \\
1 & 1 \\
\end{bmatrix}
\begin{bmatrix}
F_{n-2} \\
F_{n-1} \\
\end{bmatrix}
=
\begin{bmatrix}
F_{n-1} \\
F_{n} \\
\end{bmatrix}$$
또는 2x2 행렬을 이용해서 아래와 같이도 나타낼 수 있다.
$$\begin{bmatrix}
F_{n-2} & F_{n-1} \\
F_{n-1} & F_{n} \\
\end{bmatrix}
\begin{bmatrix}
0 & 1 \\
1 & 1 \\
\end{bmatrix}
=
\begin{bmatrix}
F_{n-1} & F_{n} \\
F_{n} & F_{n+1} \\
\end{bmatrix}$$
점화식의 일반항을 구하면 아래와 같다.
$$\begin{bmatrix}
F_{n-1} & F_{n} \\
F_{n} & F_{n+1} \\
\end{bmatrix}
=
\begin{bmatrix}
0 & 1 \\
1 & 1 \\
\end{bmatrix}^{n}$$
따라서 분할 정복을 이용해 행렬의 거듭제곱을 구하는 방법으로 큰 크기의 피보나치 수를 구할 수 있다.