the solutions to the linear homogeneous recurrence relation (equation *):

F(n) = 18F(n – 1) – 65F(n – 2) (*) F(n) – 18F(n – 1) + 65F(n – 2) = 0 form a two dimensional vector space V. We seek a generating function and make an "intelligent guess" qⁿ is indeed a solution to equation *. However, by itself, qⁿ is merely a single element of V; we need a basis for V. To find our basis, we substitute qⁿ into equation *, which yields the characteristic equation

(equation **): qⁿ - 18q^{n – 1} + 65q^{n – 2} (**)

q² - 18q + 65 (q – 5)(q – 13) = 0

Hence, q = 5 or q = 13. B = { 5ⁿ, 13ⁿ }is a basis for V. Therefore, c₁5ⁿ + c₂13ⁿ is the general solution to equation *. To determine scalar constants c₁ and c₂, we apply the initial conditions to our general solution: F(0) = 0 = c₁5⁰ + c₂13⁰ = c₁ + c₂ F(1) = 1 = c₁5¹ + c₂13¹ = 5c₁ + 13c₂ From which, we deduce: . Thus, is the solution we seek, with .

View other answers by :alpha |bugzpodder