How do I find the solution to the following reccurent? We will find the solution

Question

How do I find the solution to the following reccurent?

We will find the solution to the following lhcc recurrence an = 4an-1 - 1an-2 - 6an-3 for n ge 3 with initial conditions a0 = 3, a1 = 7, a2 = 5. The first step as usual is to find the characteristic equation by trying a solution of the "geometric" format an = rn, (We assume also r 0). In this case we get: Since we are assuming r 0 we can divide by the smallest power of r, i.e., rn-3 to get the characteristic equation: rn = 4 rn-1 - 1rn-2 - 6rn-3. r3 = 4 r2 - 1r - 6. (Notice since our Ihcc recurrence was degree 3, the characteristic equation is degree 3.) Find the three roots of the characteristic equation r1, r2 and r3. When entering your answers use r1 le r2 le r3: r1 = , r2 = , r3 = . Since the roots are distinct, the general theory (Theorem 3 in section 5.2 of Rosen) tells us that the general solution to our Ihcc recurrence looks like: an = alpha 1(r1)n + alpha 2(r2)n + alpha 3(r3)n for suitable constants alpha 1, alpha 2, alpha 3. To find the values of these constants we have to use the initial conditions a0 = 3, a1 = 7, a2 = 5. These yield by using n=0,n=l and n=2 in the formula above: By plugging in your previously found numerical values forr1, r2 and r3 and doing some algebra, find alpha 1, alpha 2, alpha 3: Note: Ad hoc substitution should work to find the alpha 1, but for those who know linear algebra, note the system of equations above can be written in matrix form as: alpha 1 = alpha 2 = alpha 3 = Note the final solution of the recurrence is: where the numbers Ti, alpha i have been found by your work. This gives an explicit numerical formula in terms of n for the an.

Explanation / Answer

r1=43

r2=3

r3=-2

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.