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 =En (En-1T(n-2)+Un-1)+Un InEn-1T(n-2)+Inyn-1 yn InEn-1(In-2T(n-3)yn-2)+InVn-1+yn =InIn-1In-2T(n-3)+TnEn-19n-2+Tnyn-1+Un Hengfeng Wei (hfwei&inju.edu.cn) 2-5 Linear Recurrences March26,20205/26Theorem (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