How to find closed form formula for sequences defined by $a_n = ra_{n-1} + d$

Question

I'm looking for a formula to find the closed form for sequences defined with the form: $$a_n = ra_{n-1} + d$$ I know I can do pattern recognition to find a closed form. For example if given the sequence: $$a_n = 2a_{n-1} + 3, a_1 = 1$$ I could write out the terms: \begin{align*} a_1 &= 1 & &= 4 - 3 & = 2^2 - 3 \\ a_2 &= 5 & &= 8 - 3 & = 2^3 - 3 \\ a_3 &= 13 & &= 16 - 3 & = 2^4 - 3 \\ a_4 &= 29 & &= 32 - 3 & = 2^5 - 3 \\ a_5 &= 61 & &= 64 - 3 & = 2^6 - 3 \end{align*} Which would suggest the closed form: $a_n = 2^{n+1} - 3$

However such a pattern is not always immediately obvious or apparent.

Is there anything like the nice arithmetic $a_n = a_1 + (n - 1)d$ or geometric $a_n = a_1r^{n-1}$ formulas that I could use?

At first I thought this was an Arithmetico-geometric sequence, but I don't believe that is quite what this is. That page led me to Linear difference equations which doesn't include anything about finding a closed form.

Answer 1

Notice that

$$\begin{align}a_n&=ra_{n-1}+d\\&=r(ra_{n-2}+d)+d=r^2a_{n-2}+d+dr\\&=r^2(ra_{n-3}+d)+d+dr=r^3a_{n-3}+d+dr+dr^2\\&=r^3(ra_{n-4}+d)+d+dr+dr^2=r^4a_{n-4}+d+dr+dr^2+dr^3\\&\qquad\vdots\\&=r^{n-1}a_1+d(1+r+r^2+r^3+\dots+r^{n-2})=r^{n-1}a_1+d\frac{1-r^{n-1}}{1-r}\end{align}$$

$$a_n=r^{n-1}a_1+d\frac{1-r^{n-1}}{1-r}$$

Now prove this is true by induction.

---

For your example, we would then have:

$$a_n=2^{n-1}-3(1-2^{n-1})=2^{n+1}-3$$

Answer 2

1) Solving the homogeneous difference equation $a_n=ra_{n-1}$ gives $a_n=cr^n$.

2) A particular solution of the nonhomogeneous difference equation $a_n=ra_{n-1}+d$ is given by $a_n=k$, $\;\;\;$where $k=rk+d$ so $\;k=\frac{d}{1-r}$.

The general soluton of the nonhomogeneous equation is given by adding these two solutions to get

$\;\;\displaystyle a_n=cr^n+\frac{d}{1-r},\;\;$ and $a_2=cr^2+\frac{d}{1-r}=ra_1+d\implies c=\frac{1}{r}\left(a_1-\frac{d}{1-r}\right)$, so

$\;\;\displaystyle a_n=\frac{1}{r}\left(a_1-\frac{d}{1-r}\right)r^n+\frac{d}{1-r}=a_1r^{n-1}+\frac{d}{1-r}\left(1-r^{n-1}\right)$