Alternative way of solving linear homogeneous recursive equation

Question

In general I solve an recursive equation like $a_n=3a_{n-1}-2a_{n-2}$ by expressing them as matrices, diagonalize them and then calculate it (very shortened, because I'm confident with that method already).

However now I found another approach and wanted to ask if it is a correct approach and how/why exactly it works:

The characteristic polynomial is $$x^2-3x+2=(x-1)(x-2)$$

Now we can observe that $a_n$ has to be of the form $a_n=a\cdot2^k+b\cdot 1^k$ With the two starting conditions (for example $a_0=-1, a_1=1$) we get the equation system:

$$-1=a+b$$ $$1=2a+b$$

We can easily see $b=-3, a=2$ and therefore the closed form results in:

$$a_n=2\cdot2^k-3\cdot1^k=2^{k+1}-3$$

I know that the solution is right and it seems that the approach is correct. However I don't understand it and (especially the step from $(x-1)(x-2)$ to $a_n=a\cdot2^k+b\cdot1^k$. I would appreciate, if somebody could explain it to me.

Answer 1

The equation is linear, hence if you find particular solutions, any linear combination of those solutions is also a solution. And as the equation is of the second order, it suffices to find two independent solutions to get the most general solution.

Now, by educated guess, you try the Ansatz $a_n=a^n$ for some unknown constant $a$. Plugging in the recurrence,

$$a^n=3a^{n-1}-2a^{n-2}$$ or after simplification,

$$\color{green}{a^2=3a-2}.$$

This is how the characteristic equation appears. Of course we have the solutions $a=1$ and $a=2$, and the general solution of the recurrence is

$$c_11^n+c_22^n.$$

($1^n=1$ and $2^n$ are indeed linearly independent.)

---

More generally, the solution will be a linear combination of the powers of the roots of the characteristic equation (real or complex).

The method falls short in case of multiple roots, because you won't get enough independent solutions. This is solved by using extra Ansatz, of the form $n^ka^n.$

E.g.

$$a_{n+2}-2a_{n+1}+a_n=0$$ yields a double root $a=1$, so that $1^n$ is a solution. Then the Ansatz $n^11^n=n$ gives

$$n+2-2(n+1)+n=0$$ which is indeed true, and the general solution is

$$c_1+c_2n.$$

Answer 2

Make the ansatz $$a_n=q^n$$ to get the characteristic polynomial.

Answer 3

Yes, let $p,q$ be the roots of $$Ax^2+Bx+C=0, ~~~(1)$$ then $$Ap^2+Bp+C=0~~~(2)$$ and $$Aq^2+Bq+C=0~~~(3).$$ Multiply (2) by $D_1 p^n$ and (3) by $D_2 q^n$ and add them to get $$A~(D_1 p^{n+2}+ D_2q^{n+2}) + B ~(D_1 p^{n+1}+ D_2 q^{n+1})+ C ~(D_1 p^n+ D_2 q^n)=0.~~~~(4)$$ Now you can define a sequence (addition of two GPs) as $$f_n= D_1 p^n +D_2 q^n ~~~(5)$$ to re-write (3) as $$A f_{n+2} + B f_{n+1}+C f_n=0. ~~~(6)$$ Clearly, given two of the three equations (1,5,6) thiird is understood.

Now you can claim that solution of (6) is nothing but (5) where $p,q$ are roots of (1). This is what is hidden behind the method when you are asked to put $f_n=x^n$ and get $x=p,q$ then (5) is the solution. $D_1, D_2$ are found by the given values of $f_0$ and $f_1$.

Similarly you can take a cubic in place of (1) and then (5) willbe a recurrence relation among: $f_{n+3}, f_{n+2}, f_{n+1}, f_{n}.$