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

1,137

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$$

Share:
1,137
Andrew So
Author by

Andrew So

Updated on August 01, 2022

Comments

  • Andrew So
    Andrew So over 1 year

    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.

  • Andrew So
    Andrew So almost 7 years
    Thanks, this was exactly what I wanted. I noticed in the comment above that you said the answer was given in the wiki page for the arithmetico-geometric sequence. I don't quite see how this sequence can be formed by multiplying the terms of an arithmetic and geometric sequence. This solution also seems very different from the one on the wiki page.
  • Simply Beautiful Art
    Simply Beautiful Art almost 7 years
    I would imagine there are many different ways to go about this, but I agree, I like this solution.