Solutions to Recurrence Relations
Recall from our previous chapter that first order linear recurrence relations with constant coefficients are recurrence relations of the form $t_n=r\times t_{n-1}+d$tn=r×tn−1+d where $r$r is a non-zero constant and $d$d is any constant.
We also noticed that our familiar arithmetic and geometric sequences both belong to this group of recurrence relations. Every geometric sequence can be written $t_n=r\times t_{n-1}$tn=r×tn−1 with $t_1=a$t1=a given as the first term and the constant coefficient $r$r becoming the common ratio. Also, every arithmetic sequence can be written $t_n=t_{n-1}+d$tn=tn−1+d with $t_1=a$t1=a. Here the constant coefficient $d$d is the common difference and the constant $a$a as the first term.
When we say, 'solve a recurrence relation' this has a slightly different meaning to solving a conventional equation. Solving a recurrence relation means to find the explicit equation that gives $t_n$tn in terms of $n$n, or in other words, the equation that gives us every term by its number only.
We already know the explicit equations for arithmetic recurrence relations and geometric recurrence relations. For arithmetic recurrence relations $t_n=t_{n-1}+d$tn=tn−1+d with $t_1=a$t1=a, our explicit solution is $t_n=a+\left(n-1\right)d$tn=a+(n−1)d. For geometric recurrence relations $t_n=r\times t_{n-1}$tn=r×tn−1 with $t_1=a$t1=a, our explicit solution is $t_n=ar^{n-1}$tn=arn−1.
But what about recurrence relations $t_n=r\times t_{n-1}+d$tn=r×tn−1+d where both $r$r and $d$d are non-zero? In other words, neither arithmetic or geometric? How do we solve these?
Let's say we have the recurrence relation $t_n=20\times t_{n-1}+30$tn=20×tn−1+30. where $t_1=10$t1=10. Let's calculate a few terms and see if we can identify a pattern.
| $t_1$t1 | $=$= | $10$10 |
| $t_2$t2 | $=$= | $20\times10+30$20×10+30 |
| $t_3$t3 | $=$= | $20\left(20\times10+30\right)+30$20(20×10+30)+30 |
| $=$= | $20^2\times10+20\times30+30$202×10+20×30+30 | |
| $t_4$t4 | $=$= | $20\left(20^2\times10+20\times30+30\right)+30$20(202×10+20×30+30)+30 |
| $=$= | $20^3\times10+20^2\times30+20\times30+30$203×10+202×30+20×30+30 | |
| $t_5$t5 | $=$= | $20\left(20^3\times10+20^2\times30+20\times30+30\right)$20(203×10+202×30+20×30+30) |
| $=$= | $20^4\times10+20^3\times30+20^2\times30+20\times30+30$204×10+203×30+202×30+20×30+30 |
Do you see a pattern at all? What about if we put brackets around our results like this?
| $t_1$t1 | $=$= | $\left(10\right)$(10) | $\left(n=1\right)$(n=1) |
| $t_2$t2 | $=$= | $\left(20\times10\right)$(20×10)$+$+$\left[\left(30\right)\right]$[(30)] | $\left(n=2\right)$(n=2) |
| $t_3$t3 | $=$= | $\left(20^2\times10\right)$(202×10)$+$+$\left[\left(20\times30\right)+\left(30\right)\right]$[(20×30)+(30)] | $\left(n=3\right)$(n=3) |
| $t_4$t4 | $=$= | $\left(20^3\times10\right)$(203×10)$+$+$\left[\left(20^2\times30\right)+\left(20\times30\right)+\left(30\right)\right]$[(202×30)+(20×30)+(30)] | $\left(n=4\right)$(n=4) |
| $t_5$t5 | $=$= | $\left(20^4\times10\right)$(204×10)$+$+ $\left[\left(20^3\times30\right)+\left(20^2\times30\right)+\left(20\times30\right)+\left(30\right)\right]$[(203×30)+(202×30)+(20×30)+(30)] | $\left(n=5\right)$(n=5) |
As it turns out, the group of brackets on the left contain the $n$nth term of a geometric sequence with first term $10$10 and $r=20$r=20. The other group of brackets on the left contains the sum of the first $n-1$n−1 terms of a geometric series with first term $30$30 and $r=20$r=20 ($n-1$n−1 because it only appears from $a_2$a2).
This pattern applies in general for recurrence relations $t_n=r\times t_{n-1}+d$tn=r×tn−1+d where $t_1=a$t1=a.
| $t_1$t1 | $=$= | $\left(a\right)$(a) | $\left(n=1\right)$(n=1) |
| $t_2$t2 | $=$= | $\left(ar\right)$(ar)$+$+$\left[\left(d\right)\right]$[(d)] | $\left(n=2\right)$(n=2) |
| $t_3$t3 | $=$= | $\left(ar^2\right)$(ar2)$+$+$\left[\left(r\times d\right)+\left(d\right)\right]$[(r×d)+(d)] | $\left(n=3\right)$(n=3) |
| $t_4$t4 | $=$= | $\left(ar^3\right)$(ar3)$+$+$\left[\left(r^2\times d\right)+\left(r\times d\right)+\left(d\right)\right]$[(r2×d)+(r×d)+(d)] | $\left(n=4\right)$(n=4) |
| $t_5$t5 | $=$= | $\left(ar^4\right)$(ar4)$+$+ $\left[\left(r^3\times d\right)+\left(r^2\times d\right)+\left(r\times d\right)+\left(d\right)\right]$[(r3×d)+(r2×d)+(r×d)+(d)] | $\left(n=5\right)$(n=5) |
Hence, we can see that the general explicit equation must be of the form $t_n=\left(ar^{n-1}\right)$tn=(arn−1)$+$+$\left[S_{n-1}\right]$[Sn−1] where $S_{n-1}$Sn−1 is the sum of $n-1$n−1 terms of a geometric series with first term $d$d and ratio $r$r.
Thus, we have our explicit formula for first order linear recurrence relations with constant coefficients.
$t_n=\left(ar^{n-1}\right)+\left[\frac{d\left(r^{n-1}-1\right)}{r-1}\right]$tn=(arn−1)+[d(rn−1−1)r−1]
Here is the table for recurrence relations and their explicit equations. The first term is $t_1=a$t1=a.
| Recurrence Relation | Explicit Equation | |
| Arithmetic Recurrence Relation | $t_n=t_{n-1}+d$tn=tn−1+d | $t_n=a+d(n-1)$tn=a+d(n−1) |
| Geometric Recurrence Relation | $t_n=r\times t_{n-1}$tn=r×tn−1 | $t_n=ar^{n-1}$tn=arn−1 |
| First Order Linear (Constant Coefficients) | $t_n=r\times t_{n-1}+d$tn=r×tn−1+d | $t_n=\left(ar^{n-1}\right)+\left[\frac{d\left(r^{n-1}-1\right)}{r-1}\right]$tn=(arn−1)+[d(rn−1−1)r−1] |
Examples
Question 1
Solve the difference equation $t_{n+1}=t_n+5$tn+1=tn+5 where $t_1=7$t1=7.
Question 2
Solve the difference equation $t_{n+1}=7t_n$tn+1=7tn where $t_1=2$t1=2.
Question 3
Solve the difference equation $t_{n+1}=2t_n-3$tn+1=2tn−3 where $t_1=4$t1=4.