Consider a sequence ao, a1, a2, . .. that satisfies a linear recurrence of the form d an = C+ blan-1 + ban-2+ . . . + baan-d = c+ bian-i (1) i=1 for all n 2 d. Here d, c, b; are constants. We call d the order of this linear recurrence. If c = 0, we say the linear recurrence is homogeneous and otherwise non-homogeneous. Thus, the Fibonaccisequence is homogeneous of order 2. In fact, we now generalize the previous question on the Fibonacci sequence. The characteristic polynomial of this linear recurrence is a p($) :=.1':\" (Mann1 + fawn2 + - - - + bag) = a?\" Z braini. (2) i=1 The n roots A1, . . . , An of this polynomial are called the characteristic roots. They are not necessarily distinct and can be cornplex. In this question, assume that the Ai's are all distinct; also assume that c = 0 (recurrence is homogeneous). (a) Show that for any initial values (1.0,. . . ,ad_1 of the recurrence sequence, there exists constants c1, . . . ,cd such that the recurrence sequence satises a: a... = 2 05A? (3) 21 for all n 2 0. A'sd Alf1 It is best to use matrix notations. Let Vn = for all n 2 d. For instance, Va = Agd A34 1 Af'l ' . _ is called the Vandermonde matrix. Use the fact that V\" is non-singular when the 1 A'l M's are distinct. HINT: Be sure to indicate where you need the LES to be roots of the characteristic polynomial. You may try to imitate the proof for Fibonacci numbers (previous exercise)