1. The Fibonacci sequence F_n is defined by F₀ = 0, F₁ = 1, and F_n = F_n-1 +F_n-2 , n 2. Show the following.

F_n = (1/sqrt5) ( [(1+sqrt5)/2]ⁿ [(1-sqrt5)/2]ⁿ ), for all n 0.

Thus, F_n is Q((1/sqrt5) [(1+sqrt5)/2]ⁿ ).

If T_n is the number of additions required to compute F_n , then T₀ = T₁ = 0, and T_n = T_n-1 + T_n-2 + 1, n 2. Hence,

T_n = (1/sqrt5) ( [(1+sqrt5)/2]ⁿ⁺¹ [(1-sqrt5)/2]ⁿ⁺¹ ) - 1, for all n 0.

Thus, T_n is Q((1/sqrt5) [(1+sqrt5)/2]ⁿ⁺¹ ). This is the complexity of the recursive algorithm to compute F_n. Develop a Q(n) non-recursive algorithm to compute F_n .