快速计算 \(\sum\limits_{i=1}^nf_if_{i-1}f_{i+1}-f_i^3\)（其中 f 是斐波那契数列，即 \(f_i=f_{i-1}+f_{i-2}\)，\(f_0=0,f_1=1\)）

借助性质 \(f_i=f_{i-1}+f_{i-2}\) 并经过一系列换元和推导：

\(\begin{cases} \sum\limits_{i=1}^nf_if_{i-1}f_{i+1}-f_i^3=\sum\limits_{i=1}^nf_i^2f_{i-1}+f_if_{i-1}^2-f_i^3\\ a_i=f_i^2f_{i-1}+f_if_{i-1}^2-f_i^3=A_i+B_i-C_i,b_i=b_{i-1}+a_i\\ A_i=f_{i-1}^3+2f_{i-1}^2f_{i-2}+f_{i-1}f_{i-2}^2=C_{i-1}+2A_{i-1}+B_{i-1}\\ B_i=f_{i-1}^3+f_{i-1}^2f_{i-2}=C_{i-1}+A_{i-1}\\ C_i=f_{i-1}^3+3f_{i-1}^2f_{i-2}+3f_{i-1}f_{i-2}^2+f_{i-2}^3=C_{i-1}+3A_{i-1}+3B_{i-1}+D_{i-1}\\ D_i=C_{i-1} \end{cases}\)

得到 \(A,B,C,D,b\) 四个函数相邻项之间的递推关系，将其归纳为线性变换的形式：

定义 \(\mathbf x_i=(A_i,B_i,C_i,D_i,b_i)\)，有：

\(\mathbf x_i=T(\mathbf x_{i-1})=M\mathbf x_{i-1}=\begin{bmatrix}2&1&1&0&0\\1&0&1&0&0\\3&3&1&1&0\\0&0&1&0&0\\0&-2&1&-1&0\end{bmatrix}\begin{bmatrix}A_{i-1}\\B_{i-1}\\C_{i-1}\\D_{i-1}\\b_{i-1}\end{bmatrix},\mathbf x_1=(0,0,1,0,-1)\)

于是 \(\mathbf x_n=M^{n-1}\mathbf x_1\)

“相关”内容(对上述问题没有帮助)

将斐波那契从非负整数域推广到整数域上：\(\mathbb N\to\mathbb Z\)

对于 \(i\in\mathbb N\)，有 \(f_{-i+2}=f_{-i+1}+f_{-i}\)，于是 \(f_{-i}=f_{-i+2}-f_{-i+1}=f_{-(i-2)}-f_{-(i-1)}\)

定义函数 \(g_n=f_{-n}\)，有 \(g_i=g_{i-2}-g_{i-1}\)，\(g_0=0,g_1=1\)（其中 \(n,i\in\mathbb N\)）

g 的前几项为：\(0,1,-1,2,-3,5,-8,13\)（从第 0 项开始）

注意到 \(g_i=(-1)^{i-1}f_i\)

引理：\(f_{2n+1}=1+\sum\limits_{i=0}^nf_{2i},f_{2n}=\sum\limits_{i=0}^{n-1}f_{2i+1}\)

证明：数学归纳法证明 \(g_i=(-1)^{i-1}f_i\)

0）g 的前几项为：\(0,1,-1,2,-3,5,-8,13\)，满足条件

1）偶数项：\(g_{2i+2}=g_{2i}-g_{2i+1}=2g_{2i}-g_{2i-1}=2g_{2i}+g_{2i-2}-g_{2i-3}=\dots\)

\(=g_{2i}+\sum\limits_{j=0}^ig_{2j}-g_1=-f_{2i}-\sum\limits_{j=0}^if_{2j}-1=-(f_{2i}+f_{2i+1})=-f_{2i+2}\)

2）奇数项：\(g_{2i+1}=g_{2i-1}-g_{2i}=2g_{2i-1}-g_{2i-2}=2g_{2i-1}+g_{2i-3}-g_{2i-2}=\dots\)

\(=g_{2i-1}+\sum\limits_{j=0}^{i-1}g_{2j+1}-g_0=f_{2i-1}+\sum\limits_{j=0}^{i-1}f_{2j+1}=f_{2i-1}+f_{2i}=f_{2i+1}\)

\(\blacksquare\)

