Solving a Linear Recurrence Relation

Question

I made quick progress on this, and then of course got stumped, so here's the problem: $$a_0 = -1, a_1 = -2, a_n = 4a_{n-1} - 3a_{n-2}$$ So, following the way I was taught to solve this type of problem, I do the following: Convert it to $$x^n = 4x^{n-1} - 3x^{n-2}$$ Divide by $x^{n-2}$ because it is the smallest exponent, leaving me with: $x^2 = 4x-3$ Setting equal to zero so I can factor $x^2-4x+3 = 0$ Factored: $(x-3)(x-1)$ Giving me roots of 3 and 1, which not being equal, allows me to continue $$a_n = q_13^n + q_21^n$$ Using the value of $a_0$ Gets me this: $$a_0 = q_1+q_2 = -1$$ Which is useless I think because getting either $q_1$ or $q_2$ equal to $$-1 - q_{1 or 2}$$ Gets me no where because then, plugging it in gets me: $$a_1 = -1 - q_2 + q_21^1 = -2$$ Simplified to: $-1 = -2$ Even I know -1 does not equal -2, I get a similar situation if I try using $a_1$ first, no clue where to go from here, any help much appreciated, thanks guys.

Answer 1

Everything you have done is correct except that you have forgotten to multiply with $3$ in the $a_1$ equation.

More specifically, you have correctly found that $$a_0=-1=q_1\cdot3^0+q_2\cdot1^0 \implies q_2=-1-q_1 \tag1$$ Then you also have that $$a_1=-2=q_1\cdot3^1+q_2\cdot1^1=3q_1-1-q_1 \tag2$$ where the last equality is due to (1). Now equality (2) yields $$-2=2q_1-1 \implies q_1=-\frac12$$ and substituting in (1) you find that $$q_2=-1-q_1=-1-\left(-\frac12\right)=-\frac12$$ In sum $$q_1=q_2=-\frac12$$

Answer 2

A solution using generating functions: Define $A(z) = \sum_{n \ge 0} a_n z^n$, write the recurrence as: $$ a_{n + 2} = 4 a_{n + 1} - 3 a_n \qquad a_0 = -1, a_1 = -2 $$ Multiply the recurrence by $z^n$, sum over $n \ge 0$, recognize: \begin{align} \sum_{n \ge 0} a_{n + 1} z^n &= \frac{A(z) - a_0}{z} \\ \sum_{n \ge 0} a_{n + 2} z^n &= \frac{A(z) - a_0 - a_1 z}{z^2} \end{align} to get: $$ \frac{A(z) + 1 + 2 z}{z^2} = 4 \frac{A(z) + 1}{z} - 3 A(z) $$ Solve for $A(z)$ and split into partial fractions: $$ A(z) = - \frac{1 - 2z}{1 - 4 z + 3 z^2} = - \frac{1}{2} \frac{1}{1 - z} - \frac{1}{2} \frac{1}{1 - 3 z} $$ Those are just two geometric series: $$ a_n = - \frac{1}{2} - \frac{3^n}{2} = - \frac{3^n + 1}{2} $$