Bryan's question at Yahoo! Answers regarding linear recurrence relations

[MarkFL]

Here is the question:

Discrete Mathematics Question?

Find the solution to recurrence relations.

A) An = An-1 + 6 An-2 , Ao = 3 , A1 = 6


B) An+2 = -4 An+1 + 5 An , A0 = 2 , A1 = 8

Here is a link to the question:

Discrete Mathematics Question? - Yahoo! Answers

I have posted a link there to this topic so the OP may find my response.

 

[MarkFL]

Hello Bryan,

A) We are given the recurrence relation

\(\displaystyle A_{n}=A_{n-1}+6A_{n-2}\) where \(\displaystyle A_0=3,\,A_1=6\)

The associated characteristic equation is:

\(\displaystyle r^2-r-6=(r+2)(r-6)=0\)

Our characteristic roots are then \(\displaystyle r=-2,\,6\)

Hence, the closed form is:

\(\displaystyle A_n=k_1(-2)^n+k_2(6)^n\)

We may use the initial values to determine the parameters $k_i$:

\(\displaystyle A_0=k_1(-2)^0+k_2(6)^0=k_1+k_2=3\)

\(\displaystyle A_1=k_1(-2)^1+k_2(6)^1=-2k_1+6k_2=6\,\therefore\,-k_1+3k_2=3\)

Solving this 2X2 system, we find:

\(\displaystyle k_1=k_2=\frac{3}{2}\) and so:

\(\displaystyle A_n=\frac{3}{2}\left((-2)^n+6^n \right)=3\cdot2^{n-1}\left((-1)^n+3^n \right)\)

B) We are given the recurrence relation:

\(\displaystyle A_{n+2}=-4A_{n+1}+5A_{n}\) where \(\displaystyle A_0=2,\,A_1=8\)

The associated characteristic equation is:

\(\displaystyle r^2+4r-5=(r+5)(r-1)=0\)

Our characteristic roots are then \(\displaystyle r=-5,\,1\)

Hence, the closed form is:

\(\displaystyle A_n=k_1(-5)^n+k_2\)

We may use the initial values to determine the parameters $k_i$:

\(\displaystyle A_0=k_1(-5)^0+k_2=k_1+k_2=2\)

\(\displaystyle A_1=k_1(-5)^1+k_2=-5k_1+k_2=8\)

Solving this 2X2 system, we find:

\(\displaystyle k_1=-1,\,k_2=3\) and so:

\(\displaystyle A_n=3-(-5)^n\)

To Bryan and any other visitors reading this topic, I encourage you to post other questions of this type in our Discrete Mathematics, Set Theory, and Logic forum.