(1+k-1)(k-1) =n[1+(10g2n)2kk-1) =n[1+(1og2n)2-1/2(1og2n)2+1/2*log2n [(log, n) /2 第六节差分法(递推关系解法补充) (取自[美]C.L.Liu著,刘振宏译《离散数学基础》,邮电出版社,1982.2,P258) 、有关定义及术语 1.递推关系或差分方程:对于序列aa1,a,,一个关系到a与几个a(i<r)的方程式 就称为刻划该序列的递推关系或差分方程。 2.边界条件或初始条件:只要给定了一个序列在一个或几个时刻的值,按递推关系, 我们就可以逐步地由a1,a-2,求出a,再由a,a11求出a+1等等。这些给定的值即称为边 界条件或初始条件。 3.具有常系数的线性递推关系:形如 Coa+cla -1+c2a-2+.+cka -=fr) 的递推关系称为k阶常系数的线性递推关系。其中,所有的c1为常数,c0和ck均不为 解法 通解=齐次解(方程右边等于0时的解)+特解(方程右边有fr)时的解) (一)齐次解的求法 形如c0a+c1ax+c2ax2+.+ck=0 的方程称为差分方程(1) 的特征方程。若α1是其特征根,则Aax1就是(1)的一个齐次解。 1.k阶特征方程有k个特征根,假定特征方程的根都不相同,那么,可以验证 ar=A,a1+A2a2+ (3)也是差分方程的一个齐次解(通项)。 其中a1,a2,…,∝k是不同的特征根,A1A2…Ak是由边界条件所确定的常数。 例:回顾斐波那契数列,其递推关系是:a=an1+a-2,对应的特征方程为 a2-a-1=0,→ 2→a=A1a1+A2a2是一个齐次解 其中A1A2可由边界条件a=1,a1=1来确定 2.某些根是重根,不妨令α1是m重根(m1时下式就是(3)式的第一项),则与∝1对应 的齐次解为 a= (Agm-+A rm-2+.+Amr+Amra 整个方程的齐次解由形如(4)式的齐次解相加而成=n+{(log 2 n) 2 - 2 (1+ k -1)(k -1) }n = n[1+（log 2 n） 2 - 2 k(k -1) ] =n[1+（log 2 n） 2 -1/2（log 2 n） 2 +1/2*log 2 n] =[（log 2 n） 2 +log 2 n+2]]/2*n 第六节 差分法(递推关系解法补充) (取自[美]C.L.Liu 著，刘振宏译《离散数学基础》， 邮电出版社，1982.2, P258) 一、有关定义及术语 1. 递推关系或差分方程：对于序列 a0,a1,...,ar ,...，一个关系到 ar与几个 ai(i<r)的方程式 就称为刻划该序列的递推关系或差分方程。 2. 边界条件或初始条件：只要给定了一个序列在一个或几个时刻的值，按递推关系， 我们就可以逐步地由 ar-1,ar-2,...求出 ar，再由 ar ,ar-1,...求出 ar+1 等等。这些给定的值即称为边 界条件或初始条件。 3. 具有常系数的线性递推关系：形如 c0ar+c1ar-1+c2ar-2+...+ckar-k=f(r) (1) 的递推关系称为 k 阶常系数的线性递推关系。其中，所有的 ci为常数，c0和 ck均不为 0。 二、解法 通解＝齐次解（方程右边等于 0 时的解）＋特解（方程右边有 f(r)时的解） （一）齐次解的求法 形如 c0 a k＋c1 a k-1＋c2 a k-2＋...＋ck＝0 (2) 的方程称为差分方程(1) 的特征方程。若a1是其特征根，则 r Aa1 就是(1)的一个齐次解。 1. k 阶特征方程有 k 个特征根，假定特征方程的根都不相同，那么，可以验证 r k k r 2 2 r a r = A1a1 + A a +L+ A a (3) 也是差分方程的一个齐次解（通项）。 其中 1 2 k a ,a ,L,a 是不同的特征根，A1,A2,...,AK是由边界条件所确定的常数。 例：回顾斐波那契数列，其递推关系是：ar=ar-1+ar-2，对应的特征方程为 1 0 2 a - a - = , r 2 2 r 1 2 a r A1 1 A 2 1 5 , 2 1 5 Þ = a + a - a = + Þ a = 是一个齐次解。 其中 A1,A2可由边界条件 a0=1,a1=1 来确定。 2. 某些根是重根，不妨令a1 是 m 重根（m=1 时下式就是(3)式的第一项）， 则与a1 对应 的齐次解为： ar=(A1r m-1+A2r m-2+...+Am-1r 1 +Amr 0 ) r a1 (4) 整个方程的齐次解由形如(4)式的齐次解相加而成