T(m)=(1+)Tn-1)+2 for n>1 with T(1)=0 m 1n+1 xn=1+ →xnxn-1·…x1=n+1 T(n) T(n-1) 2 十 for n 1 n+1 2 n+1 T(n)T(1) n+1 +2 3≤k≤n+1 T(m)=2(n+1)(Hn+1- 3 ≈2mnn-1.846m Hengfeng Wei (hfweixinju.edu.cn) 2-5 Linear Recurrences March26,20207/26T(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