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+ =1 4口，1①，43，t夏，里0Q0 Hengfeng Wei (hfweixinju.edu.cn) 2-5 Linear Recurrences farch26.20204/26
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Theorem (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
Theorem (First-order Linear Recurrences) T(n)=EnT(n-1)+yn for n>0 with T(0)=0 T(m)=n+∑ Cj+1Tj+2·En 1≤j<n 4口，1①，43，t夏，30Q0 Hengfeng Wei (hfweixinju.edu.cn) 2-5 Linear Recurrences farch26.20205/26
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Theorem (First-order Linear Recurrences) T(n) = xnT(n − 1) + yn for n > 0 with T(0) = 0 T(n) = yn + X 1≤j<n yjxj+1xj+2 · · · xn T(n) = xnT(n − 1) + yn = xn (xn−1T(n − 2) + yn−1) + yn = xnxn−1T(n − 2) + xnyn−1 + yn = xnxn−1 (xn−2T(n − 3) + yn−2) + xnyn−1 + yn = xnxn−1xn−2T(n − 3) + xnxn−1yn−2 + xnyn−1 + yn = . . . Hengfeng Wei (hfwei@nju.edu.cn) 2-5 Linear Recurrences March 26, 2020 5 / 26
Theorem (First-order Linear Recurrences) T(n)=InT(n-1)+yn for n>0 with T(0)=0 T(m)=+∑ Cj+1Tj+2·En 1≤j<n T(n)=2nT(n-1)+Un =2n (En-1T(n-2)+Un-1)+Un EnEn-1T(n -2)+inyn-1+yn InEn-1(In-2T(n-3)+Vn-2)+inUn-1+n =InIn-1In-2T(n-3)+TnEn-19n-2+Tnyn-1+Un 4口·￥①，43，t夏，里Q0 Hengfeng Wei (hfwei&inju.edu.cn) 2-5 Linear Recurrences March26,20205/26
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Theorem (First-order Linear Recurrences) T(n) = xnT(n − 1) + yn for n > 0 with T(0) = 0 T(n) = yn + X 1≤j<n yjxj+1xj+2 · · · xn T(n) = xnT(n − 1) + yn = xn (xn−1T(n − 2) + yn−1) + yn = xnxn−1T(n − 2) + xnyn−1 + yn = xnxn−1 (xn−2T(n − 3) + yn−2) + xnyn−1 + yn = xnxn−1xn−2T(n − 3) + xnxn−1yn−2 + xnyn−1 + yn = . . . Hengfeng Wei (hfwei@nju.edu.cn) 2-5 Linear Recurrences March 26, 2020 5 / 26
Theorem (First-order Linear Recurrences) T(n)=InT(n-1)+yn for n >0 with T(0)=0 T(m)=n+∑ Tj+1j+2·…En 1≤j<n 4口，1①，43，t夏，30Q0 Hengfeng Wei (hfweixinju.edu.cn) 2-5 Linear Recurrences farch26.20206/26
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Theorem (First-order Linear Recurrences) T(n) = xnT(n − 1) + yn for n > 0 with T(0) = 0 T(n) = yn + X 1≤j<n yjxj+1xj+2 · · · xn T(n) xnxn−1 · · · x1 | {z } summation factor = T(n − 1) xn−1 · · · x1 + yn xnxn−1 · · · x1 S(n) ≜ T(n) xnxn−1 · · · x1 S(n) = S(n − 1) + yn xnxn−1 · · · x1 Hengfeng Wei (hfwei@nju.edu.cn) 2-5 Linear Recurrences March 26, 2020 6 / 26
Theorem (First-order Linear Recurrences) T(n)=InT(n-1)+yn for n>0 with T(0)=0 T(m)=n+∑ 2j+1j+2·…En 1≤j<n T(n) T(n-1) Un xncn-1·C1 xn-1··E1 EnCn-1··x1 summation factor 4口·￥①，43，t夏，里Q0 Hengfeng Wei (hfweixinju.edu.cn) 2-5 Linear Recurrences farch26.20206/26
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Theorem (First-order Linear Recurrences) T(n) = xnT(n − 1) + yn for n > 0 with T(0) = 0 T(n) = yn + X 1≤j<n yjxj+1xj+2 · · · xn T(n) xnxn−1 · · · x1 | {z } summation factor = T(n − 1) xn−1 · · · x1 + yn xnxn−1 · · · x1 S(n) ≜ T(n) xnxn−1 · · · x1 S(n) = S(n − 1) + yn xnxn−1 · · · x1 Hengfeng Wei (hfwei@nju.edu.cn) 2-5 Linear Recurrences March 26, 2020 6 / 26