an f(an-1;an-2;...;an-t)+g(n) recurrence type typical example first-order linear an nan-1-1 nonlinear am=1/(1+an-1） second-order linear an=0m-1十2an-2 nonlinear am=am-1an-2十Vam-2 variable coefficients am=nan-1+(n-1)am-2+1 tth order an=f(am-1,am-2,.,0n-t)】 full-history 0n=n十an-1十an-2..十a1 divide-and-conquer an=a1n/2」+afn/21十n Table 2.1 Classification of recurrences Hengfeng Wei (hfweixinju.edu.cn) 2-5 Linear Recurrences March26,20203/26an = f(an−1, an−2, . . . , an−t) + g(n) Hengfeng Wei (hfwei@nju.edu.cn) 2-5 Linear Recurrences March 26, 2020 3 / 26