Find all solutions of the recurrence relation

Question

I know that if i have a recurrence relation

$$a_n=a_{n-1}+a_{n-2}$$

a solution to the recurrence relation is

$$a_n=\alpha_1 r^n +\alpha_2 r^n$$

but what if the recurrence relation is on the form

$$a_n=a_{n-1}+a_{n-2}+Cn$$

Answer 1

This is a sum of the form $\alpha_1r_1^n+\alpha_2 r_2^n+\gamma n+\delta$. Try to find $\gamma,\delta$ s.t $a_n=\gamma n+\delta$ fulfils our relation $a_n=a_{n−1}+a_{n−2}+Cn.$

Answer 2

There are many similarities between solving ODE and sequence induction relations.

In the same way you find a general solution for homegeneous equation and a particular solution for the full equation for ODE, you can proceed in the same way here.

If we call

• $g_n$ the general solution of $a_n-a_{n-1}-a_{n-2}=0$
• and $p_n,q_n$ two particular solutions of $a_n-a_{n-1}-a_{n-2}=Cn$

Then the sequence $x_n=p_n-q_n$ verifies $x_n-x_{n-1}-x_{n-2}=Cn-Cn=0$, so their difference is solution of the homegeneous equation.

It means that a general solution of the full equation is given by $a_n=g_n+p_n$, where any $p_n$ works.

Now how to find a particular solution ?

When you have a polynom on right hand side of equation, you can try to find a polynom as solution.

$P(n)-P(n-1)-P(n-2)=Cn$

If $P(n)=an^d+...$ then $Cn=an^d-an^d-an^d+...=-an^d+Q(n)$ where $\deg(Q)<d$.

So we see that in our case, the degree of $P$ is at most $1$ and we search a solution $P(n)=an+b$.

Reporting in the equation gives : $an+b-a(n-1)-b-a(n-2)-b=-an+3a-b=Cn$

And by identification $a=-C,\ b=3a\ $ thus $\ P(n)=-(n+3)C$.

Finally with $\phi=\frac{1+\sqrt 5}{2}$ and $\bar\phi=1-\phi:\quad a_n=\alpha{\vphantom{\bar\phi}\phi}^{\,n}+\beta\bar\phi^{\,n}-(n+3)C$