Solving Recursion With Characteristic Polynomial

Question

Say a linear recursion has the form: $a_n=a_{n-1}+a_{n-2}+2^{n-2}$, I know it would be possible to solve it with $a_n=a_{n-1}+a_{n-2}$ and $a_n=2^{n-2}$ and then combine the two using some coefficient A, B.

However, is there any proof to this will always work for linear recursions? (to separate and then combine it) I have seen this method being using a few times on math exchange.

Answer 1

This is very similar to the way you solve linear differential equations with constant coefficients, and for a good reason... We can identify a basis for the space of solutions, which depends on the roots of the polynomial characteristic.

In this case, the characteristic polynomial is $p(\lambda) = \lambda^2 -\lambda -1$ and the solution can be written as $a_n = h_n + p_n$, where $h_n$ is the general solution of the homogeneous equation $h_n = h_{n-1} + h_{n-2}$ and $p_n$ is a particular solution of our equation.

The roots of the characteristic polynomial are $\lambda = \frac{1 \pm \sqrt{5}}{2}$ and so we have that $$ h_n = c_1 \left( \frac{1-\sqrt{5}}{2}\right)^n+ c_2 \left( \frac{1+\sqrt{5}}{2}\right)^n $$

Regarding the particular solution, one usual option is to try something "similar" to the RHS, in this case we can try $p_n= c 2^{n}$. If we plug that into the equation, we can see that $p_n = 2^{n}$ is a solution to the equation.

Finally, the general solution to our equation is given by

$$ a_ n = 2^{n} +c_1 \left( \frac{1-\sqrt{5}}{2}\right)^n+ c_2 \left( \frac{1+\sqrt{5}}{2}\right)^n $$.

Answer 2

It depends what you mean by "always work." The method is

1) Solve the homogeneous recurrence. (The recurrence without the $2^n$). This involves finding the roots of a polynomial, which you can do if the degree inn't two high. In a case like this, the degree is $2$, so you can do it.

2) Guess a solution to the inhomogeneous recurrence. For some functions on the right-hand side, there is an easy way to do it. For example, if instead of $2^n$ we had $3^n$ of $n^2$ there is a well-known way to find a solution. If it were $\sin{n}$ I, at least have no way to go about it.

3) Combine the general solution and the guess to satisfy the initial conditions. This can be done, in principal, but the result may be too complicate to be worth the effort.

There are some nice slides at http://nms.lu.lv/wp-content/uploads/2016/04/21-linear-recurrences.pdf which include proofs of the theorems.