详解由递推公式求斐波那契数列的通项公式

用递推算法求解斐波那契数列,请列出该问题中的边界条件和递推公式
斐波那契数列是一种典型的递推数列，又被称作黄金分割数列，由欧几里德提出。

斐波那契数列的边界条件是F(0)=0，F(1)=1，递推公式是F(n)=F(n-1)+F(n-2)，其中n≥2。

斐波那契数列在计算机科学课程和数学竞赛中都是经典的题目，它也有着多年的发展历史。

斐波那契数列可以通过采用多种不同的递推方式来进行求解，比如使用递归，迭代，动态规划等。

斐波那契数列的最重要的思想就是利用现有结果来计算比它更大序号上的斐波那契数列值。

首先，因为斐波那契数列的边界条件是F(0)=0，F(1)=1，所以从没有前置条件的情况下我们可以先把F(0)和F(1)的值赋值给一个变量来提前存储起来，从而简化程序中给定边界条件所需要的存储空间。

其次，斐波那契数列其实也是一种满足递推关系式的等比数列，其递推公式
F(n)=F(n-1)+F(n-2)。

所以在我们采用迭代的方式给定斐波那契数列的值的时候，从给定的边界条件的下标位置开始向后进行依次循环，将在 F(n-1) 和 F(n-2) 即前一位和前两位的斐波那契数值于当前的斐波那契数值相加即可。

最后，根据斐波那契数列的递推公式，我们可以想象出在每次递推时迭代所需要遍历的序号位置是按升序排列的，因为当我们要求得斐波那契数列中第n位的值时，这个数列中第前面n-1位和n-2位的斐波那契数值都已经确定。

由此可见，斐波那契数列是一种有一定适用性的数列，可以采用不同的方式求解，根据自身的特性可以高效地求得任意序号位置上的斐波那契数值。

数列的递推公式及通项公式数列是由一系列按照一定规律排列的数字组成的序列。

数列中的每个数字称为项，而这些项之间的关系可以通过递推公式和通项公式来描述。

本文将介绍数列的递推公式和通项公式，并通过具体的例子来解释其应用。

一、递推公式递推公式是指通过前一项或多项来确定后一项的公式。

递推公式可以分为线性递推和非线性递推两种类型。

1.1 线性递推线性递推是指数列的每一项都可以通过前一项乘以某个常数再加上某个常数得到。

其一般形式如下：an = a(n-1) * r + d其中，an代表数列中的第n项，a(n-1)代表数列中的第n-1项，r为公比，d为公差。

例如，给定数列1，3，5，7，9，...，其中第一项a1为1，公差d 为2。

根据数列的特点可以确定递推公式为：an = a(n-1) + 2通过递推公式，可以依次计算出数列的每一项。

1.2 非线性递推非线性递推是指数列的每一项不能用前一项的线性组合表示，而是通过其他的方式来确定。

例如，斐波那契数列就是一个常见的非线性递推数列。

斐波那契数列的递推公式为：an = a(n-1) + a(n-2)其中，a1 = 1，a2 = 1。

根据递推公式，可以计算出斐波那契数列的每一项。

二、通项公式通项公式是指通过数列的位置n来直接计算数列中的第n项的公式。

通项公式可以分为线性通项和非线性通项两种类型。

2.1 线性通项线性通项是指数列的每一项可以通过位置n的线性关系来计算。

其一般形式如下：an = a1 + (n-1) * d其中，an代表数列中的第n项，a1为数列首项，d为公差。

以等差数列为例，假设已知数列首项a1为2，公差d为3，可以通过线性通项公式an = 2 + (n-1) * 3计算出数列的任意一项。

2.2 非线性通项非线性通项是指数列的每一项不能用位置n的线性关系来计算，而是通过其他的方式来确定。

例如，等比数列就是一个常见的非线性通项数列。

等比数列的通项公式为：an = a1 * r^(n-1)其中，an代表数列中的第n项，a1为数列首项，r为公比。

斐波那契数列是一个非常著名的数列，它由如下的递归关系定义：F(0) = 0,F(1) = 1,F(n) = F(n-1) + F(n-2) 对于n >= 2。

对于这个数列的通项公式（即直接计算第n项的公式而不需要计算之前所有项的值），存在一个非常著名的公式，称为Binet公式：F(n) = (φ^n - ψ^n) / √5，其中，φ= (1 + √5) / 2 约等于1.618033988749895...（黄金分割比），ψ = (1 - √5) / 2 约等于-0.618033988749895...。

