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

2023-03-28 18:27:44 浏览数 (1)

文章目录

  • 一、递推方程 内容概要
  • 二、递推方程 定义
  • 三、递推方程 示例
  • 四、斐波那契数列 ( Fibnacci )

一、递推方程 内容概要

递推方程 内容概要 :

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

二、递推方程 定义

序列

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)

;

数学

0 人点赞