斐波那契数列: \(F_i = F_{i-1} + F_{i-2}\)
\[\begin{bmatrix} F_i \\ F_{i-1} \end{bmatrix}= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \times \begin{bmatrix} F_{i-1} \\ F_{i-2} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{i-1} \times \begin{bmatrix} F_1 \\ F_0 \end{bmatrix}
\]
递推式 - 1: \(G_i = a \times G_{i-1} + b \times G_{i-2}\)
\[\begin{bmatrix} G_i \\ G_{i-1} \end{bmatrix} = \begin{bmatrix} a & b \\ 1 & 0 \end{bmatrix} \times \begin{bmatrix} G_{i-1} \\ G_{i-2} \end{bmatrix} = \begin{bmatrix} a & b \\ 1 & 0 \end{bmatrix}^{i-1} \times \begin{bmatrix} G_1 \\ G_0 \end{bmatrix}
\]
递推式 - 2: \(G_i = a \times G_{i-1} + i^2\)
\[\begin{bmatrix} G_i \\ (i+1)^2 \\ i+1 \\ 1 \end{bmatrix} = \begin{bmatrix} a & 1 & 0 & 0 \\ 0 & 1 & 2 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{bmatrix} \times \begin{bmatrix} G_{i-1} \\ i^2 \\ i \\ 1 \end{bmatrix} = \begin{bmatrix} a & 1 & 0 & 0 \\ 0 & 1 & 2 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{bmatrix}^i \times \begin{bmatrix} G_0 \\ 1 \\ 1 \\ 1 \end{bmatrix}
\]
递推式 - 3: \(G_i = a \times G_{i-1} + i^3\)
\[\begin{bmatrix} G_i \\ (i+1)^3 \\ (i+1)^2 \\ i+1 \\ 1 \end{bmatrix} = \begin{bmatrix} a & 1 & 0 & 0 & 0 \\ 0 & 1 & 3 & 3 & 1 \\ 0 & 0 & 1 & 2 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix} \times \begin{bmatrix} G_{i-1} \\ i^3 \\ i^2 \\ i \\ 1 \end{bmatrix} = \begin{bmatrix} a & 1 & 0 & 0 & 0 \\ 0 & 1 & 3 & 3 & 1 \\ 0 & 0 & 1 & 2 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix}^i \times \begin{bmatrix} G_0 \\ 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}
\]
递推式 - 4: \(G_i = a \times G_{i-1} + b^i\)
\[\begin{bmatrix} G_i \\ b^{i+1} \end{bmatrix} = \begin{bmatrix} a & 1 \\ 0 & b \end{bmatrix} \times \begin{bmatrix} G_{i-1} \\ b^i \end{bmatrix} = \begin{bmatrix} a & 1 \\ 0 & b \end{bmatrix}^i \times \begin{bmatrix} G_0 \\ b \end{bmatrix}
\]
递推式 - 带常数：\(f(n) = a \times f(n-1) + b \times f(n-3) + c\)
\[\begin{bmatrix}
f[n] \\
f[n-1] \\
f[n-2] \\
c
\end{bmatrix}
=
\begin{bmatrix}
a & 0 & b & 1 \\
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1
\end{bmatrix}
\times
\begin{bmatrix}
f[n-1] \\
f[n-2] \\
f[n-3] \\
c
\end{bmatrix}
=
\begin{bmatrix}
a & 0 & b & 1 \\
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1
\end{bmatrix}^{n-2}
\times
\begin{bmatrix}
f[2] \\
f[1] \\
f[0] \\
c
\end{bmatrix}
\]
递推式 - 带变量：\(f(1)=1\)，\(f(2)=2\)，\(f(n) = f(n-1) + 2f(n-2) + n^3\)
利用二项式定理：
\[n^3 = (n-1+1)^3 = (n-1)^3 + 3(n-1)^2 + 3(n-1) + 1
\]
\[\begin{bmatrix}
f(n) \\
f(n-1) \\
n^3 \\
n^2 \\
n \\
1
\end{bmatrix}
=
\begin{bmatrix}
1 & 2 & 1 & 3 & 3 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 3 & 3 & 1 \\
0 & 0 & 0 & 1 & 2 & 1 \\
0 & 0 & 0 & 0 & 1 & 1 \\
0 & 0 & 0 & 0 & 0 & 1
\end{bmatrix}
\times
\begin{bmatrix}
f(n-1) \\
f(n-2) \\
(n-1)^3 \\
(n-1)^2 \\
n-1 \\
1
\end{bmatrix}
=
\begin{bmatrix}
1 & 2 & 1 & 3 & 3 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 3 & 3 & 1 \\
0 & 0 & 0 & 1 & 2 & 1 \\
0 & 0 & 0 & 0 & 1 & 1 \\
0 & 0 & 0 & 0 & 0 & 1
\end{bmatrix}^{n-2}
\times
\begin{bmatrix}
f(2) \\
f(1) \\
8 \\
4 \\
2 \\
1
\end{bmatrix}
\]
递推式 - 前缀和:
递推式定义：
- \( T[0]=T[1]=T[2]=1 \)
- \( T[n]=T[n-1]+T[n-2]+T[n-3] \ (n \geq 3) \)
- \( S[n] = T[0] + T[1] + \dots + T[n] = S[n-1] + T[n-1]+T[n-2]+T[n-3] \)
\[\begin{bmatrix}
S[n] \\
T[n] \\
T[n-1] \\
T[n-2]
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 & 1 & 1 \\
0 & 1 & 1 & 1 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0
\end{bmatrix}
\cdot
\begin{bmatrix}
S[n-1] \\
T[n-1] \\
T[n-2] \\
T[n-3]
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 & 1 & 1 \\
0 & 1 & 1 & 1 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0
\end{bmatrix}^{n-2}
\cdot
\begin{bmatrix}
S[2] \\
T[2] \\
T[1] \\
T[0]
\end{bmatrix}
\]