假设目标函数 \(g_n\) 是关于斐波那契数列的多项式或其合式，如 \(g_n=\sum\limits_{i=0}^Kw_ig_n^\Box g_{n-1}^\Box\) 或 \(g_n=\sum\limits_{j=1}^n\sum\limits_{i=0}^Ka_ig_j^\Box g_{j-1}^\Box\)

（其中满足 \(f_i=f_{i-1}+f_{i-2}\) 或 \(f_i=af_{i-1}+bf_{i-2}\)）

若目标函数中有 \(f_i^af_{i-1}^b\)，且 \(k=a+b\)，那么针对所有的 k 可以构造矩阵 \(M_k=\begin{bmatrix}\binom k0&\dots&\binom k{k-1}&\binom kk\\\binom{k-1}0&\dots&\binom{k-1}{k-1}\\\vdots&\vdots\\\binom{1}{0}&\binom11\\\binom00\end{bmatrix}\) 或 \(M_k=\begin{bmatrix}\binom k0a^k&\dots&\binom k{k-1}ab^{k-1}&\binom kkb^k\\\binom{k-1}0a^{k-1}&\dots&\binom{k-1}{k-1}b^{k-1}\\\vdots&\vdots\\\binom{1}{0}a&\binom11b\\\binom00\end{bmatrix}\)

相应地，设 \(\mathbf x_{k,i}=\begin{bmatrix}A_{0,i}\\\vdots\\A_{k-1,i}\\A_{k,i}\end{bmatrix}=\begin{bmatrix}f_i^k\\\vdots\\f_if_{i-1}^{k-1}\\f_{i-1}^k\end{bmatrix}\)，

（注：为了简洁，\(A_{0,i},A_{1,i},A_{2,i}\dots\) 通常用 \(A_i,B_i,C_i,\dots\) 替代）

那么 \(\mathbf x_{k,i}=M_k\mathbf x_{k,i-1}\)

定义 \(M=\begin{bmatrix}M_t\\&\ddots\\&&M_0\\&W&&0\end{bmatrix}\)，\(\mathbf x_i=\begin{bmatrix}\mathbf x_{t,i}\\\vdots\\\mathbf x_{0,i}\\g_i\end{bmatrix}\)（注意：W 是一系列行向量 \(A_i,B_i,C_i,\dots\) 的线性组合拼接组成）

最后得到线性变换形式：\(\mathbf x_i=M\mathbf x_{i-1}\)

于是 \(\mathbf x_n=M^n\mathbf x_0\)（\(\mathbf x_0\) 可以通过 \(f_{-1},f_0\) 得到）

例如：\(g_n=af_n^2+bf_n+c\) 可以构造 \(M_0,M_1,M_2\) 和 \(\mathbf x_{0,i},\mathbf x_{1,i},\mathbf x_{2,i}\)

定义 \(M=\begin{bmatrix}M_2\\&M_1&&\mathbf0\\&&M_0\\&W&&0\end{bmatrix}\)，\(\mathbf x_i=\begin{bmatrix}\mathbf x_{2,i}\\\mathbf x_{1,i}\\\mathbf x_{0,i}\\g_i\end{bmatrix}\)

其中 \(W=(a,0,0,b,0,c)\)（\(W\in\mathbb R^{1\times6}\)），\(\mathbf x_1=(f_1^2,f_1f_0,f_0^2,f_1,f_0,1,g_1)=(1,0,0,1,0,1,a+b+c)\)

有 \(\mathbf x_i=M\mathbf x_{i-1}\)，于是 \(g_n\) 就能快速递推了

1. \(\forall i\ge0\)，\(f_n=f_{i+1}f_{n-i}+f_if_{n-(i+1)}\)；如：\(f_n=f_2f_{n-1}+f_1f_{n-2}\)，\(f_n=f_3f_{n-2}+f_2f_{n-3}\)

1) \(g_n=\prod\limits_{i=0}^k(f_{i+1}f_n+f_{i}f_{n-1})\)

2）\(g_n=g_{n-1}+f_n\cdot n^k=g_{n-1}+(f_{n-1}+f_{n-2})\sum\limits_{i=0}^k\binom ki(n-1)^i\)

定义 \(A_{i,n}=f_nn^i,B_{i,n}=f_n(n-1)^i\)