一、递推方程 内容概要

递推方程 内容概要 :

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

二、递推方程 定义

序列 $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$
  $⋮$
• 当 $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)$ ;

文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。

原文链接：hanshuliang.blog.csdn.net/article/details/109208747