$u_{n+1} = a u_n +b u_{n-1} +c$

Question

Is there a closed form formula for the general term of a recurrence sequence satisfying $$u_{n+1} = a u_n +b u_{n-1} +c$$ The sequence I am interested in satisfies $u_{n+1} = 8 u_n - 3 u_{n-1} -4$.

Answer 1

You can solve any non-homogeneous, linear recurrence of the above form by converting it to homogeneous form.

(I'll use $n$ instead of $n+1$, doesn't matter anyway!)

$$u_{n}=au_{n-1}+bu_{n-2}+c$$ $$u_{n-1}=au_{n-2}+bu_{n-3}+c$$ Subtract them to get:-

$$u_{n}=(a+1)u_{n-1}+(b-a)u_{n-2}-bu_{n-3}$$ You can then use characteristic polynomial to find the answer.

---

Speaking strictly for the equation you wrote, the characteristic polynomial is $$z^3=9z^2-11z+3$$ which has the roots $$z=1, 4+\sqrt{13}, 4-\sqrt{13}$$ giving $$u_n=a_1+a_2{(4+\sqrt{13})}^n+a_3{(4-\sqrt{13})}^n$$, where $a_i$s depend on the initial condition.

Answer 2

This is a linear difference equation so can be stated as

$$ u = u_h + u_p $$

with

$$ u_h(n+1)-au_h(n)-bu_h(n-1) = 0\\ u_p(n+1)-au_p(n)-bu_p(n-1) = c\\ $$

now making $u_h(n) = \phi^n$ and substituting we have

$$ \phi^n\left(\phi-a-b\phi^{-1}\right) = 0 $$

so

$$ \phi = \frac{1}{2} \left(a\pm\sqrt{a^2+4 b}\right) $$

and

$$ u_h(n) = \frac{C_1}{2^n} \left(a-\sqrt{a^2+4 b}\right)^n+\frac{C_2}{2^n} \left(a+\sqrt{a^2+4 b}\right)^n $$

and also

$$ u_p(n) = \frac{c}{1-a-b} $$

so finally

$$ u(n) = \frac{C_1}{2^n} \left(a-\sqrt{a^2+4 b}\right)^n+\frac{C_2}{2^n} \left(a+\sqrt{a^2+4 b}\right)^n + \frac{c}{1-a-b} $$