Fn Fn-1+Fn-2 for n>1 with Fo=0,F1=1 x2-x-1=0 →0= 2 Fn=c1o”+c26 F%=0=C1+c2 F1=1=c10+C20 1 Fn=- Hengfeng Wei (hfweixinju.edu.cn) 2-5 Linear Recurrences March26,202012/26Fn = Fn−1 + Fn−2 for n > 1 with F0 = 0, F1 = 1 x 2 − x − 1 = 0 =⇒ ϕ = 1 + √ 5 2 , ϕˆ = 1 − √ 5 2 Fn = c1ϕ n + c2ϕˆn F0 = 0 = c1 + c2 F1 = 1 = c1ϕ + c2ϕˆ Fn = 1 √ 5 (ϕ n − ϕˆn ) Hengfeng Wei (hfwei@nju.edu.cn) 2-5 Linear Recurrences March 26, 2020 12 / 26