下载文档原格式
二阶常系数递推关系求解方法一、递推关系的定义与性质在数学中，递推关系是指通过递推公式来描述数列中各项之间的关系。
常系数递推关系是指递推关系中各项的系数都是常数。
设有一个序列 {an}，其中 n 表示序列中的项数。
如果序列满足递推关系 an = c1an-1+ c2an-2 + ... + ck an-k ，其中ci (1 ≤ i ≤ k) 为常数，那么我们称该序列满足一个 k 阶常系数递推关系。
常系数递推关系的性质：1. 齐次性：如果一个递推关系的非齐次项为0，即对于所有的 i，ci = 0，则该递推关系称为齐次线性递推关系。
2. 非齐次性：如果一个递推关系的非齐次项不为0，即存在一些 i，ci ≠ 0，则该递推关系称为非齐次线性递推关系。
3.初值条件：对于一个k阶线性递推关系，需要给出前k项的初值条件才能确定整个序列。
二、求解齐次线性递推关系的通解对于线性递推关系 an = c1an-1+ c2an-2 + ... + ck an-k ，其中ci (1 ≤ i ≤ k) 为常数，我们可以采用特征根法求解其通解。
1. 假设通解为an = λn ，将其代入递推关系，得到λ^n = c1λ^(n-1)+ c2λ^(n-2) + ... + ck λ^(n-k)2.将等式左边的λ^n移至等式右边，得到λ^n - c1λ^(n-1) - c2λ^(n-2) - ... - ck λ^(n-k) = 03.将该齐次方程转化为特征方程，即λ^k - c1λ^(k-1) - c2λ^(k-2) - ... - ck = 04.解特征方程，得到k个实数或复数根λ1,λ2,...,λk。
5.得到齐次线性递推关系的通解为an = A1λ1^n + A2λ2^n + ... + Akλk^n其中A1,A2,...,Ak为待定系数。
通过给定的初值条件，可以使用线性方程组求解方法来确定待定系数A1,A2,...,Ak。
三、求解非齐次线性递推关系的通解对于非齐次线性递推关系 an = c1an-1+ c2an-2 + ... + ck an-k + f(n)，其中 f(n) 为一个关于 n 的函数，我们可以采用常数变易法求解其通解。
ACM 暑期集训 组合数学（4） 递推 递归 母函数1 递推关系序列{a n }=a 0，a 1，…，a n ，…，把 a n 与某些a i (i <n )联系起来的等式叫做关于序列{a n }的递推方程。
当给定递推方程和适当的初值就唯一确定了序列。
递推关系分类： （1）按常量部分：齐次递推关系：指常量＝0，如F(n)=F(n-1)+F(n-2) 非齐次递推关系：指常量≠0，如F(n)=2*F(n-1)+1 （2）按运算关系：线性关系，如上面的两个；非线性关系，如F(n)=F(n-1)*F(n-2)。
（3）按系数：常系数递推关系，如（1）中的两个；变系数递推关系，如D(n)=(n-1)(D(n-1)+D(n-2)。
（4）按数列的多少一元递推关系，只涉及一个数列，上面的均为一元； 多元递推关系，涉及多个数列，如⎩⎨⎧+=+=----111177n n nn n n a b b b a a Fibonacci 数列为1,1,2,3,5,8,13,.....long long data[100]; data[1]=1; data[2]=1;for(int i=3;i<=50;i++) data[i]=data[i-1]+data[i-2]; while(cin>>n) cout<<data[n]<<endl;例1：直线割平面问题。
在一个无限的平面上有N 条直线，试问这些直线最多能将平面分割成多少区域？F(1) = 2; F(2) = 4; F(3) = 7; F(n)=F(n-1)+n; (n>1)int recurrence(int n) //递推 {f[1]=2;for(i=2;i<=n;i++) f[n]=f[n-1]+n; return f[n]; }int recursion(int n) 递归： {if(n==1) return 2;//递归终止条件 else return recursion(n-1)+n; }更快的方法是求出通项：F(n)=n^(n+1)/2+1例2：HDOJ2050 折线割平面问题在一个无限的平面上有N 条折线，试问这些折线最多能将平面分割成多少区域？F(n)=F(n-1)+4n-3; F(n)=2*n^2-n+1;例3：椭圆割平面问题。
数学中的递归关系与递归公式数学中的递归关系与递归公式是一种重要的数学工具，被广泛应用于各个领域，包括计算机科学、经济学、物理学等。
本文将就递归关系和递归公式的概念、特点以及应用领域进行探讨。
一、递归关系的概念与特点递归关系是指在定义中依赖自身的关系。
换句话说，当前的值取决于前面的值。
在数学中，递归关系常常用于描述数列、集合以及函数之间的关系。
一个典型的递归关系可以用如下的数列来说明：F(n) = F(n-1) + F(n-2)，其中F(1)=1，F(2)=1。
在这个数列中，每一个数都是前两个数的和。
递归关系的特点在于它能够将较大的问题转化为较小的子问题，并通过不断地迭代求解子问题来得到最终的结果。
递归关系有以下几个重要的特点：1. 递归关系需要一个或多个初始条件，也称为基本情况。
在上述例子中，F(1)=1和F(2)=1即为初始条件，没有初始条件的递归关系将无法求解。
2. 递归关系必须能够在每一步中将问题规模缩小。
这保证了问题在经过有限次迭代后能够达到基本情况。
3. 递归关系可能存在多个解，每一个解都是基于不同的初始条件得到的。
4. 递归关系的求解通常通过递归公式来实现。
二、递归公式的概念与求解方法递归公式是一种用于求解递归关系的数学表达式。
它用于将问题的较大实例转化为较小实例的解。
通常情况下，递归公式由递归关系的定义式推导得到。
以斐波那契数列为例，递归关系F(n) = F(n-1) + F(n-2)中的递归公式为F(n) = F(n-1) + F(n-2)，其中F(1)=1，F(2)=1。
通过递归公式，我们可以直接计算出数列中任意位置的值，而无需通过逐步迭代求解。
除了直接求解递归关系外，递归公式还可以用于证明数学定理和推导数学结论。
通过递归公式，我们可以建立数学模型，进而解决实际问题。
三、递归关系与递归公式的应用1. 计算机科学中的递归关系与递归公式在计算机科学中，递归关系和递归公式被广泛应用于算法分析和设计中。
