A nice recurrence sequence

Question

I want to find general solution for recurrence:

$a_n=7a_{n-1}-10a_{n-2}+4n$

with suppose $c_1, c_2, c_3$ is constant.

I need some tutorial or solution on this challenging recurrence.

Answer 1

The answer is of the form $$ a_n=c_1w_1^n+c_2w_2^n+c_3n+c_4, $$ where $w_1,w_2$ are the roots of $$ x^2-7x+10=0 $$ i.e., $w_1=2,\,w_2=5$.

The part $=c_1w_1^n+c_2w_2^n$ corresponds to the homogeneous recurrence relation: $$ A_n=7A_{n-1}-10A_{n-2}. $$

For the inhomogeneous part $c_3n+c_4$, we obtain $$ c_3n+c_4=7(c_3(n-1)+c_4)-10(c_3(n-2)+c_4)+4n, $$ which implies $$ c_3=7c_3-10c_3+4, $$ and hence $c_3=1$, while $$ c_4=7c_4-10c_4 -7+20, $$ and thus $c_4=13/4$. Altogether $$ a_n=c_12^n+c_25^n+n+\frac{13}{4}. $$

Answer 2

It's a linear difference ( similar to differential ) equation for the sequence $a_n$, write it as

$$a_n - 7\, a_{n-1} + 10 \,a_{n-2} =4n$$

The idea is to write the sequence $a_n$ as a sum of two sequence $a'_n$ and $b_n$ where $a'_n$ satisfies the homogenous equation

$$a'_n - 7\, a'_{n-1} + 10\, a'_{n-2} = 0$$

and $b_n$ is a particular solution of the equation

$$b_n - 7\, b_{n-1} + 10\, b_{n-2} = n$$

Let's find one such $b_n$, search for a polynomial of degree not larger than $1 +2 = 3$ ($1$ the degree of $n$ and $2$ the order of the recurrence ( involves $2$ previous terms).

$$b_n= p n^3 + q n^2 + r n + s$$

Plug in the expressions for $b_n$,$b_{n-1}$, $b_{n-2}$ into the previous equation and identify the coefficients of $n^3$, $n^2$, $n$, $1$. You get a system in $p$,$q$,$r$,$s$ with unique solution $p=q=0$, $r=1$, $s=\frac{13}{4}$ and so $$b_n = n + \frac{13}{4}$$

Now for $a'_n$ that satisfies the homogenous equation, write it as a combination of other sequences that also satisfy it for obvious reasons. Those are some special geometric sequences $\lambda^n$$ the condition being

$$\lambda^n - 7\, \lambda^{n-1} + 10\, \lambda^{n-2} =0$$

for all $n$, equivalently (divide by $\lambda^{n-2}$)

$$\lambda^2 - 7\, \lambda + 10=0$$

There are two possible values for $\lambda$, the roots of the above quadratic equation.

$\lambda= 2$ or $\lambda = 5$ and any combination

$$a'_n = c_1\, 5^n + c_2 \,2^n$$ will be a solution of the homogenous equation ( and these will be all of them).

Therefore $a_n = a'_n + b_n$, that is

$$a_n = c_1\, 5^n + c_2\, 2^n + n + \frac{13}{4}$$