精华内容
下载资源
问答
  • 对于一些递推,我们常常会有关于求数列某一项的问题,如果我们能推出其通项公式,那么问题就会变得更好解决,特征方程就是一个有力的工具。 相关定义及引理 我们定义对于数列fnfnf_n递推关系fn=w0+∑ki=1wi∗fn...

    参考文章

    ruanxingzhi

    引入

    对于一些递推式,我们常常会有关于求数列某一项的问题,如果我们能推出其通项公式,那么问题就会变得更好解决,特征方程就是一个有力的工具。

    相关定义及引理

    我们定义对于数列 fn f n 递推关系 fn=w0+ki=1wifnk+i1(n>k) f n = w 0 + ∑ i = 1 k w i ∗ f n − k + i − 1 ( n > k )

    我们给出两个引理:

    引理1:对于一个 w0=0 w 0 = 0 的递推式,若有数列 {an} { a n } 满足递推关系,那么数列 {Aan} { A a n } 也满足递推关系。

    引理2:对于一个 w0=0 w 0 = 0 的递推式,若有数列 {an} { a n } {bn} { b n } 满足递推关系,那么数列 {an+bn} { a n + b n } 也满足递推关系

    对于引理1的证明是比较简单的,既然 {an} { a n } 满足 an=ki=1wiank+i1 a n = ∑ i = 1 k w i ∗ a n − k + i − 1 ,那么我们在两边同乘上A,并把右边的A乘在f的系数之前即得证,即 Aan=ki=1wiAank+i1(n>k) A a n = ∑ i = 1 k w i ∗ A a n − k + i − 1 ( n > k )

    引理2也比较好证。我们知道 an=ki=1wiank+i1 a n = ∑ i = 1 k w i ∗ a n − k + i − 1 bn=ki=1wibnk+i1 b n = ∑ i = 1 k w i ∗ b n − k + i − 1 ,左右分别相加再提取公因式,即 an+bn=ki=1wiank+i1+ki=1wibnk+i1=ki=1wi(ank+i1+bnk+i1) a n + b n = ∑ i = 1 k w i ∗ a n − k + i − 1 + ∑ i = 1 k w i ∗ b n − k + i − 1 = ∑ i = 1 k w i ∗ ( a n − k + i − 1 + b n − k + i − 1 )

    所以如果我们有一些数列满足某递推关系,那么我们对其进行线性组合得到通项公式。一般地,我们认为k阶需要k个线性组合。

    一次线性递推式

    我们称形如 fn=Afn1+B f n = A f n − 1 + B 的递推式为一次线性递推式,即当k=1时。

    怎么由它推导得出我们需要的通项公式呢,我们只需要用一个小trick就够了。

    我们对这个数列进行偏移,得到一个等比数列 {fn+t} { f n + t } 。不妨令 fn+t=q(fn1+t) f n + t = q ( f n − 1 + t ) ,则 fn=qfn1+qtt f n = q f n − 1 + q t − t

    那么我们会得到两个方程:

    {q=Aqtt=B(1) (1) { q = A q t − t = B

    解之得
    {q=At=BA1(2) (2) { q = A t = B A − 1

    利用等比数列通项公式立知 fn=(f1+t)qn1t f n = ( f 1 + t ) ∗ q n − 1 − t

    但有人就会问了,如果 A=1 A = 1 呢?此时我们再看递推关系式,那不就是一个简单的等差数列吗。

    特殊的二次线性递推式

    我们称形如 fn=Afn1+Bfn2+C f n = A f n − 1 + B f n − 2 + C 的递推式为二次线性递推式,即当k=2时。

    我们先来看一个特殊的二次线性递推式,当C=0时,即有 fn=Afn1+Bfn2 f n = A f n − 1 + B f n − 2 。那么我们仍然希望做出一个偏移,使得这个序列能像一次一样处理。

    不妨设 fntfn1=q(fn1tfn2) f n − t f n − 1 = q ( f n − 1 − t f n − 2 )

    fn=(q+t)fn1qtfn2 f n = ( q + t ) f n − 1 − q t f n − 2 ,同样的我们有

    {q+t=Aqt=B(3) (3) { q + t = A q t = − B

    注意到这和韦达定理的形式是一样的,那么我们可以构造一个一元二次方程,这个方程恰好是 x2AxB=0 x 2 − A x − B = 0 。这就是这个递推式的特征方程。

    从之前设的方程,我们知道一个以q为公比的等比数列满足该递推方程,那么现在我们解出了这两个可能的q值,我们可以这样表示通项公式 fn=Aqn11+Bqn12 f n = A ∗ q 1 n − 1 + B ∗ q 2 n − 1 。再代入 f1,f2 f 1 , f 2 的值,就可以解出A和B。


    但这里我们同样没有讨论到特殊的情况,也就是当这个一元二次方程有两个相同的根时。我们重新回到之前所设的递推式,则有 fntfn1=t(fn1tfn2) f n − t f n − 1 = t ( f n − 1 − t f n − 2 )

    则我们可以轻易地得到 fn=tfn1+(f2tf1)tn2 f n = t f n − 1 + ( f 2 − t f 1 ) ∗ t n − 2

    再同时除以 tn t n 可得一个新数列

    fntn=fn1tn1+f2tf1t2 f n t n = f n − 1 t n − 1 + f 2 − t f 1 t 2

    我们容易知道

    fntn=f1t+f2tf1t2(n1) f n t n = f 1 t + f 2 − t f 1 t 2 ∗ ( n − 1 )

    整理得 fn=[(2tf1f2)+(f2tf1)n]tn2 f n = [ ( 2 t f 1 − f 2 ) + ( f 2 − t f 1 ) n ] t n − 2

    但是一般地,我们认为这个表达式过于复杂,不如仍然设为 fn=(A+Bn)tn1 f n = ( A + B n ) t n − 1 ,然后利用 f1,f2 f 1 , f 2 解之。

    一般的二次线性递推式

    上面说过了特殊情况,我们再来看一般的情况 fn=Afn1+Bfn2+C f n = A f n − 1 + B f n − 2 + C

    对于这样的一个递推关系,我们同样希望能化为上面特殊情况的形式,同样的套路。设 fn+t=A(fn1+t)+B(fn2+t) f n + t = A ( f n − 1 + t ) + B ( f n − 2 + t )

    展开即得 (A+B1)t=C ( A + B − 1 ) t = C 。那么只需设 fn+t f n + t 为新的数列,就可以套用之前的方法解决了。

    同样有一个问题,可能存在 A+B1=0 A + B − 1 = 0 的情况。

    那么既然无法偏移,我们设 fntfn1=q(fn1tfn2)+C f n − t f n − 1 = q ( f n − 1 − t f n − 2 ) + C

    则相当于一个 gn=qgn1+C g n = q g n − 1 + C ,用一次线性递推式解决之。

    展开全文
  • 这里主要讨论母函数以及牛顿展开的证明。 考虑卡特兰数的递推,发现这是一个卷积 令f(x)f(x)f(x)为卡特兰数的生成函数 可以将递推表示为 f(x)=x∗f(x)2+1 f(x)=x*f(x)^2+1 f(x)=x∗f(x)2+1 解得 f(x)=1±1−4x...

    组合意义非常显然,经典的路径问题。这里主要讨论母函数以及牛顿展开的证明。

    考虑卡特兰数的递推式,发现这是一个卷积式
    f ( x ) f(x) f(x)为卡特兰数的生成函数
    可以将递推式表示为
    f ( x ) = x ∗ f ( x ) 2 + 1 f(x)=x*f(x)^2+1 f(x)=xf(x)2+1
    解得
    f ( x ) = 1 ± 1 − 4 x 2 x f(x)=\frac{1\pm\sqrt{1-4x}}{2x} f(x)=2x1±14x
    ± \pm ±号怎么取?
    考虑 x = 0 x=0 x=0的时候,取正号显然不合法(卡特兰数第一项)
    故卡特兰数的生成函数为
    f ( x ) = 1 − 1 − 4 x 2 x f(x)=\frac{1-\sqrt{1-4x}}{2x} f(x)=2x114x
    1 − 4 x \sqrt{1-4x} 14x 用牛顿二项式展开
    ( 1 − 4 x ) 1 2 = ∑ k = 0 ∞ ( 1 2 k ) ( − 4 x ) k (1-4x)^{\frac{1}{2}}=\sum_{k=0}^\infty{\frac{1}{2} \choose k}(-4x)^k (14x)21=k=0(k21)(4x)k
    考虑把 ( 1 2 k ) {\frac{1}{2} \choose k} (k21)展开
    ( 1 2 k ) = ( 1 2 ) ( − 1 2 ) ( − 3 2 ) . . . ( 3 2 − k ) k ! = ( − 1 ) k 2 k ∗ k ! ∏ i = 1 k ( 2 i − 3 ) ∏ i = 1 k ( 2 i − 3 ) = ( − 1 ) ∗ 1 ∗ 3 ∗ 5 ∗ . . . ∗ ( 2 k − 3 ) = ( − 1 ) ∗ ( 2 k − 2 ) ! 2 ∗ 4 ∗ 6 ∗ . . . ( 2 k − 2 ) = ( − 1 ) ∗ ( 2 k − 2 ) ! 2 k − 1 ∗ ( k − 1 ) ! {\frac{1}{2} \choose k} = \frac{(\frac{1}{2})(-\frac{1}{2})(-\frac{3}{2})...(\frac{3}{2}-k)}{k!}\\ =\frac{(-1)^{k}}{2^k*k!}\prod_{i=1}^k(2i-3)\\ \prod_{i=1}^k(2i-3)=(-1)*1*3*5*...*(2k-3)\\ =\frac{(-1)*(2k-2)!}{2*4*6*...(2k-2)} =\frac{(-1)*(2k-2)!}{2^{k-1}*(k-1)!} (k21)=k!(21)(21)(23)...(23k)=2kk!(1)ki=1k(2i3)i=1k(2i3)=(1)135...(2k3)=246...(2k2)(1)(2k2)!=2k1(k1)!(1)(2k2)!
    带入原式,得到(这里忽略了 k = 0 k=0 k=0的边界)
    1 − ∑ k = 1 ∞ ( − 1 ) k − 1 ( 2 k − 2 ) ! ( − 4 x ) k 2 2 k − 1 ∗ k ! ∗ ( k − 1 ) ! = ∑ k = 1 ∞ 2 ∗ ( 2 k − 2 ) ! k ! ( k − 1 ) ! x k = ∑ k = 1 ∞ 2 k ( 2 k − 2 k − 1 ) x k 1-\sum_{k=1}^\infty\frac{(-1)^{k-1}(2k-2)!(-4x)^k}{2^{2k-1}*k!*(k-1)!}\\ =\sum_{k=1}^\infty \frac{2*(2k-2)!}{k!(k-1)!}x^k\\ =\sum_{k=1}^\infty\frac{2}{k}{2k-2 \choose k-1}x^k 1k=122k1k!(k1)!(1)k1(2k2)!(4x)k=k=1k!(k1)!2(2k2)!xk=k=1k2(k12k2)xk
    最后除以 2 x 2x 2x(左移)
    得到
    f ( x ) = ∑ k 1 k + 1 ( 2 k k ) x k f(x)=\sum_k \frac{1}{k+1} {2k\choose k}x^k f(x)=kk+11(k2k)xk
    以上就是卡特兰数的推导过程

    展开全文
  • 2021年5月20号的那天,作为单身狗的我就不给大家添乱了,写下了这篇博客,斐波那契数列的通项公式的推导,并且加深举例,让大家可以举一反三,这篇证明为了通俗易懂一点,仅仅用到了高2的数学,一步一步带大家计算...

    斐波那契数列通项公式的推导证明----举一反三

    1-前言

            2021年5月20号的那天,有对象的都忙着约会秀恩爱,而我这样的单身狗,只能自己学习沉淀自己,为梦想而奔波,仿佛是在向世界宣布,520与我无关。这不,那天我在写一篇关于时间复杂度的博客,其中递归的时候遇到了一个数列:1, 1, 3, 5, 9, 15, 25, 41, 67,我想着求出第n项的通项公式,于是当晚发了朋友圈向圈内的朋友么请教一下,521那天也连续发了3条,而且是有偿。
    在这里插入图片描述

            但是大多数的人都只能得出这个结论:
    f ( n + 2 ) = f ( n + 1 ) + f ( n ) + 1 , n ∈ N ∗ , n ≥ 3 f(n+2)=f(n+1)+f(n)+1,n\in{N^*},{n}\geq 3 f(n+2)=f(n+1)+f(n)+1nNn3
            也就是从从第3项开始,每一项都是前2项之和,再加上1,也许是大家那天都很忙,也许是大家都没有头绪证明,对此,我还是决定写篇博客,把这个通项公式求出来,分享到朋友圈,一个是记录自己的成长,一个是也让不会并且很感兴趣的人去了解,朋友圈本就是记录分享一些情绪,有趣,感人,美好与学术知识的圣地。

    2-斐波那契

    2-1-什么是斐波那契

            记得小学的时候数学课本上有过一个兔子的故事,简单来说就是一对小兔子(一公一母)一个月后长成一对大兔子,大兔子接下来下个月能生下一对小兔子(也是一公一母),第三个月原本的大兔子再生一对,同时那对小兔子长大了,第四个月……
    把上面的故事里的每个月的(包括第一个月)兔子对数写下来便得到了一个数列:
    1 , 1 , 2 , 3 , 5 , 8 , 13 , 21... 1,1,2,3,5,8,13,21... 1123581321...
            这其中的规律很明显:
    a 1 = a 2 = 1 a_1=a_2=1 a1=a2=1 a n + 2 = a n + 1 + a n a_{n+2}=a_{n+1}+a_n an+2=an+1+an
            这样的一个数列{an}就是著名的斐波那契数列。

            但问题在于这仅仅是它的递推公式,而且还有三个递推变量,怎么看都不爽。这时候就不禁让人想研究它的通项公式了。不急,一步一步来看它通项公式到底长什么样。

    2-2-通项公式的证明

            要解决一道数列的题目,三个递推变量怎么看都不顺眼,第一想法看看能不能干掉一个变量。简而言之,就是把两个变量看作一个整体,看看有没有相邻变量之间的关系。

            首先是这个式子:

    1式: a n + 2 = a n + 1 + a n a_{n+2}=a_{n+1}+a_n an+2=an+1+an

            我们把它定为1式,试一试能不能把 a n + 1 a_{n+1} an+1 拆成两部分给等式两边构成一个形如这样的式子:

    2式: a n + 2 + λ a n + 1 = υ ( a n + 1 + λ a n ) a_{n+2}+λa_{n+1}=\upsilon(a_{n+1}+λa_n) an+2+λan+1=υ(an+1+λan)

            这样 { a n + 1 + λ a n a_{n+1}+λa_n an+1+λan}这个数列就应该满足一种等比数列的性质,也就是公比为 υ \upsilon υ等比数列。其中每一项为:
    a n + 1 + λ a n , 当 n = 1 时 , 首 项 为 a 2 + λ a 1 a_{n+1}+λa_n,当n=1时,首项为a_{2}+λa_1 an+1+λann=1a2+λa1
            由于 a 1 = a 2 = 1 a_1=a_2=1 a1=a2=1得到首项应为:

    首 项 : ( 1 + λ ) 首项: (1+λ) (1+λ)

            我们把2式展开:
    a n + 2 + λ a n + 1 = υ ( a n + 1 + λ a n ) a_{n+2}+λa_{n+1}=\upsilon(a_{n+1}+λa_n) an+2+λan+1=υ(an+1+λan)
            展开 a n + 2 + λ a n + 1 = υ a n + 1 + υ λ a n a_{n+2}+λa_{n+1}=\upsilon a_{n+1}+\upsilon λa_n an+2+λan+1=υan+1+υλan        合并同类项: a n + 2 = ( υ − λ ) a n + 1 + υ λ a n a_{n+2}=(\upsilon-λ)a_{n+1}+\upsilon λa_n an+2=(υλ)an+1+υλan
            与1式相比: a n + 2 = a n + 1 + a n a_{n+2}=a_{n+1}+a_n an+2=an+1+an
            可知: { υ − λ = 1 υ λ = 1 \begin{cases} \upsilon-λ=1\\ \upsilon λ=1 \end{cases} {υλ=1υλ=1        得: υ = λ + 1 \upsilon=λ+1 υ=λ+1
            将 υ = λ + 1 \upsilon=λ+1 υ=λ+1带入2式,可得: a n + 2 + λ a n + 1 = ( λ + 1 ) ( a n + 1 + λ a n ) a_{n+2}+λa_{n+1}=(λ+1)(a_{n+1}+λa_n) an+2+λan+1=(λ+1)(an+1+λan)
            展开,合并同类项:

    3式: a n + 2 = a n + 1 + ( λ 2 + λ ) a n a_{n+2}=a_{n+1}+(λ^2+λ)a_n an+2=an+1+(λ2+λ)an

            与1式相比: a n + 2 = a n + 1 + a n a_{n+2}=a_{n+1}+a_n an+2=an+1+an
            可知: λ 2 + λ = 1 λ^2+λ=1 λ2+λ=1
            那么现在问题就是看看存不存在这个实数 λ,如果有再想办法把它解出来。 λ 2 + λ = 1 λ^2+λ=1 λ2+λ=1 λ 2 + λ + 1 4 = 5 4 λ^2+λ+\frac{1}{4}=\frac{5}{4} λ2+λ+41=45 ( λ + 1 2 ) 2 = 5 4 (λ+\frac{1}{2})^2=\frac{5}{4} (λ+21)2=45 { λ + 1 2 = 5 4 2 = 5 2 2 λ + 1 2 = − 5 4 2 = − 5 2 2 \begin{cases} λ+\frac{1}{2}=\sqrt[2]{\frac{5}{4}}=\frac{\sqrt[2]{5}}{2}\\ λ+\frac{1}{2}=-\sqrt[2]{\frac{5}{4}}=-\frac{\sqrt[2]{5}}{2} \end{cases} λ+21=245 =225 λ+21=245 =225         得出解: { λ 1 = 5 2 − 1 2 λ 2 = − 5 2 − 1 2 \begin{cases} λ_1=\frac{\sqrt[2]{5}-1}{2}\\ \\ λ_2=\frac{-\sqrt[2]{5}-1}{2} \end{cases} λ1=225 1λ2=225 1
            由等比数列的性质:设等比数列的首项为a1,公比为q,则: a k = a 1 ⋅ q k − 1 a_k=a_1·q^{k-1} ak=a1qk1
            { a n + 1 + λ a n a_{n+1}+λa_n an+1+λan}是等比数列,则有: a n + 1 + λ a n = ( a 2 + λ a 1 ) υ n − 1 a_{n+1}+λa_{n}=(a_{2}+λa_1)\upsilon^{n-1} an+1+λan=(a2+λa1)υn1
            首项 ( a 2 + λ a 1 ) = ( 1 + λ ) (a_{2}+λa_1)=(1+λ) (a2+λa1)=(1+λ),公比 υ = λ + 1 \upsilon=λ+1 υ=λ+1,有: a n + 1 + λ a n = ( 1 + λ ) ( λ + 1 ) n − 1 a_{n+1}+λa_{n}=(1+λ)(λ+1)^{n-1} an+1+λan=(1+λ)(λ+1)n1
            有:

    4式: a n + 1 + λ a n = ( λ + 1 ) n a_{n+1}+λa_{n}=(λ+1)^{n} an+1+λan=(λ+1)n

            现将第1个解 λ 1 = 5 2 − 1 2 λ_1=\frac{\sqrt[2]{5}-1}{2} λ1=225 1代入4式后得到:

    5式: a n + 1 + 5 2 − 1 2 a n = ( 5 2 + 1 2 ) n a_{n+1}+\frac{\sqrt[2]{5}-1}{2}a_{n}=(\frac{\sqrt[2]{5}+1}{2})^{n} an+1+225 1an=(225 +1)n

            再将第2个解 λ 2 = − 5 2 − 1 2 λ_2=\frac{-\sqrt[2]{5}-1}{2} λ2=225 1代入4式后得到:

    6式: a n + 1 + − 5 2 − 1 2 a n = ( 1 − 5 2 2 ) n a_{n+1}+\frac{-\sqrt[2]{5}-1}{2}a_{n}=(\frac{1-\sqrt[2]{5}}{2})^{n} an+1+225 1an=(2125 )n

            若要得到 a n a_n an 的通项公式只需5式减去6式,得到:
    5 2 − 1 2 a n − − 5 2 − 1 2 a n = ( 5 2 + 1 2 ) n − ( 1 − 5 2 2 ) n \frac{\sqrt[2]{5}-1}{2}a_{n}-\frac{-\sqrt[2]{5}-1}{2}a_{n}=(\frac{\sqrt[2]{5}+1}{2})^{n}-(\frac{1-\sqrt[2]{5}}{2})^{n} 225 1an225 1an=(225 +1)n(2125 )n 2 5 2 2 a n = ( 1 + 5 2 2 ) n − ( 1 − 5 2 2 ) n \frac{2\sqrt[2]{5}}{2}a_{n}=(\frac{1+\sqrt[2]{5}}{2})^{n}-(\frac{1-\sqrt[2]{5}}{2})^{n} 2225 an=(21+25 )n(2125 )n 5 2 a n = ( 1 + 5 2 2 ) n − ( 1 − 5 2 2 ) n \sqrt[2]{5}a_{n}=(\frac{1+\sqrt[2]{5}}{2})^{n}-(\frac{1-\sqrt[2]{5}}{2})^{n} 25 an=(21+25 )n(2125 )n
            可得通项公式为:
    a n = 1 5 2 [ ( 1 + 5 2 2 ) n − ( 1 − 5 2 2 ) n ] a_{n}=\frac{1}{\sqrt[2]{5}}[(\frac{1+\sqrt[2]{5}}{2})^{n}-(\frac{1-\sqrt[2]{5}}{2})^{n}] an=25 1[(21+25 )n(2125 )n]
            其线性分布为:
    在这里插入图片描述

    2-3-举一反三

            我们回到朋友圈发的那个数列:1, 1, 3, 5, 9, 15, 25, 41, 67,这其中的规律很明显:
    a 1 = a 2 = 1 a_1=a_2=1 a1=a2=1 a n + 2 = a n + 1 + a n + 1 , n ∈ N ∗ , n ≥ 1 a_{n+2}=a_{n+1}+a_n+1,n\in{N^*},{n}\geq 1 an+2=an+1+an+1nNn1
            这其实也是斐波那契数列的特殊形式,我们使用上面推导斐波那契通项公式的方式,推导这个的通项公式,原式等号左右2边加1变一下: a n + 2 = a n + 1 + a n + 1 a_{n+2}=a_{n+1}+a_n+1 an+2=an+1+an+1        得到:

    a式: a n + 2 + 1 = ( a n + 1 + 1 ) + ( a n + 1 ) a_{n+2}+1=(a_{n+1}+1)+(a_n+1) an+2+1=(an+1+1)+(an+1)

            同样,试一试能不能把 a n + 1 + 1 a_{n+1}+1 an+1+1 拆成两部分给等式两边构成一个形如这样的式子:

    b式: a n + 2 + 1 + λ ( a n + 1 + 1 ) = υ [ a n + 1 + 1 + λ ( a n + 1 ) ] a_{n+2}+1+λ(a_{n+1}+1)=\upsilon[a_{n+1}+1+λ(a_n+1)] an+2+1+λ(an+1+1)=υ[an+1+1+λ(an+1)]

            这样 { ( a n + 1 + 1 ) + λ ( a n + 1 ) (a_{n+1}+1)+λ(a_n+1) (an+1+1)+λ(an+1)}这个数列就应该满足一种等比数列的性质,也就是公比为 υ \upsilon υ等比数列。其中每一项为:
    ( a n + 1 + 1 ) + λ ( a n + 1 ) , 当 n = 1 时 , 首 项 为 a 2 + 1 + λ ( a 1 + 1 ) (a_{n+1}+1)+λ(a_n+1),当n=1时,首项为a_{2}+1+λ(a_1+1) (an+1+1)+λ(an+1)n=1a2+1+λ(a1+1)
            由于 a 1 = a 2 = 1 a_1=a_2=1 a1=a2=1得到首项应为:

    首 项 : ( 2 + 2 λ ) 首项: (2+2λ) (2+2λ)

            我们把b式展开:
    a n + 2 + 1 + λ ( a n + 1 + 1 ) = υ [ a n + 1 + 1 + λ ( a n + 1 ) ] a_{n+2}+1+λ(a_{n+1}+1)=\upsilon[a_{n+1}+1+λ(a_n+1)] an+2+1+λ(an+1+1)=υ[an+1+1+λ(an+1)]
            展开 a n + 2 + 1 + λ a n + 1 + λ = υ [ a n + 1 + 1 + λ a n + λ ] a_{n+2}+1+λa_{n+1}+λ=\upsilon[a_{n+1}+1+λa_n+λ] an+2+1+λan+1+λ=υ[an+1+1+λan+λ] a n + 2 + 1 + λ a n + 1 + λ = υ a n + 1 + υ + υ λ a n + υ λ a_{n+2}+1+λa_{n+1}+λ=\upsilon a_{n+1}+\upsilon+\upsilonλa_n+\upsilonλ an+2+1+λan+1+λ=υan+1+υ+υλan+υλ        合并同类项: a n + 2 = ( υ − λ ) a n + 1 + υ λ a n + υ λ + υ − λ − 1 a_{n+2}=(\upsilon-λ) a_{n+1}+\upsilonλa_n+\upsilonλ+\upsilon-λ-1 an+2=(υλ)an+1+υλan+υλ+υλ1
            与原式相比: a n + 2 = a n + 1 + a n + 1 a_{n+2}=a_{n+1}+a_n+1 an+2=an+1+an+1
            可知: { ① υ − λ = 1 ② υ λ = 1 ③ υ λ + υ − λ − 1 = 1 \begin{cases} ①\upsilon-λ=1\\ ②\upsilon λ=1\\ ③\upsilon λ+\upsilon-λ-1=1 \end{cases} υλ=1υλ=1υλ+υλ1=1
            由①式和②式,带入③式,可见③也符合结果,且从①可得 υ = λ + 1 \upsilon=λ+1 υ=λ+1
            将 υ = λ + 1 \upsilon=λ+1 υ=λ+1带入b式,可得: a n + 2 + 1 + λ ( a n + 1 + 1 ) = ( λ + 1 ) [ a n + 1 + 1 + λ ( a n + 1 ) ] a_{n+2}+1+λ(a_{n+1}+1)=(λ+1)[a_{n+1}+1+λ(a_n+1)] an+2+1+λ(an+1+1)=(λ+1)[an+1+1+λ(an+1)]
            展开,合并同类项,可得:

    c式: a n + 2 = a n + 1 + ( λ 2 + λ ) a n + ( λ 2 + λ ) a_{n+2}=a_{n+1}+(λ^2+λ)a_n+(λ^2+λ) an+2=an+1+(λ2+λ)an+(λ2+λ)

            与1原式相比: a n + 2 = a n + 1 + a n + 1 a_{n+2}=a_{n+1}+a_n+1 an+2=an+1+an+1
            可知: λ 2 + λ = 1 λ^2+λ=1 λ2+λ=1
            同样得出解: { λ 1 = 5 2 − 1 2 λ 2 = − 5 2 − 1 2 \begin{cases} λ_1=\frac{\sqrt[2]{5}-1}{2}\\ \\ λ_2=\frac{-\sqrt[2]{5}-1}{2} \end{cases} λ1=225 1λ2=225 1
            由等比数列的性质:设等比数列的首项为a1,公比为q,则: a k = a 1 ⋅ q k − 1 a_k=a_1·q^{k-1} ak=a1qk1
            { ( a n + 1 + 1 ) + λ ( a n + 1 ) (a_{n+1}+1)+λ(a_n+1) (an+1+1)+λ(an+1)}是等比数列,则有: a n + 1 + 1 + λ ( a n + 1 ) = ( a 2 + 1 + λ ( a 1 + 1 ) ) υ n − 1 a_{n+1}+1+λ(a_{n}+1)=(a_{2}+1+λ(a_1+1))\upsilon^{n-1} an+1+1+λ(an+1)=(a2+1+λ(a1+1))υn1
            首项 ( a 2 + 1 + λ ( a 1 + 1 ) ) = ( 2 + 2 λ ) (a_{2}+1+λ(a_1+1))=(2+2λ) (a2+1+λ(a1+1))=(2+2λ),公比 υ = λ + 1 \upsilon=λ+1 υ=λ+1,有:
    a n + 1 + 1 + λ ( a n + 1 ) = ( 2 + 2 λ ) ( λ + 1 ) n − 1 a_{n+1}+1+λ(a_{n}+1)=(2+2λ)(λ+1)^{n-1} an+1+1+λ(an+1)=(2+2λ)(λ+1)n1 a n + 1 + λ a n + λ + 1 = 2 ( 1 + λ ) ( λ + 1 ) n − 1 a_{n+1}+λa_{n}+λ+1=2(1+λ)(λ+1)^{n-1} an+1+λan+λ+1=2(1+λ)(λ+1)n1
            有:

    d式: a n + 1 + λ a n = 2 ( λ + 1 ) n − λ − 1 a_{n+1}+λa_{n}=2(λ+1)^{n}-λ-1 an+1+λan=2(λ+1)nλ1

            现将第1个解 λ 1 = 5 2 − 1 2 λ_1=\frac{\sqrt[2]{5}-1}{2} λ1=225 1代入d式后得到:

    e式: a n + 1 + 5 2 − 1 2 a n = 2 ( 5 2 − 1 2 + 1 ) n − 5 2 − 1 2 − 1 a_{n+1}+\frac{\sqrt[2]{5}-1}{2}a_{n}=2(\frac{\sqrt[2]{5}-1}{2}+1)^{n}-\frac{\sqrt[2]{5}-1}{2}-1 an+1+225 1an=2(225 1+1)n225 11

            再将第2个解 λ 2 = − 5 2 − 1 2 λ_2=\frac{-\sqrt[2]{5}-1}{2} λ2=225 1代入d式后得到:

    f式: a n + 1 + − 5 2 − 1 2 a n = 2 ( − 5 2 − 1 2 + 1 ) n − − 5 2 − 1 2 − 1 a_{n+1}+\frac{-\sqrt[2]{5}-1}{2}a_{n}=2(\frac{-\sqrt[2]{5}-1}{2}+1)^{n}-\frac{-\sqrt[2]{5}-1}{2}-1 an+1+225 1an=2(225 1+1)n225 11

            若要得到 a n a_n an 的通项公式只需e式减去f式,得到: a n + 1 + 5 2 − 1 2 a n = 2 ( 5 2 − 1 2 + 1 ) n − 5 2 − 1 2 − 1 a_{n+1}+\frac{\sqrt[2]{5}-1}{2}a_{n}=2(\frac{\sqrt[2]{5}-1}{2}+1)^{n}-\frac{\sqrt[2]{5}-1}{2}-1 an+1+225 1an=2(225 1+1)n225 11 − - a n + 1 + − 5 2 − 1 2 a n = 2 ( − 5 2 − 1 2 + 1 ) n − − 5 2 − 1 2 − 1 a_{n+1}+\frac{-\sqrt[2]{5}-1}{2}a_{n}=2(\frac{-\sqrt[2]{5}-1}{2}+1)^{n}-\frac{-\sqrt[2]{5}-1}{2}-1 an+1+225 1an=2(225 1+1)n225 11 = = = 5 2 a n = 2 ( 5 2 − 1 2 + 1 ) n − 5 2 − 1 2 − ( 2 ( − 5 2 − 1 2 + 1 ) n − − 5 2 − 1 2 ) \sqrt[2]{5}a_{n}=2(\frac{\sqrt[2]{5}-1}{2}+1)^{n}-\frac{\sqrt[2]{5}-1}{2}-(2(\frac{-\sqrt[2]{5}-1}{2}+1)^{n}-\frac{-\sqrt[2]{5}-1}{2}) 25 an=2(225 1+1)n225 1(2(225 1+1)n225 1) 5 2 a n = 2 ( 5 2 − 1 2 + 1 ) n − 2 ( − 5 2 − 1 2 + 1 ) n − 5 2 − 1 2 + − 5 2 − 1 2 \sqrt[2]{5}a_{n}=2(\frac{\sqrt[2]{5}-1}{2}+1)^{n}-2(\frac{-\sqrt[2]{5}-1}{2}+1)^{n}-\frac{\sqrt[2]{5}-1}{2}+\frac{-\sqrt[2]{5}-1}{2} 25 an=2(225 1+1)n2(225 1+1)n225 1+225 1 5 2 a n = 2 ( 5 2 − 1 2 + 1 ) n − 2 ( − 5 2 − 1 2 + 1 ) n − 5 2 \sqrt[2]{5}a_{n}=2(\frac{\sqrt[2]{5}-1}{2}+1)^{n}-2(\frac{-\sqrt[2]{5}-1}{2}+1)^{n}-\sqrt[2]{5} 25 an=2(225 1+1)n2(225 1+1)n25 5 2 a n = 2 [ ( 1 + 5 2 − 1 2 ) n − ( 1 − 5 2 + 1 2 ) n ] − 5 2 \sqrt[2]{5}a_{n}=2[(1+\frac{\sqrt[2]{5}-1}{2})^{n}-(1-\frac{\sqrt[2]{5}+1}{2})^{n}]-\sqrt[2]{5} 25 an=2[(1+225 1)n(1225 +1)n]25 5 2 a n = 2 [ ( 1 + 5 2 2 ) n − ( 1 − 5 2 2 ) n ] − 5 2 \sqrt[2]{5}a_{n}=2[(\frac{1+\sqrt[2]{5}}{2})^{n}-(\frac{1-\sqrt[2]{5}}{2})^{n}]-\sqrt[2]{5} 25 an=2[(21+25 )n(2125 )n]25
            可得通项公式为:
    a n = 2 5 2 [ ( 1 + 5 2 2 ) n − ( 1 − 5 2 2 ) n ] − 1 a_{n}=\frac{2}{\sqrt[2]{5}}[(\frac{1+\sqrt[2]{5}}{2})^{n}-(\frac{1-\sqrt[2]{5}}{2})^{n}]-1 an=25 2[(21+25 )n(2125 )n]1
            其线性分布为:

    在这里插入图片描述
            完结撒花

    展开全文
  • 斐波那契数列通项公式:斐波那契数列通项公式可以由母函数推导得到,过程如下:首先,我们不知道数列的母函数,先按照定义假设一个母函数定义母函数如上图,Fi为数列的项,i为下标,数列为母函数的各项系数,各项...

    斐波那契数列通项公式:

    b1d1b7f999cda498a330aef024100a94.png

    斐波那契数列通项公式

    可以由母函数推导得到,过程如下:

    首先,我们不知道数列的母函数,先按照定义假设一个母函数

    ab0131fb24796b89bbb50a6e0f4bc377.png

    定义母函数

    如上图,Fi为数列的项,i为下标,数列为母函数的各项系数,各项指数和i相同,因为是无限级数,所以定义一个无穷小量O(x),当x次数足够大的时候,此项就足够接近于零,前提是x是零附近的实数,按照数列的定义,每一项为前两项之和,我们来构建每一项与前两项的差值,从而利用到这个性质,看看有什么结果

    既然要构建系数差值,那么就需要次数相同的项,那么前两项就要乘以x和x的平方,如下:

    fd6ca855a1e05d175235d5bc3cdf45f4.png

    构建相同次数的系数关系

    观察可以看见,可以使用这三个多项式相加减,构造形如Fn-1,Fn,Fn-2的关系

    ad348af7cd62dfaa6058652385c876c1.png

    构造三者关系

    这样,就构造出了连续三项之间的关系,显然,直到无穷项,大部分系数其实都等于零,基于斐波那契数列的定义

    db17c762c51889f18399b29ec91d91b9.png

    消除了无穷项

    显然,F0=0,F1=1,F2=1,代入可得:

    d4a543c2f1c33c32abf05e01f4dcf02c.png

    化简

    次数越高,无穷小量就越接近零,我们使用FG代表无穷级数,那么就有FG*(x^2+x-1)=-x,无穷小量就直接是零了

    dabacbbda0ab0845f79f29bc0bc7e38a.png

    母函数的表达式

    这里假设分母x^2+x-1的根为r和s,那么,母函数可以写成如下形式

    035bbc8756c869fbd6a5841687550672.png

    使用根来定义母函数

    2f60a4fc1007bc2de79969795c55d63a.png

    想办法把r和s分开

    之所以要把r和s分开,是因为分开后,可以分别做泰勒展开

    fb516e9ba874fdd98dcc23b171222bfc.png

    泰勒展开结果

    这样,我们就得到了每一项系数使用r和s的表达结果,规律很容易看出来

    d19d6877e6d99e3ac9517f2e90997aa5.png

    系数通项公式即为数列通项公式

    我们来验证一下,r和s为x^2+x-1的两个根,解一下

    08166cd15ae78979508ec483fbe29467.png

    解方程

    08cd9c858517889de4fe99404b48f537.png

    给r和s赋值

    看数列前5项:

    99202f0702156949bd7111dc95655edf.png

    计算数列前几项

    好像有什么奇怪的东西混进来了,不怕,mma给的是精确的结果,我们把结果化简

    8f33792fd2257b411a796a5a3040777e.png

    前10项和数列一致

    那通项公式呢

    f30e4520573784b5d7b0a20986613563.png

    通项公式化简

    好像怎么化简都得不到网上的标准格式,不怕,我们来验证两种格式是否等价即可

    ae19d75ab7e55be1e472eb441dc79a0a.png

    两种格式等价

    n在自然数内,可以使得Fn和标准格式的通项公式相等,推导过程到此结束。

    121c28a45eed0493158cd705987d41cf.png

    生成函数的数学推导过程

    展开全文
  • 斐波那契数列通项公式证明

    千次阅读 2018-10-11 16:38:38
    其中 是第 斐波那契数。 有递推公式可知: 则: 因式分解:   泰特展开: 则:  (2) 结合生成函数定义, 公式(1),可得: 斐波那契数: 2. 特征向量方法: 设存在矩阵M使得 ...
  • ( 数论专题 )【 斐波那契通项公式 + 等比数列求和公式 】 斐波那契通项公式( 证明略): 例题: 求当n趋向于无穷大,Sn等于什么,输出最简分数。 分子是斐波那契数列,分母是K的 i 次方, K是给定的。...
  • 一.等差与等比数列. ...这个数列的通项公式为: fn=f0+na f_{n}=f_{0}+na fn​=f0​+na 设sn=∑i=0nfis_{n}=\sum_{i=0}^{n}f_{i}sn​=∑i=0n​fi​,则有: sn=(n+1)f0+an(n+1)2 s_{n}=(n+1)f_{...
  • 算法:斐波那契数列通项公式推导

    千次阅读 2020-10-14 17:46:48
    故利用泰勒公式: G(x)=a1−rx+b1−sx=a(1+rx+r2x2+...)+b(1+sx+s2x2+...) G(x) = \frac{a}{1-rx} + \frac{b}{1-sx}\\ = a(1+rx+r^2x^2+...) + b(1+sx+s^2x^2+...) G(x)=1−rxa​+1−sxb​=a(1+rx+r2x2+...)+b(1+sx+...
  • 母函数求递推的通项公式(一)

    千次阅读 2009-03-23 18:28:00
    总是看到有人问递推的通项公式如何求,母函数(Generating function)是一个很好用的工具, 现总结如下以供学习  母函数是组合数学里面的概念,其实就是这坨东西  是不是看不明白,确实有些生疏,再看这一坨 ...
  • sinx的泰勒展开式

    万次阅读 多人点赞 2019-08-19 20:18:33
    最后以省略号结束,代表 “ 无穷 ”,需要求的就是 a0,a1,a2,…… 的值,准确地说就是通项公式。然后,我们就可以开始 “ 微分 ” 了,就是等式两边同时、不停地微分下去。左边的三角函数的微分,其实是四个一...
  • 以前学习矩阵知识的时候,一直觉得在玩数学游戏,没有多少真实的应用,但此次解决实际的问题时,方显得矩阵的强大,其实还可以使用其他方式进行通项推导,但此方法是最简洁、最漂亮的,原来数学还是很有用的!...
  • 首先 \[h_n=\sum_{i}h_ih_{n-i-1}\] 写出 \(h\) 的母函数 \(H(x)\) 那么 \[H(x)=H^2(x)x+1,H(x)=\frac{1-\sqrt{1-4x}}{2x}\] ...引入牛顿二项式 \[(x+y)^{\alpha}=\sum_{k=0}^{\infty}\binom{\alpha}{k}x^{\alpha-k...
  • 二阶齐次线性递推通项公式的寻找

    千次阅读 2017-04-18 23:25:39
    数竞同学问了特征根的问题..然后就顺便把处理递归的理论学习了一个。 虽然好像在OI中没什么用...
  • 通项公式 a n a n a_n ( a 1 = 1 a 1 = 1 a_1=1 ) 这个问题在我之前写的一篇博客上有解法: 点我 接下来考虑生成函数的解法 设这个序列的生成函数 G ( x ) = a 1 x + a 2 x 2 + … = ∑ + ∞ i = 0 ...
  • 泰勒公式和二项式展开定理的共同点对于f(x)=(1+x)^n,采用泰勒展开法有:f(x)=fk0(0)*(x)^0/0!+fk1(0)(x)^1/1!+fk2(0)(x)^2/2!...其中fk0(0),fk1(0).. 分别代表fk(x)的k阶导数,并且传0代替k阶导数中的x,所以有:fk0...
  • C++——求展开式问题

    2018-04-02 21:18:34
    展开式问题 关于展开式的问题,要先找到递推公式,找到每一项的通项,然后累加或累乘,利用循环语句,程序如下:while语句实现do-while语句实现2.计算实数n次方根(循环语句搭配判断以及break和continue) ...
  • 项式定理公式推导

    万次阅读 2019-05-13 10:01:27
  • 排列组合公式式定理 系数性质: ⑴和首末两端等距离的系数相等;...⑵当二式指数n是奇数时,中间...⑷二展开式中奇数和偶数总和相同,都是2^(n-1); ⑸二展开式中所有系数总和是2^n。 ...
  • 泰勒展开式的理解

    千次阅读 2017-12-28 10:10:53
    泰勒展开式在x=x0点展开形式为:【即f(x)只是用来近似t(x)在x0点附近的函数值】 其本质就是为了在某个点附近,用多项式函数来近似其他函数。之所以要使用多项式来近似是因为多项式具有好计算,易求导,且好积分等...
  • 1、斐波那契数列的通项公式推导: 已知斐波那契数列的递推公式为f(n)=f(n−1)+f(n−2)f(n)=f(n-1)+f(n-2)f(n)=f(n−1)+f(n−2)且f(0)=0,f(1)=1f(0)=0,f(1)=1f(0)=0,f(1)=1。 设斐波那契数列的生成函数为F(x)F(x)F(x)...
  • 本节根据置换的和多重线性函数来推导行列式的展开式 0 回忆行列式函数D的性质 (i) 若存在i不等于j有ai= aj 则D(a1,...,an)=0; (ii)D是其自变量的多重线性函数 (iii)D(e1,...,en)=1; (iv)若D是其自变量的交错函数,即...
  • 幂级数展开公式

    千次阅读 2018-08-20 09:25:46
  • 伯努利数、欧拉数与泰勒展开式

    千次阅读 2020-07-07 13:32:07
    伯努利数和正切函数泰勒展开式1.伯努利数2.三角函数泰勒展开式3.双曲三角函数展开式4.自然幂指数和5. 程序应用与计算参考 1.伯努利数 伯努利数是十八世纪瑞士数学家雅各布·伯努利引入的一个数。伯努利数是一个...
  • 泰勒(Taylor)展开式

    千次阅读 2019-10-11 21:34:26
  • 通过泰勒展开式计算反正弦函数

    千次阅读 2017-05-13 21:14:16
    我们知道任何收敛的函数都可以通过泰勒公式展开,通过这个思路我们便可以方便的对一些没有解析表达式的函数求解反函数,泰勒展开的相关知识可以翻阅信号与系统相关书籍。在这里举例计算反正弦函数。 我们知道反正弦...
  • 常见函数泰勒公式展开(清晰)

    万次阅读 多人点赞 2021-02-17 00:12:04
    e x = ∑ n = 0 ∞ 1 n ! x n = 1 + x + 1 2 ! x 2 + ⋯ ∈ ( − ∞ , + ∞ ) sin ⁡ x...知乎:tan(x)的泰勒展开通项公式吗? 2021年2月17日00:12:40 2021年5月9日11:34:16 增加了 tan ⁡ x \tan x% tanx 的泰勒展开
  • 分布概率公式的理解

    千次阅读 2015-03-21 14:27:00
    分布概率公式的理解   多分布是二分布的推广。二分布(也叫伯努利分布)的典型例子是扔硬币,硬币正面朝上概率为p, 重复扔n次硬币,k次为正面的概率即为一个二分布概率。而多分布就像扔骰子,有6个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,305
精华内容 2,122
关键字:

展开式通项公式