非线性递推数列

二、非线性递推数列目的要求：掌握常见的非线性递推数列的通项求法（化为：一阶线性、恒等变形不动点法、数归法、母函数法等）重点：（难点）根据其特点采用相应方法求an1、分式递推数列：a=Ca±n+iaa+bn1aa+bba⑴右d=0，贝D =n= +—a cacacn+1 n n令其为b=-b+a (一阶线性……)n+1cnc⑵若d丰0,c丰0，用不动点法(P166TH10)例1、例1、an+1an,2na+1na=1，1解：丄an+解：丄an+1=^―+2n即bann+1=b+2nn例2、4a 一aan+1 nn+1+2a=9,

na=1，求a1n解：变形：an+1bn+12(b+a=n

b+a—4n

b(2—a)—C2—6a+9)

—n =bn+1+a)9b+a一4n令a2一6a+9=0化为⑴型）a=a=312=丄-1bn66n一5a=n 2n一11112=一n=一n :.b=bb 2 n1一2nn1题中a恰好是耳=x的根’即-为人）=諾的不动点TH9P166TH10P166 f(n)=an+b(…)cn一d则①常::21是等比n2是等差u一pIn2、其他非线性递推数列「等差（等比）线性恒等变形后q恒等变形后q迭代

数归

母函数法书上例10、11、12）例10、£n=a=1,2=2,an+13+aa()= n“-1n>3丿，求aan

n一2解：变形aa=3+aan+1n一2 nn一1,an+1 n一2非连续二项）aa=3+aann—3 n—1n一2naa—aa=aan+1n一2 nn—3 nn：1一aan一1n一2na(a +a)=a (an n—1 n—3 n一2 n+1+a)n一1a+a艮卩： 1ana+a——n：1 n：3an一2为常数列）a+a——n+1 an

+a1=3

(n=4).a =3an+1一an n一1二阶常线性齐次..a特征根法）例12、a=1,a=10,a2a=10a3 (n>3)1 2 nn-2 n-1解：变形'a、 n—Ian-1丿22a=10•—n_^，即：b2=10ba n n-1n-2a= nan-1迭代b=(10b”n n-1=10；(10b)4=•••=102•10n-2 4・・102n-21•b2n-22=102n—2-=101-2〕2•10212=10(b tb)n-1 2/.a=10a =10n-1n n-1例11、£},u=2,u=—n0 1 23求证：\u]=2n解：(猜测后证明)适用于递推关系复杂，不便求an或证明a)nn=1时,22_(_) 2nOu=2+2-1=2 3 +2- 32n=2时,1)猜测：再证：23- (-du=8+8-1=2 3 +2-32”_(_])» 2”_(_])»u=2 3 +2_ 3n2«_(_1)n 2-(-i)2 3为整数，则2_3为(0,1)内的纯小数)n=0、1、2显然成立2)数学归纳法证明，设f(n)=2"n=0、1、2显然成立假设n=k时，结论成立，则n=k+1时由u=u(2-2)-uk+1 kk-1 1=yf(k)+2-f0)^22f(k-1)+2-2f(k-1))-—2=2fCt)+2f(k-1)+2-fCt)+2f(k-1)]+2f(k)-2f(k-1)+2-fCt)+2f(k-1)——2又2f(k-1)=f(k+1)+2f(k-1)=(-1)k又贝Uu=2f(+1)+2-f(+1)+2(-»+1+2(-»-5 (•••2(-1)k+1+2(-»为i己k取k+1 2=2fCui=2fCui)+2-fCui)猜测成立

2)再证f(n)为整数/)2n—(—1)" (2+14n—1—2n-2+••.)•/fmJ=f(n)为整数，2-f(n)为(0,1)内的纯小数•••对任意自然数•••对任意自然数n， lu ]=2n2n—(1)3例15、母函数法nn n联系是研究组合数性质的有效方法之一nn将数列C0,Ci,...,Cn当多项式函数f(x)=C0+C1X+…Cnxnn n联系是研究组合数性质的有效方法之一nnn一般：多项式a+ax+…+axn称为数列a的母函数(有限、无限均可)0 1 n 0n而母函数艺axn可求和函数，从而可借助母函数求线性递推数列的通项nn=0例15、a=1,a=—2,a=5a -6a (n>2)0 1 n n—1 n—2解：(显然特征根法可求a)n现用母函数法令f(x)=a+ax+…+a01Xn+… ①•/a—5a +6a =0n n—1 n—2•••设法求出f(x)，即可求an寻求(a—5a ,6a)xnn n—1 n由—5xf(x)=-5a0X-5aiX2—…6x2f(x)=6ax2+…+6a0 n—2①+②+③得：(1—5x+6x2—5anxn—…—1②xn+…-③)=a+(a—5a)x+(a0102+…+(a—5a+6an-1n54—5a+6azx210n+•…=1—7xn-2•f(x)= 1—7x=