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

MarkFL

Staff member
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

Staff member
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.