这两个数实际上是方程x^2 - x - 1 = 0 的两个解。

不动点法是求解具有递归关系的数列通项的一种方法，它基于的思想是寻找一个函数的不动点（这里的不动点指的是满足f(x) = x的点），这在函数迭代和分形理论中非常常见。

但是，必须说明的是，斐波那契数列的通项公式并不是通过不动点法得出的。

不动点法在斐波那契数列的直接计算中并不是标准做法。

在数学中，不动点通常是指在迭代过程中不会改变的点。

例如，对于某个函数f(x)，如果存在x*使得f(x*) = x*，则称x*为f的不动点。

但是对于斐波那契数列，我们通常不使用不动点法来求取其通项公式，因为现有的递推关系和Binet公式已经非常简洁且易于计算。

为了计算斐波那契数列的项，我们通常依赖于递归计算、Binet公式或者使用动态规划这类编程技术来避免重复计算已求出的项。

这些方法在实践中更加常见和有效。

要理解不动点的概念，一个简单的例子就是函数f(x) = x^2。

假设我们想要找到满足f(x) = x 的x值，我们可以简单求解方程x^2 = x，得到两个解x=0和x=1。

其中0和1就是这个函数的不动点。

不过这个例子和斐波那契数列的求解并没有直接关联。

总的来说，斐波那契数列的通项是通过数学推导得出的Binet公式，而不是通过不动点法，后者在其他类型的问题中更为常见，特别是在分析动态系统和迭代函数时。

斐波那契数列通项公式的推导过程斐波那契数列是数学中一个经典的数列，它的每一项都是前两项的和。

斐波那契数列的通项公式的推导过程是一个非常有趣的数学问题，下面我们就来详细讲解一下。

让我们回顾一下斐波那契数列的定义：数列的第一项和第二项分别为0和1，从第三项开始，每一项都是前两项的和。

用数学符号表示，斐波那契数列可以写成如下形式：F(1) = 0，F(2) = 1，F(n) = F(n-1) + F(n-2)（n ≥ 3）。

要推导斐波那契数列的通项公式，我们可以使用数学归纳法。

首先，我们假设斐波那契数列的通项公式为Fn = a^n + b^n（n ≥ 1），其中a和b是待定的常数。

接下来，我们需要证明这个假设对所有的n都成立。

首先，我们可以验证当n=1和n=2时，假设成立。

当n=1时，根据我们的假设，有F(1) = a^1 + b^1 = a + b = 0，因此a + b = 0。

当n=2时，根据我们的假设，有F(2) = a^2 + b^2 = a^2 + (-a)^2 = 1，因此a^2 + b^2 = 1。

接下来，我们假设对于任意的k（k ≥ 2），假设成立，即F(k) = a^k + b^k。

我们需要证明对于k+1也成立，即F(k+1) = a^(k+1) + b^(k+1)。

根据斐波那契数列的定义，有F(k+1) = F(k) + F(k-1)。

根据我们的假设，有F(k) = a^k + b^k，F(k-1) = a^(k-1) + b^(k-1)。

将这两个式子代入F(k+1) = F(k) + F(k-1)中，得到：F(k+1) = (a^k + b^k) + (a^(k-1) + b^(k-1))通过整理化简，得到：F(k+1) = a^k * (a + b) + b^k * (a + b)根据我们之前得到的结论a + b = 0，将其代入上式中，得到：F(k+1) = a^k * 0 + b^k * 0 = 0因此，假设对于任意的k成立，那么对于k+1也成立。

介绍斐波那契数列及其运用斐波那契数列（Fibonacci Sequence）又称黄金分割数列，是一组特殊的数字序列，全部数字相加，当前项为其前两项之和。

它以著名意大利数学家莱昂纳多·斐波那契（Leonardio Fibonacci）的名字命名，因他在《尼罗河数字》（1202）中提出了它的组成规律。

一、斐波那契数列的定义斐波那契数列定义为：一列数字，从第三项开始，每一项都等于前两项之和。

通常用斐波那契数列的记法表示，用两个不同的数字作为起点，从而可以确定整个数列。

第一、第二项均为1，因此数列的起点为（1，1），前三项分别是：1，1，2。

二、斐波那契数列基本性质1. 通项公式斐波那契数列的通项公式为：an=an-1+an-2，即使用递推公式，可以求出斐波那契数列的任意一项。

其中an代表第n项，an-1代表第n-1项，an-2代表第n-2项。

