Theorem (Linear Homogeneous Recurrences with Constant Coefficients) an=T1an-1+r2an-2+·+rtan-t for n≥t with a0,a1,·,at-1 “Characteristic polymnomial”: q(x)=xt-rizt-1-r2xt-2-...-rt B1(m1),2(m2),·,B(m),·,Bk(mk) Bi is a root with multiplicity mi and m+m2+...+mk =t an ∑cn+∑2n改+…+∑ck2联 0≤j<m1 0≤j<m2 0≤j<mk an is a linear combination of nBn (called "particular solutions") Hengfeng Wei (hfweixinju.edu.cn) 2-5 Linear Recurrences March 26.2020 11/26Theorem (Linear Homogeneous Recurrences with Constant Coefficients) an = r1an−1 + r2an−2 + · · · + rtan−t for n ≥ t with a0, a1, · · · , at−1 “Characteristic polynomial” : q(x) ≡ x t − r1x t−1 − r2x t−2 − · · · − rt β1 (m1), β2 (m2), · · · , βi (mi), · · · , βk (mk) βi is a root with multiplicity mi and m1 + m2 + · · · + mk = t 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 an is a linear combination of n jβ n (called “particular solutions”) Hengfeng Wei (hfwei@nju.edu.cn) 2-5 Linear Recurrences March 26, 2020 11 / 26