am=r1an-1+r2an-2+…+rtan-t for n≥t q(x）=2-r1x2-1-r2x-2 rt an ∑cn野+∑c2改+…+∑ck 0≤j<m1 0≤j<m2 0<j<mk Proof. Take B (m =2)for example. 8m=rm3n-1+r28m-2+…+r3m-tfor n≥t 3m-tq(=0 ng”=n(m-1)Bn-1+r2(m-2)B"-2+…+(m-t)3"-for n≥t Bm-t(n-t)q(8)+Bg(3)=0 Hengfeng Wei (hfweixinju.edu.cn) 2-5 Linear Recurrences March 26,2020 13/26an = r1an−1 + r2an−2 + · · · + rtan−t for n ≥ t q(x) ≡ x t − r1x t−1 − r2x t−2 − · · · − rt an = X 0≤j<m1 c1jn jβ n 1 + X 0≤j<m2 c2jn jβ n 2 + · · · + X 0≤j<mk ckjn jβ n k Proof. Take β (m = 2) for example. β n = r1β n−1 + r2β n−2 + · · · + rtβ n−t for n ≥ t β n−t q(β) = 0 nβn = r1(n − 1)β n−1 + r2(n − 2)β n−2 + · · · + rt(n − t)β n−t for n ≥ t β n−t ￾ (n − t) q(β) + βq ′ (β)
= 0 Hengfeng Wei (hfwei@nju.edu.cn) 2-5 Linear Recurrences March 26, 2020 13 / 26