矩阵乘法与斐波那契

P. S.

以下文章小写字母及希腊字母表实数，大写字母表矩阵，

f_i

表斐波那契数列的第

i

项。

Part.1 矩阵基础运算

加减法

若

C=A\pm B

，则：

C_{i,j}=A_{i,j}\pm B_{i,j}

代码实现：

CPP

struct mat{
	long long a[105][105];
}; 
mat pm(mat x,mat y,int n){
	mat c;
	for(int i=1;i<=n;i++)
	    for(int j=1;j<=n;j++)
	        c.a[i][j]=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            c.a[i][j]=x.a[i][j]=x.a[i][j]+y.a[i][j];
    return c;
}

Part.2 斐波那契通项公式

众所周知：

f_n=\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n)

根据 二项式定理 展开可得（即第三斐波那契性质）：

f_n=\frac{\sum_{i=1}^{n} \mathrm{C}_n^i\cdot 5^{\frac{n-1}{2}}\cdot(i\%2)}{2^{n-1}}

接下来，我们将用两种方法证明通项公式。

法一：函数法（选读）

设斐波那契生成函数为

G(x)

，即：

G(x)=\sum_{i\ge1}f_ix^i

G(x)-xG(x)=x+x^2G(x)

G(x)=\frac{x}{1-x-x^2}

因式分解：

G(x)=\frac{x}{(1-\frac{1-\sqrt{5}}{2}x)(1-\frac{1+\sqrt{5}}{2}x)}

同理，裂项后：

f_n=\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n)

法二：特征根法

首先我们明确所有线性递推数列都是 等比数列。
有：

f_n=f_{n-1}+f_{n-2}

，公比

a

满足

f_n=a^n

。
那么还有：

a^n=a^{n-1}+a^{n-2}

a^2-a-1=0

f_n=a^n_1x+a^n_2

同样得通项公式。

矩阵乘法与斐波那契

文章操作

P. S.

Part.1 矩阵基础运算

加减法

Part.2 斐波那契通项公式

法一：函数法（选读）

法二：特征根法

相关推荐

评论

矩阵乘法与斐波那契