2. 黄金比例斐波那契数列中数字的总和可以表示为黄金比例，即：a1/a2=a2/a3=a3/a4….=0.618，它表示任意斐波那契数列中，数字相加的比值都处于0.618左右。

三、斐波那契数列的应用1. 密码中的应用加密技术是用来保护信息在传输过程中不被窃取的一种技术，其中一种最常用的加密技术称为基于斐波那契数列的加密技术，该技术是一种有规律性的序列及规则的加密技术，使用起来既安全又直观，经常用来进行信息传输加密，以及用于制作密码、密钥保护等。

2. 算法中的应用斐波那契数列也常在算法中使用，如在算法中求解动态最优解，优先查找网络最短路等，比较容易使用其中的比例来解决各种规划问题，am是an-1+bn-2模式的了解，这种模式在很多分支处理方面都有着较好的应用，特别是网络路由最短路，及生物群降纬等，都是用户非常喜欢的算法。

3. 图形中的应用很多形象，如螺旋、花环、蜂窝等，在很多设计中都有着广泛的应用，但这些形象的基础其实都是斐波那契数列，在空间几何中，大多数螺旋线形状，都可以用fibonacci数列进行模拟，这样就可以简化模型，使其形状更加精确，便于使用，比如说螺旋道路、凸透镜和周期传播都是这类应用。

斐波那契数列斐波那契数列，又称黄金分割数列、因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从1963年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。

定义斐波那契数列指的是这样一个数列1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368........自然中的斐波那契数列这个数列从第3项开始，每一项都等于前两项之和。

斐波那契数列的定义者，是意大利数学家列昂纳多·斐波那契，生于公元1170年，卒于1250年，籍贯是比萨。

他被人称作“比萨的列昂纳多”。

1202年，他撰写了《算盘全书》（Liber Abacci）一书。

他是第一个研究了印度和阿拉伯数学理论的欧洲人。

他的父亲被比萨的一家商业团体聘任为外交领事，派驻地点于阿尔及利亚地区，列昂纳多因此得以在一个阿拉伯老师的指导下研究数学。

他还曾在埃及、叙利亚、希腊、西西里和普罗旺斯等地研究数学。

