文章目录
一、递推方程 内容概要
二、递推方程 定义
三、递推方程 示例
四、斐波那契数列 ( Fibnacci )
一、递推方程 内容概要
递推方程 内容概要 :
递推方程定义
递推方程实例
常系数线性递推方程
常系数线性递推方程定义
公式解法
递推方程在计数问题中的应用
二、递推方程 定义
序列 a 0 , a 1 , ⋯ , a n , ⋯ a_0 , a_1 , \cdots , a_n , \cdotsa
0
,a
1
,⋯,a
n
,⋯ , 记做 { a n } \{a_n\}{a
n
} ,
将 a n a_na
n
与 某些 a i ( i < n ) a_i \ \ ( i < n )a
i
(i<n) 联系起来的等式 , a i a_ia
i
可以是 1 11 个 , 也可以是多个 ;
将 a n a_na
n
用前面若干项 a n − 1 , a n − 2 , ⋯ a_{n-1} , a_{n-2} , \cdotsa
n−1
,a
n−2
,⋯ 表示出来 ,
称为 关于序列 { a n } \{a_n\}{a
n
} 的 递推方程 ;
递推方程组成 : 下面 3 33 个是一套 ;
数列
递推方程
初值
给定递推方程 , 和 初值 , 就可以 唯一确定一个序列 ;
递推方程表达的关系 : 递推方程 只表达了 项与之前的项 的关系 , 如果 初值不同 , 得到的数列是不同的 ;
递推方程与数列关系 : 递推方程代表的不是一个数列 , 是 若干个数列 的 共同的依赖关系 ;
递推方程 , 就是将计数结果 , 表达成一个数列 , { a n } \{a_n\}{a
n
} 就是通项公式 ;
序列示例 : 如选取问题 , 从 n nn 个元素中选择 r rr 个元素 , 如果 n nn 给定 , 那么 r rr 就是这个参数 ,
当 r = 0 r = 0r=0 时的选择个数是 a 0 a_0a
0
当 r = 1 r = 1r=1 时的选择个数是 a 1 a_1a
1
⋮ \vdots⋮
当 r = n r = nr=n 时的选择个数是 a n a_na
n
数列的通项 , 代表了某种计数结果 ;
三、递推方程 示例
1 . 阶乘计算数列 : 1 ! , 2 ! , 3 ! , 4 ! , 5 ! , 6 ! , ⋯ 1! , 2! , 3! , 4! , 5! , 6! , \cdots1!,2!,3!,4!,5!,6!,⋯
数列的 第 1 11 项是 1 11 的阶乘 , 第 2 22 项是 2 22 的阶乘 , ⋯ \cdots⋯ , 第 n nn 项是 n nn 的阶乘 ;
2 . 递推方程 : F ( n ) = n F ( n − 1 ) F(n) = nF(n-1)F(n)=nF(n−1)
如 : 第 4 44 项的值 F ( 4 ) = 5 ! F(4) = 5!F(4)=5! , 就等于第 4 − 1 = 3 4-1=34−1=3 项的值 F ( 4 − 1 ) = F ( 3 ) = 4 ! F(4-1)=F(3) = 4!F(4−1)=F(3)=4! 乘以 5 55 ;
3 . 初值 : F ( 1 ) = 1 F(1) = 1F(1)=1
根据 F ( 1 ) = 1 F(1) = 1F(1)=1 可以计算 F ( 2 ) F(2)F(2) , 根据 F ( 2 ) F(2)F(2) 可以计算 F ( 3 ) F(3)F(3) , 根据 F ( 3 ) F(3)F(3) 可以 计算 F ( 4 ) F(4)F(4) , ⋯ \cdots⋯ , 根据 F ( n − 1 ) F(n-1)F(n−1) 可以计算 F ( n ) F(n)F(n) ;
四、斐波那契数列 ( Fibnacci )
1 . 斐波那契数列 : 1 , 1 , 2 , 3 , 5 , 8 , 13 , ⋯ 1 , 1 , 2 , 3 , 5 , 8 , 13 , \cdots1,1,2,3,5,8,13,⋯
2 . 递推方程 : F ( n ) = F ( n − 1 ) + F ( n − 2 ) F(n) = F(n-1) + F(n-2)F(n)=F(n−1)+F(n−2)
描述 : 第 n nn 项等于第 n − 1 n-1n−1 项 和 第 n − 2 n-2n−2 项之和 ;
如 : 第 4 44 项的值 F ( 4 ) = 5 F(4) = 5F(4)=5 , 就等于
第 4 − 1 = 3 4-1=34−1=3 项的值 F ( 4 − 1 ) = F ( 3 ) = 3 F(4-1)=F(3) = 3F(4−1)=F(3)=3
加上 第 4 − 2 = 2 4-2=24−2=2 项的值 F ( 4 − 2 ) = F ( 2 ) = 2 F(4-2) = F(2) =2F(4−2)=F(2)=2 ;
3 . 初值 : F ( 0 ) = 1 , F ( 1 ) = 1 F(0) = 1 , F(1) = 1F(0)=1,F(1)=1
根据 F ( 0 ) = 1 , F ( 1 ) = 1 F(0) = 1, F(1) = 1F(0)=1,F(1)=1 可以计算 F ( 2 ) F(2)F(2) , 根据 F ( 1 ) , F ( 2 ) F(1),F(2)F(1),F(2) 可以计算 F ( 3 ) F(3)F(3) , 根据 F ( 2 ) F ( 3 ) F(2)F(3)F(2)F(3) 可以 计算 F ( 4 ) F(4)F(4) , ⋯ \cdots⋯ , 根据 F ( n − 2 ) , F ( n − 1 ) F(n-2) , F(n-1)F(n−2),F(n−1) 可以计算 F ( n ) F(n)F(n) ;
