Theorem (First-order Linear Recurrences) T(n)=InT(n-1)+Un ，forn>0 with T(0)=0 T(m)=n+∑ 2j+1j+2·…En 1≤j<m T(n) T(n-1) Yn xncn-1·C1 En-1···E1 Encn-1···r1 summation factor S(n) T(n) Enxn-1···E1 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
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) Yn xncn-1·C1 En-1···E1 Encn-1···r1 summation factor S(n) T(n) rnxn-1··c1 S(n)=S(n-1)+ Yn xnxn-1···x1 4口·￥①，43，t夏，3)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
T(m)=(1+)T(m-1)+2 for n>1 with T(1)=0 2 4口，1①，43，t夏，里0Q0 Hengfeng Wei (hfweixinju.edu.cn) 2-5 Linear Recurrences farch26.20207/26
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . T(n) = (1 + 1 n )T(n − 1) + 2 for n > 1 with T(1) = 0 xn = 1 + 1 n = n + 1 n =⇒ xnxn−1 · · · x1 = n + 1 T(n) n + 1 = T(n − 1) n + 2 n + 1 for n > 1 T(n) n + 1 = T(1) 2 + 2 X 3≤k≤n+1 1 k T(n) = 2(n + 1)(Hn+1 − 3 2 ) ≈ 2n ln n − 1.846n Hengfeng Wei (hfwei@nju.edu.cn) 2-5 Linear Recurrences March 26, 2020 7 / 26
T(m)=(1+)T(m-1)+2 for n>1 with T(1)=0 m 1n+1 xn=1十二= 4口，1①，43，t夏，里0Q0 Hengfeng Wei (hfweixinju.edu.cn) 2-5 Linear Recurrences farch26.20207/26
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . T(n) = (1 + 1 n )T(n − 1) + 2 for n > 1 with T(1) = 0 xn = 1 + 1 n = n + 1 n =⇒ xnxn−1 · · · x1 = n + 1 T(n) n + 1 = T(n − 1) n + 2 n + 1 for n > 1 T(n) n + 1 = T(1) 2 + 2 X 3≤k≤n+1 1 k T(n) = 2(n + 1)(Hn+1 − 3 2 ) ≈ 2n ln n − 1.846n Hengfeng Wei (hfwei@nju.edu.cn) 2-5 Linear Recurrences March 26, 2020 7 / 26
T(m)=(1+)T(m-1)+2 for n>1 with T(1)=0 m .1n+1 xn=1十二= →xnxn-1·…x1=n+1 4口，1①，43，t夏，30Q0 Hengfeng Wei (hfweixinju.edu.cn) 2-5 Linear Recurrences farch26.20207/26
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . T(n) = (1 + 1 n )T(n − 1) + 2 for n > 1 with T(1) = 0 xn = 1 + 1 n = n + 1 n =⇒ xnxn−1 · · · x1 = n + 1 T(n) n + 1 = T(n − 1) n + 2 n + 1 for n > 1 T(n) n + 1 = T(1) 2 + 2 X 3≤k≤n+1 1 k T(n) = 2(n + 1)(Hn+1 − 3 2 ) ≈ 2n ln n − 1.846n Hengfeng Wei (hfwei@nju.edu.cn) 2-5 Linear Recurrences March 26, 2020 7 / 26