通项公式递推公式斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...如果设F(n）为该数列的第n项（n∈N*），那么这句话可以写成如下形式：:F(n)=F(n-1)+F(n-2)显然这是一个线性递推数列。

通项公式(如上，又称为“比内公式”，是用无理数表示有理数的一个范例。

) 注：此时通项公式推导方法一：利用特征方程（线性代数解法）线性递推数列的特征方程为：x²=x+1解得，.则∵∴解得方法二：待定系数法构造等比数列1（初等代数解法）设常数r，s .使得则r+s=1，－rs=1n≥3时，有……联立以上n-2个式子，得：∵，上式可化简得：那么……（这是一个以为首项、以为末项、为公比的等比数列的各项的和）。

斐波那契数列通项公式的推导：
由11a =，21a =，12n n n a a a --=+，*n ∈N ，3n ≥
令()()1123n n n n a ra s a ra n ----=-≥，则11r s rs +=⎧⎨=-⎩
从而()2121n n n a ra s a ra ---=-
所以11n n n a s r a --=+
所以112212n n n n n n a s r a s rs r a -----=+=++=122321n n n n n s rs r s r s r -----=+++++ 这是公比为r s 的等比数列前n 项和，所以n n n s r a s r
-=-， 由11r s rs +=⎧⎨=-⎩
，解得一组解s r ⎧⎪⎪⎨⎪=⎪⎩
代入得n n n a ⎡⎤⎥=-⎥⎝⎭⎝⎭⎦
． 数列递推公式：若数列{}n a 中的任意项n a 与相邻的若干项之间的关系可以用一个公式
表示，则这个公式叫做数列的递推公式．数列的递推公式揭示了数列的任一项n a 与1n a -（或前几项）的关系，也是给出数列的一种重要方法．
迭代是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或者方程组）的过程，为实现这一过程所使用的方法统称为迭代法．所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）．迭代关系式的建立是解决迭代问题的关键，通常可以顺推或倒推的方法来完成．
递推与迭代在生活实际中有广泛的应用，计算机算法就建立在递推与迭代的基础上．。

斐波那契数列通项公式的推导斐波那契数列，这玩意儿听起来是不是有点高大上？但其实它就在我们身边，藏在很多有趣的地方呢！咱们先来说说啥是斐波那契数列。

它是这样一组数：0、1、1、2、3、5、8、13、21、34…… 从第三个数开始，每个数都是前两个数的和。

就像接力赛一样，一个接一个，永不停歇。

那为啥要研究它的通项公式呢？这就好比你知道了一个宝藏的密码，有了通项公式，就能轻松算出数列中任意一项的值，是不是很神奇？我记得有一次，我在公园里散步，看到一群小朋友在玩跳格子的游戏。

他们从一个格子跳到另一个格子，跳的步数正好就构成了斐波那契数列。

我当时就想，这小小的游戏里居然藏着这么有趣的数学规律。

接下来，咱们就开始推导这个神奇的通项公式。

咱们设斐波那契数列的第 n 项为 F(n) ，那它就满足这个递推关系式：F(n) = F(n - 1) + F(n - 2) ，并且 F(0) = 0 ，F(1) = 1 。

这看起来有点复杂，别着急，咱们一步步来。

咱们先假设斐波那契数列的通项公式是 F(n) = a^n （这里的 a 是一个待求的数）。

把它代入递推关系式里，就得到：a^n = a^(n - 1) + a^(n - 2)两边同时除以 a^(n - 2) ，就变成：a^2 = a + 1这就变成了一个一元二次方程，解这个方程，得到：a = (1 ± √5) / 2咱们把这两个解分别叫做α 和β ，也就是α = (1 + √5) / 2 ，β = (1 -√5) / 2 。

那通项公式是不是就是F(n) = C1α^n + C2β^n （这里的 C1 和 C2 是待定系数）呢？接下来，咱们就利用初始条件 F(0) = 0 和 F(1) = 1 来确定 C1 和 C2 。

把 F(0) = 0 代入，得到：C1 + C2 = 0 ，也就是 C2 = - C1再把 F(1) = 1 代入，得到：C1α + C2β = 1把 C2 = - C1 代入上式，得到：C1α - C1β = 1解这个方程，就能求出C1 = 1 / √5 ，C2 = - 1 / √5所以，斐波那契数列的通项公式就是：F(n) = [ (1 / √5) * ((1 + √5) / 2)^n - (1 / √5) * ((1 - √5) / 2)^n ]你看，经过这么一番推导，咱们就找到了斐波那契数列的通项公式！回到开头提到的小朋友跳格子的游戏，当我给他们讲了斐波那契数列的通项公式，他们那充满好奇和惊讶的眼神，让我深深感受到，数学的魅力是无穷的，哪怕是这么一个看似复杂的公式，也能在生活中找到它的影子，给我们带来惊喜。

斐波那契数列的通项公式1，1，2，3，5，8，13，21，……，这个数列从第三项开始，每一项都等于前两项之和。

递推关系：)2()1()(-+-=n f n f n f )3(≥n 其中：1)2()1(==f f 显然这是一个线性递推数列。

通项公式为：⎥⎥⎦⎤⎢⎢⎣⎡⎪⎪⎭⎫ ⎝⎛--⎪⎪⎭⎫ ⎝⎛+nn 25125151很有趣的是：这样一个完全是自然数的数列，通项公式居然是用无理数来表达的通项公式的推导：普通方法一：设常数r ，s 使得)]2()1([)1()(---=--n rf n f s n rf n f则⎩⎨⎧=-=+11rs s r 解得：⎪⎪⎩⎪⎪⎨⎧-=+=251251s r 5=-s r3≥n 时，有)]2()1([)1()(---=--n rf n f s n rf n f)]3()2([)2()1(---=---n rf n f s n rf n f)]4()3([)3()2(---=---n rf n f s n rf n f……)]1()2([)2()3(rf f s rf f -=- 将以上2-n 个式子相乘，得： )]1()2([)1()(2rf f s n rf n f n -=---又∵ r s -=1 1)2()1(==f f 代入上式12)1()1()(--=-=--n n s r sn rf n f1)1()(-+-=n s n rf n f两边同除ns ，则s s n f s r s n f n n 1)1()(1+-∙=-，设sb s r b n n 11+∙=- 则 A s r b s r A b s r A b n n n +=+=+--11)(s r A -=⇒1)1(11sr b s r s r b n n -+=-+- ⎭⎬⎫⎩⎨⎧-+s r b n 1是首项为=-=-+)(1)1(s r s r s r s f ，公比是s r 的等比数列 n n n sr s r s r s r s r s r b )(1)()(11∙-=∙-=-+-⎥⎦⎤⎢⎣⎡--=--∙-=1)(11)(1n n n s r s r s r s r s r b )(11)(1)(nn n n s r s r s s r s r n f --=∙⎥⎦⎤⎢⎣⎡--= ∴ ⎥⎦⎤⎢⎣⎡--+=n n n f )251()251(51)(普通方法二：前面证法同前，)1()(1-+=-n rf s n f n)2(221-++=--n f r rs s n n)3(33221-+++=---n f r s r rs s n n n……)1(123221f r s r s r rs s n n n n n -----+++++=123221-----+++++=n n n n n r s r s r rs s这是一个以1-n s 为首项、以1-n r 为末项、sr 为公比的等比数列sr s rr s n f n n -∙-=--1)(11)(1n n s r s r --= （注求和公式：q q a a S n n--=11）系比法： 设 11)1(-+++=+n n n n a a x xa a ①系比：111x x += 即 012=-+x x 解得251±-=x 当251--=x 时代入①得11)2511(251-++--+=--+n n n n a a a a⎥⎦⎤⎢⎣⎡+--=+--+11251251251n n n n a a a a ⎭⎬⎫⎩⎨⎧+-+n n a a 2511是首项是25125112-=+-a a ，公比为251-的等比数列， nn n n a a )251()251)(251(25111-=--=+--+ ② 当251+-=x 时代入① 得11)2511(251-+++-+=+-+n n n n a a a a ⎥⎦⎤⎢⎣⎡+-++=+-+-+11251251251n n n n a a a a ⎭⎬⎫⎩⎨⎧+-++n n a a 2511是首项是25125112+=+-+a a ，公比为251+的等比数列， nn n n a a )251()251)(251(25111+=++=+-+-+ ③②－③ nn n n a a )251()251(5)251251(--+==+++- ⎥⎦⎤⎢⎣⎡--+=n n n a )251()251(55特征法：此数列对应特征方程为12+=x x 即012=--x x ，解得251±=x ， 设此数列的通项公式为nn n c c a )251()251(21-++=， 由初始条件121==a a 可知，⎪⎪⎩⎪⎪⎨⎧=-++=-++1)251()251(1251251222121c c c c ，解之得⎪⎪⎩⎪⎪⎨⎧-==515121c c ， 所以⎥⎦⎤⎢⎣⎡--+=n n n a )251(251(55）。

数列的递推公式与通项公式数列是数学中的重要概念，它是按照特定规律排列的一系列数值。

在数列中，递推公式和通项公式是两个关键概念。

递推公式用来描述数列中每一项与前一项之间的关系，而通项公式则是用来计算数列中任意一项的值。

本文将深入探讨数列的递推公式与通项公式，希望能帮助读者对数列的理解更加深入。

一、递推公式递推公式是数列中每一项与前一项之间的关系式。

通过递推公式可以计算出数列中的各项值，从而形成一个完整的数列。

递推公式可以是线性的，也可以是非线性的，具体形式取决于数列的特点。

以斐波那契数列为例，斐波那契数列是一个非常著名的数列，在数列中的前两项是1，之后的每一项都等于前两项之和。

可以得出斐波那契数列的递推公式如下：Fn = Fn-1 + Fn-2其中，Fn表示第n项的值，Fn-1表示第n-1项的值，Fn-2表示第n-2项的值。

通过递推公式，我们可以计算出斐波那契数列中任意一项的值。

除了非线性的递推公式，还有一些数列的递推公式是线性的。

例如，等差数列和等比数列就可以使用线性的递推公式来描述。

在等差数列中，每一项都是前一项加上一个固定的差值d，递推公式可以表示为：an = a1 + (n-1)d其中，an表示第n项的值，a1表示首项的值，d表示公差，n表示项数。

通过递推公式，我们可以轻松地计算出等差数列中任意一项的值。

二、通项公式通项公式是数列中任意一项的值的一般公式。

通过通项公式，我们可以直接计算数列中任意一项的值，而不需要通过递推关系一步一步计算。

以等差数列为例，等差数列的通项公式可以通过递推公式推导得到。

在等差数列中，递推公式为：an = a1 + (n-1)d将此递推公式进行整理和化简，可以得到等差数列的通项公式：an = a1 + (n-1)d通过通项公式，我们可以直接计算出等差数列中任意一项的值。

只需要知道首项的值a1，公差d和要计算的项数n即可。

同样地，等比数列也有对应的通项公式。

等比数列的递推公式为：an = a1 * r^(n-1)其中，an表示第n项的值，a1表示首项的值，r表示公比，n表示项数。

数列的递推关系与通项公式在数学中，数列是由数字按照一定顺序排列而成的序列。

不同的数列可以有不同的递推关系和通项公式来描述它们。

本文将详细介绍数列的递推关系和通项公式的概念、应用和计算方法。

一、递推关系递推关系是指通过前面几项的数值来计算出数列后面一项的数值的关系式。

递推关系可以用于求解以后面的数值为目标的数列问题，通常采用迭代或递归的方式进行计算。

举个例子，斐波那契数列的递推关系为：$F_{n}=F_{n-1}+F_{n-2}$，其中$F_1=1,F_2=1$。

也就是说，斐波那契数列中每一项的值都等于前两项的值之和。

通过递推关系，可以计算出斐波那契数列的任意一项，例如$F_3=2,F_4=3$等。

二、通项公式通项公式是指数列的任意一项能通过公式直接计算出来。

通项公式是数列的一种显式表达式，它不需要通过前面的项数计算后面的项数。

通项公式的求解是数列学习的重点之一。

对于某些数列，其通项公式可能很容易求解，而对于某些数列，其通项公式可能非常难以求解。

一般来说，数列的通项公式可以通过数学归纳法、递推关系和差分方程等方式求解。

举个例子，对于等差数列$a_{n}=a_{1}+(n-1)d$，其中$a_{1}$为首项，$d$为公差，$n$为项数。

通过推导，我们可以得到等差数列的通项公式为$a_{n}=a_{1}+(n-1)d$。

通过这个通项公式，我们可以方便地计算出等差数列中任意一项的值。

三、数列的应用数列是数学中非常重要的一部分，具有广泛的应用价值。

在实际生活和工作中，数列有着很多重要的应用，比如在经济学、物理学、计算机科学等学科中，数列都有着不可或缺的作用。

1. 经济学中的应用经济学中常用的一些数列，如等比数列和收益率数列，可以用于计算商品价格、资产价值和财务报表等。

数列可以帮助经济学家计算和预测未来的经济情况，找出经济规律和趋势，从而为政策制定和决策提供依据。

2. 物理学中的应用在物理学中，数列可用于描述诸如声波、光波等周期性变化的现象。

斐波那契数列的性质斐波那契递推式：斐波那契通项公式：求证过程如下：斐波那契和矩阵的关系：描述这个。

那还是描述矩阵和线性递推式的关系吧线性递推式。

即F(n)和F(n-1),F(n-2),F(n-3),F(n-4)...其阶均是⼀次的关系。

如F(n)=2F(n-1)+F(n-2).F(n)=F(n-1)+2F(n-3)+4F(n-4)...矩阵可以求解这样的递推式。

也就是说可以快速计算F(n).时间复杂度可以到达log(n)级别。

先介绍⼀下我们需要⽤到的关于矩阵的知识。

描述矩阵规模时：n⾏m列。

即⼤⼩为n*m.矩阵乘法：形状上：2*2 和 2*3 的矩阵乘积后,结果是2*3的矩阵。

即 a*b 矩阵和 c*d的矩阵乘积结果是a*d的矩阵。

其中b和c必须相等。

原因看下⾯。

运算法则：对于结果矩阵的第i⾏第j列的位置的结果是由前⼀个矩阵的对应的⾏。

和后⼀个矩阵对应的列。

对应位置 乘积和获得的。

⽐如第1⾏第1列的11.是由前矩阵的第⼀⾏(1,3)和后矩阵的第⼀列(2,3)对应位置乘 积和。

1*2+3*3 = 11 获得的。

如果上述b和c如果不相等。

那么会有地⽅"失配"没有数值可以进⾏ 计算。

不符合矩阵乘法定义。

矩阵乘法性质： 矩阵乘法不符合交换律。

符合结合律。

（具体不分析了。

稍加思考即得。

）矩阵的幂运算：即计算以下式⼦。

其中朴素想法可以通过⼀步⼀步矩阵乘法来获得结果矩阵。

但是从宏观⾓度上去想。

我们把矩阵的乘法理解成⼀种普通的数的乘法。

我们现在要计算数的幂。

可以类⽐快速幂。

那么矩阵也有矩阵的快速幂。

分治思想。

具体实现其实就是快速幂把乘法那部分改成矩阵乘法即可。

代码百度上有很多。

等下我会放⼀份。

（acdreamer矩阵的模板）矩阵计算递推式。

⽐如:对于F(n)=aF(n-1)+bF(n-2)我们可以构造矩阵和矩阵⼆者乘积为：会发现经过⼀次乘积。

我们可以获得矩阵。

那么我们再将这个矩阵乘⼀次就会得到F(3),F(2)的矩阵。