【组合数学】递推方程 ( 递推方程内容概要 | 递推方程定义 | 递推方程示例说明 | 斐波那契数列 )

韩曙亮

发布于 2023-03-28 18:27:44

8060

发布于 2023-03-28 18:27:44

文章被收录于专栏：韩曙亮的移动开发专栏

文章目录

一、递推方程内容概要

递推方程内容概要 :

递推方程定义
递推方程实例
常系数线性递推方程
- 常系数线性递推方程定义
- 公式解法
递推方程在计数问题中的应用

二、递推方程定义

序列

a_0 , a_1 , \cdots , a_n , \cdots

, 记做

\{a_n\}

,

将

a_n

与某些

a_i \ \ ( i < n )

联系起来的等式 ,

a_i

可以是

1

个 , 也可以是多个 ;

将

a_n

用前面若干项

a_{n-1} , a_{n-2} , \cdots

表示出来 ,

称为关于序列

\{a_n\}

的递推方程 ;

递推方程组成 : 下面

3

个是一套 ;

数列
递推方程
初值

给定递推方程 , 和初值 , 就可以 唯一确定一个序列 ;

递推方程表达的关系 : 递推方程只表达了项与之前的项的关系 , 如果初值不同 , 得到的数列是不同的 ;
递推方程与数列关系 : 递推方程代表的不是一个数列 , 是若干个数列的共同的依赖关系 ;

递推方程 , 就是将计数结果 , 表达成一个数列 ,

\{a_n\}

就是通项公式 ;

序列示例 : 如选取问题 , 从

n

个元素中选择

r

个元素 , 如果

n

给定 , 那么

r

就是这个参数 ,

当

r = 0

时的选择个数是

a_0

当

r = 1

时的选择个数是

a_1

\vdots

当

r = n

时的选择个数是

a_n

数列的通项 , 代表了某种计数结果 ;

三、递推方程示例

1 . 阶乘计算数列 :

1! , 2! , 3! , 4! , 5! , 6! , \cdots

数列的第

1

项是

1

的阶乘 , 第

2

项是

2

的阶乘 ,

\cdots

, 第

n

项是

n

的阶乘 ;

2 . 递推方程 :

F(n) = nF(n-1)

如 : 第

4

项的值

F(4) = 5!

, 就等于第

4-1=3

项的值

F(4-1)=F(3) = 4!

乘以

5

;

3 . 初值 :

F(1) = 1

根据

F(1) = 1

可以计算

F(2)

, 根据

F(2)

可以计算

F(3)

, 根据

F(3)

可以计算

F(4)

,

\cdots

, 根据

F(n-1)

可以计算

F(n)

;

四、斐波那契数列 ( Fibnacci )

1 . 斐波那契数列 :

1 , 1 , 2 , 3 , 5 , 8 , 13 , \cdots

2 . 递推方程 :

F(n) = F(n-1) + F(n-2)

描述 : 第

n

项等于第

n-1

项和第

n-2

项之和 ;

如 : 第

4

项的值

F(4) = 5

, 就等于

第

4-1=3

项的值

F(4-1)=F(3) = 3

加上第

4-2=2

项的值

F(4-2) = F(2) =2

;

3 . 初值 :

F(0) = 1 , F(1) = 1

根据

F(0) = 1, F(1) = 1

可以计算

F(2)

, 根据

F(1),F(2)

可以计算

F(3)

, 根据

F(2)F(3)

可以计算

F(4)

,

\cdots

, 根据

F(n-2) , F(n-1)

可以计算

F(n)

;

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-10-21，如有侵权请联系 cloudcommunity@tencent.com 删除

数学

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

数学

登录后参与评论

0 条评论

热度