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$