「数论」特征方程学习笔记

平时做题时,通常会遇见一些求递推数列的题,比如

Luogo P4910fn=fn1+fn2,f1=2,f2=1f_n=f_{n-1}+f_{n-2},f_1=2,f_2=1 ,可以使用 O(log2n)O(\log_2 n) 的矩阵快速幂解决(

其实可以使用特征方程推出求和公式(虽然没什么用(

几个结论

先来看一个栗子:

Fn+2=2×Fn+1+3×FnF_{n+2}=2\times F_{n+1}+3 \times F_{n}

这里 FF 就是一个递推序列

显然可以通过爆算得到一个满足这个递推式的数列 fn=3n,{f}={1,3,9,27,}f_n=3^n, \{f\}=\{1,3,9,27,\cdots\}

就只有这一个满足递推式吗?

注意到 {2×f}={2,6,18,54}\{2\times f\}=\{2,6,18,54\} 也是满足这个递推式的

于是可以的出来一个结论:

若一个等比数列 {fn}\{f_n\} 满足递推式 Fn+2=α×Fn+1+β×FnF_{n+2}=\alpha\times F_{n+1}+\beta \times F_{n} ,那么, {λ×fn}\{\lambda \times f_n\} 也满足递推式 FF

证明很简单(

fn=λ×fnf'_n=\lambda\times f_n

fn+2=αfn+1+βfnf_{n+2}=\alpha f_{n+1}+\beta f_{n}λ×fn+2=λ×αfn+1+λ×βfn\lambda\times f_{n+2}=\lambda\times \alpha f_{n+1}+\lambda\times \beta f_{n}

fn+2=α×fn+1+β×fnf'_{n+2}=\alpha\times f'_{n+1}+\beta\times f'_n 满足 Fn+2=α×Fn+1+β×FnF_{n+2}=\alpha\times F_{n+1}+\beta \times F_{n}


就只有 fn=λ×3nf_n=\lambda\times 3^n 满足这个递推式吗?

通过爆算 又可以得出 gn=(1)ng_n=(-1)^n 是满足这个规律的

{gn}={1,1,1,1,}\{g_n\}=\{-1,1,-1,1,\cdots\}

知道了 {fn}\{f_n\}{gn}\{g_n\} 满足 FF ,那能不能把 ffgg 扔一块呢QAQ

{fn+gn}={0,4,8,28,}\{f_n + g_n\}=\{0, 4, 8, 28,\cdots\} 满足递推式

{2fn+3gn}={1,9,15,57,}\{2f_n+3g_n\}=\{-1,9,15,57,\cdots\} 也满足递推式

于是可以将刚刚推出来的结论完善一下:

若等比数列 {fn}\{f_n\}{gn}\{g_n\}满足递推式 FF ,那么, {λ×fn+ω×gn}\{\lambda \times f_n+\omega\times g_n \} 也满足递推式 FF

证明很简单(

把刚刚的 λ\lambda 改改就好了(


从特殊向一般

上面说了几个特殊情形,尝试推出几个一般性的结论

递推式 fn+pk1fn1+pk2fn2++p0fnk=0f_{n}+p_{k-1}f_{n-1}+p_{k-2}f_{n-2}+\cdots+p_{0}f_{n-k}=0 称作 kk常系数齐次线性递推方程

当然你可以写成 fn=(pk1fn1+pk2fn2++p0fnk)f_{n}=-(p_{k-1}f_{n-1}+p_{k-2}f_{n-2}+\cdots+p_{0}f_{n-k})

按照刚刚的结论,对于数列 {an},{bn},{cn}\{a_n\},\{b_n\},\{c_n\} \cdots 都满足这个递推式,那么他们的线性组合 {λ×an+ω×bn+θ×cn}\{\lambda \times a_n + \omega \times b_n + \theta \times c_n\cdots\} 也满足这个递推式

{an},{bn},{cn}\{a_n\},\{b_n\},\{c_n\} \cdots 就可以称做这个线性递推方程的解

知道了这些解之后,就可以组合出各种各样的满足递推式的数列

但是注意到

如果解 {bn}\{b_n\}可以通过解 {an}\{a_n\} 直接得到,那么 {bn}\{b_n\} 的存在就是无意义的了

如果解 {cn}\{c_n\} 可以通过解 {an},{bn}\{a_n\},\{b_n\} 直接得到,那么 {cn}\{c_n\} 的存在也没有意义了

比如对于 22 阶递推方程 Fn+2=2×Fn+1+3×FnF_{n+2}=2\times F_{n+1}+3 \times F_{n} ,知道了 fn=3nf_n=3^n 是她的解之后, fn=2×3nf'_n=2 \times 3^n 的解就没有任何用处了

如果 {an},{bn}\{a_n\},\{b_n\}\cdots线性无关的,那么就可以通过 {an},{bn}\{a_n\},\{b_n\}\cdots 拼凑出 每一个 合法的数列


实际运用

通过刚刚的讨论,发现一个基本事实:拿到一个递推式,如果能求出它的一组解,还知道 fnf_n 的前几项,就能推出数列的通项公式

就拿刚开始研究性质的递推方程 Fn+2=2×Fn+1+3×FnF_{n+2}=2\times F_{n+1}+3 \times F_{n} ,她的两个解是 fn=3n,gn=(1)nf_{n}=3^n,g_n=(-1)^n

根据之前的结论,可以令 Fn=α×fn+β×gnF_n=\alpha \times f_n + \beta \times g_n

如果知道了前两项 F1=0,F2=4F_1=0,F_2=4 直接带入上面递推式

解得 α=13,β=1\alpha=\frac 1 3 ,\beta = 1 ,也就是说,Fn=13×3n+(1)nFn=3n1+(1)nF_n=\frac13\times3^n+(-1)^n \Longrightarrow F_n=3^{n-1}+(-1)^n


求递推式解

并非所有人都十分强,一样看出来递推式的解

现在需要一个方法去构造递推式的解(

还是以刚刚的 Fn+2=2×Fn+1+3×FnF_{n+2}=2\times F_{n+1}+3 \times F_{n} 的作为栗子

那么不妨令以q为公比的等比数列满足 Fn+2=5×Fn+16×FnF_{n+2}=5\times F_{n+1}-6\times F_n,那么柿子变成

q2×an=2q×an+3×anq^2\times a_n=2q \times a_n+3\times a_n

两边除以 ana_n

q2=2q+3q^2 = 2q + 3

下面就是求解二次方程了(

解得 q1=1,q2=3q_1=-1,q_2=3 ,这样就构造出来了两组解 fn=3n,gn=(1)nf_{n}=3^n,g_n=(-1)^n


一般地,对于长得像上面递推式的柿子,以 xpx^p 代替 Fn+pF_{n+p},得到的方程称作 特征方程

例如

an+2=an+1+2ana_{n+2}=a_{n+1}+2*a_n 的特征方程是 x2=x+2x^2=x+2

an+3=5an+2+3an+1+ana_{n+3}=5*a_{n+2}+3*a_{n+1}+a_n 的特征方程是 x3=5x2+3x+1x^3=5x^2+3x+1

解特征方程,得到的根就可以作为等比数列的公比

有时候二阶特征方程 Δ<0\Delta < 0 怎么办鸭(

只是无实根罢了(,这个特征方程具有共轭负根,剩下的继续算就吼了(

练习

img

1, 算出开头 Luogu P4910 的通项公式(

2, 求斐波那契数列的通项公式(

fn+2=fn+1+fnf_{n+2}=f_{n+1}+f_n

特征方程为

x2=x+1x^2=x+1

解得

x1=152,x2=1+52x_1 = \frac{1-\sqrt{5}}{2},x_2 = \frac{1+\sqrt{5}}{2}

不妨设 fn=α(x1)n1+β(x2)n1f_n = \alpha (x_1)^{n-1} + \beta(x_2)^{n-1}

又已知 f1=1,f2=1f_1=1,f_2=1,代入则有:

解得

代入原柿子,即得

fn=5125(152)n1+5+125(1+52)n1f_n = \frac{\sqrt{5}-1}{2\sqrt{5}}(\frac{1-\sqrt{5}}{2})^{n-1} + \frac{\sqrt{5}+1}{2\sqrt{5}}(\frac{1+\sqrt{5}}{2})^{n-1}

整理,得

fn=15[(1+52)n152)n]f_n=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^n-\frac{1-\sqrt{5}}{2})^n]

3, NOIP 2017 tg 初赛

10, 若 f0=0,f1=1,fn+1=fn+fn12f_0=0,f_1=1,f_{n+1}=\frac{f_{n}+f_{n-1}}{2} ,则随着 ii 的增大,fif_i 将接近于()。

A. 12\frac{1}{2} B. 23\frac{2}{3}

C. 512\frac{\sqrt{5}-1}{2} D. 11

特征方程

x2=x+12x^2 = \frac{x+1}{2}

解得

x1=12,x2=1x_1=-\frac{1}{2},x_2=1

不妨设 fn=α×(12)n+βf_n=\alpha\times (-\frac{1}{2})^n + \beta

代入 f0=0,f1=1f_0=0,f_1=1

得,

α=23,β=23\alpha = -\frac{2}{3},\beta = \frac{2}{3}

fn=23(12)n+23f_n = -\frac{2}{3}\cdot (-\frac{1}{2})^n + \frac{2}{3}

显然

limn+f(n)=23\displaystyle \lim_{n \to +\infty} f(n)=\frac{2}{3}

故选 B


参考资料

  1. 特征方程教程 - blue's Blog
  2. 微分方程的特征方程怎么求的? - 百度知道
  3. 特征方程和特征根 - CSDN
  4. Method of characteristics - Wikipedia
  5. Characteristic polynomial - Wikipeida

Shq 又氵了一篇 Blog 呢(

坚持原创技术分享,您的支持将鼓励我继续创作!