Answer to Question #268859 in Discrete Mathematics for Zobird

Question

4. (2 points) Solve these recurrence relations together with the initial conditions given. Each is worth 1 point.

a) an = 6an-1 - 11an-3 +6an-3 for n > 3, a0 = 4, a1 = 6, a2 = 12

b) an = an–1 +9an-2 – 9an-3 for n > 3, a0 = 6, a1= 0, a2 = 30

Answer 1

a)

The characteristic polynomial of this recurrence relation is

$$r^3-6r^2+11r-6=0$$

$$r^2(r-1)-5r(r-1)+6(r-1)=0$$

$$(r-1)(r^2-5r+6)=0$$

$$(r-1)(r-2)(r-3)=0$$

$$r_1=1, r_2=2, r_3=3$$

Hence, the solutions to this recurrence relation are of the form

$$a_n=\alpha_1\cdot1^n+\alpha_2\cdot2^n+\alpha_3\cdot3^n$$

Use the initial conditions

$$a_0=4=\alpha_1+\alpha_2+\alpha_3$$ $$a_1=6=\alpha_1+2\alpha_2+3\alpha_3$$ $$a_2=12=\alpha_1+4\alpha_2+9\alpha_3$$

$$\alpha_1+\alpha_2+\alpha_3=4$$ $$\alpha_2+2\alpha_3=2$$ $$2\alpha_2+6\alpha_3=6$$

$$\alpha_1+\alpha_2+\alpha_3=4$$ $$\alpha_2+2\alpha_3=2$$ $$\alpha_2+3\alpha_3=3$$

$$\alpha_1=3$$ $$\alpha_2=0$$ $$\alpha_3=1$$

Hence, the unique solution to this recurrence relation and the given initial conditions is the sequence $\{a_n\}$ with

$$a_n=3+3^n$$

b)

The characteristic polynomial of this recurrence relation is

$$r^3-r^2-9r+9=0$$

$$r^2(r-1)-9(r-1)=0$$

$$(r-1)(r-3)(r+3)=0$$

$$r_1=1, r_2=-3, r_3=3$$

Hence, the solutions to this recurrence relation are of the form

$$a_n=\alpha_1\cdot1^n+\alpha_2\cdot(-3)^n+\alpha_3\cdot3^n$$

Use the initial conditions

$$a_0=6=\alpha_1+\alpha_2+\alpha_3$$ $$a_1=0=\alpha_1-3\alpha_2+3\alpha_3$$ $$a_2=30=\alpha_1+9\alpha_2+9\alpha_3$$

$$\alpha_1+\alpha_2+\alpha_3=6$$ $$4\alpha_2-2\alpha_3=6$$ $$8\alpha_2+8\alpha_3=24$$

$$\alpha_1+\alpha_2+\alpha_3=6$$ $$2\alpha_2-\alpha_3=3$$ $$\alpha_2+\alpha_3=3$$

$$\alpha_1=3$$ $$\alpha_2=2$$ $$\alpha_3=1$$

Hence, the unique solution to this recurrence relation and the given initial conditions is the sequence $\{a_n\}$ with

$$a_n=3+2\cdot(-3)^n+3^n$$