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

文章目录

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

一、递推方程 内容概要

​递推方程 内容概要 :​

• 递推方程定义
• 递推方程实例
• 常系数线性递推方程

• 常系数线性递推方程定义
• 公式解法

• 递推方程在计数问题中的应用

二、递推方程 定义

​序列​

a

,

a

1

,

⋯

 

,

a

n

,

⋯

a_0 , a_1 , \cdots , a_n , \cdots

a0,a1,⋯,an,⋯ , 记做

{

a

n

}

\{a_n\}

{an} ,

将

a

n

a_n

an 与 某些

a

i

(

i

<

n

)

a_i \ \ ( i < n )

ai  (i<n) 联系起来的等式 ,

a

i

a_i

ai 可以是

1

1

1 个 , 也可以是多个 ;

将

a

n

a_n

an 用前面若干项

a

n

−

1

,

a

n

−

2

,

⋯

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

an−1,an−2,⋯ 表示出来 ,

称为 关于序列

{

a

n

}

\{a_n\}

{an} 的 递推方程 ;

​递推方程组成 :​ 下面

3

3

3 个是一套 ;

• 数列
• 递推方程
• 初值

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

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

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

{

a

n

}

\{a_n\}

{an} 就是通项公式 ;

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

n

n

n 个元素中选择

r

r

r 个元素 , 如果

n

n

n 给定 , 那么

r

r

r 就是这个参数 ,

• 当

  r

  =

  r = 0

  r=0 时的选择个数是

  a

  a_0

  a0​

• 当

  r

  =

  1

  r = 1

  r=1 时的选择个数是

  a

  1

  a_1

  a1

  ⋮

  \vdots

  ⋮

• 当

  r

  =

  n

  r = n

  r=n 时的选择个数是

  a

  n

  a_n

  an​

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

三、递推方程 示例

​1 . 阶乘计算数列 :​

1

!

,

2

!

,

3

!

,

4

!

,

5

!

,

6

!

,

⋯

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

1!,2!,3!,4!,5!,6!,⋯

数列的 第

1

1

1 项是

1

1

1 的阶乘 , 第

2

2

2 项是

2

2

2 的阶乘 ,

⋯

\cdots

⋯ , 第

n

n

n 项是

n

n

n 的阶乘 ;

​2 . 递推方程 :​

F

(

n

)

=

n

F

(

n

−

1

)

F(n) = nF(n-1)

F(n)=nF(n−1)

​如 :​ 第

4

4

4 项的值

F

(

4

)

=

5

!

F(4) = 5!

F(4)=5! , 就等于第

4

−

1

=

3

4-1=3

4−1=3 项的值

F

(

4

−

1

)

=

F

(

3

)

=

4

!

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

F(4−1)=F(3)=4! 乘以

5

5

5 ;

​3 . 初值 :​

F

(

1

)

=

1

F(1) = 1

F(1)=1

根据

F

(

1

)

=

1

F(1) = 1

F(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 , \cdots

1,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

n

n 项等于第

n

−

1

n-1

n−1 项 和 第

n

−

2

n-2

n−2 项之和 ;

​如 :​ 第

4

4

4 项的值

F

(

4

)

=

5

F(4) = 5

F(4)=5 , 就等于

第

4

−

1

=

3

4-1=3

4−1=3 项的值

F

(

4

−

1

)

=

F

(

3

)

=

3

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

F(4−1)=F(3)=3

加上 第

4

−

2

=

2

4-2=2

4−2=2 项的值

F

(

4

−

2

)

=

F

(

2

)

=

2

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

F(4−2)=F(2)=2 ;

​3 . 初值 :​

F

(

)

=

1

,

F

(

1

)

=

1

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

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