Theorem(First-order Linear Recurrences with Constant Coefficients) T(n)=rT(n-1)+g(n)forn>0 with T(0)=a T(n)r"a+ i1 Hengfeng Wei (hfweixinju.edu.cn) 2-5 Linear Recurrences March26,20204/26Theorem (First-order Linear Recurrences with Constant Coefficients) T(n) = rT(n − 1) + g(n) for n > 0 with T(0) = a T(n) = r n a + Xn i=1 r n−i g(i) Hengfeng Wei (hfwei@nju.edu.cn) 2-5 Linear Recurrences March 26, 2020 4 / 26