A sequence can be defined by a recurrence relation plus specification of the first term. The recurrence relation is the instruction for finding the next term from any given term. We need the first term as a starting point.
In this chapter, we look at linear recurrence relations. Sometimes, but not always, the sequence generated by the recurrence relation settles down to a steady state. We say the sequence converges to some value.
A linear recurrence relation is written as follows:
$t_{n+1}=kt_n+b,\ t_1=a$tn+1=ktn+b, t1=a
Consider the recurrence relation $t_{n+1}=0.5t_n-2,\ t_1=12$tn+1=0.5tn−2, t1=12
Since $t_1=12$t1=12, the formula says $t_2=0.5\times12-2=4$t2=0.5×12−2=4. Then, $t_3=0.5\times4-2=0$t3=0.5×4−2=0. Continuing in this way we find that the sequence generated by the recurrence relation is
$\left\{12,4,0,-2,-3,-3.5,-3.75,-3.875,-3.9375,-3.96875,...\right\}${12,4,0,−2,−3,−3.5,−3.75,−3.875,−3.9375,−3.96875,...}
We might guess that the sequence is converging to the value $-4$−4 but this is only a guess, so far.
Suppose a particular recurrence relation does converge to a steady state. Then, for large enough $n$n we can say $t_{n+1}\approx t_n$tn+1≈tn. From the linear recurrence relation formula, we have $t_{n+1}=kt_n+b$tn+1=ktn+b but since $t_{n+1}\approx t_n$tn+1≈tn it follows that $t_n\approx kt_n+b$tn≈ktn+b. We treat this as an equation and solve for $t_n$tn and find that
$t_n=\frac{b}{1-k}$tn=b1−k
In the case of the recurrence relation in Example $1$1, we must have $t_n\rightarrow\frac{-2}{1-0.5}=-4$tn→−21−0.5=−4, as expected. We have used the symbol $\rightarrow$→ to indicate that $t_n$tn approaches its limiting value as $n$n becomes very large.
When does a recurrence relation fail to converge?
Think about a recurrence relation $t_{n+1}=kt_n+b,\ \ t_1=a$tn+1=ktn+b, t1=a. If the sequence generated by the recurrence relation converges, its successive terms $t_{n+1}$tn+1 and $t_n$tn must get closer together as $n$n increases.
On the other hand, if the absolute distance $|t_{n+1}-t_n|$|tn+1−tn| increases or stays the same with increasing $n$n, we can be sure that the recurrence relation does not settle down to a fixed value.
The distance $|t_{n+1}-t_n|$|tn+1−tn| is $|kt_n+b-(kt_{n-1}+b)|$|ktn+b−(ktn−1+b)|, which simplifies to $|k||(t_n-t_{n-1})|$|k||(tn−tn−1)|.
From this expression, we can see that the successive differences between terms do not get smaller when $k\le-1$k≤−1 and when $k\ge1$k≥1. That is, when $|k|\ge1$|k|≥1.
So, we can be certain that the recurrence relation does not converge when $k$k is not in the interval $(-1,1)$(−1,1).
We might now begin to believe that the recurrence relation does converge whenever $k\in(-1,1)$k∈(−1,1). But some more steps are needed in order to be sure of this.
An explicit formula for $t_n$tn
It will be helpful if we can derive an explicit formula for $t_n$tn. That is, we want a formula for $t_n$tn that does not depend on $t_{n-1}$tn−1 but instead depends on knowing the first term $t_1$t1.
Starting with $t_{n+1}=kt_n+b$tn+1=ktn+b we see that $t_n=kt_{n-1}+b$tn=ktn−1+b and then $t_{n-1}=kt_{n-2}+b$tn−1=ktn−2+b, and so on. We can experiment with a long chain of substitutions:
$t_{n+1}$tn+1 | $=$= | $kt_n+b$ktn+b |
$=$= | $k(kt_{n-1}+b)+b$k(ktn−1+b)+b | |
$=$= | $k^2t_{n-1}+kb+b$k2tn−1+kb+b | |
$=$= | $k^2(kt_{n-2}+b)+kb+b$k2(ktn−2+b)+kb+b | |
$=$= | $k^3t_{n-2}+k^2b+kb+b$k3tn−2+k2b+kb+b |
and so on.
Following this pattern, we see that this must eventually lead to
$t_{n+1}=k^nt_1+b\left(k^{n-1}+k^{n-2}+...+1\right)$tn+1=knt1+b(kn−1+kn−2+...+1)
The term on the right in brackets is a geometric series. Its sum is $\frac{k^n-1}{k-1}$kn−1k−1 if $k\ne1$k≠1 and the sum is $n$n if $k=1$k=1. So, we have the result
$t_{n+1}=k^nt_1+b\frac{k^n-1}{k-1}$tn+1=knt1+bkn−1k−1 if $k\ne1$k≠1 and
$t_{n+1}=t_1+bn$tn+1=t1+bn if $k=1$k=1
What the explicit formula tells us
We have already dealt with the case $|k|\ge1$|k|≥1. So, we focus on what happens when $-1
Notice that $k^n\rightarrow0$kn→0 when $n$n is large and that $\frac{k^n-1}{k-1}\rightarrow\frac{1}{1-k}$kn−1k−1→11−k. This means that $t_n\rightarrow\frac{b}{1-k}$tn→b1−k as we saw previously.
In conclusion, we can say that a recurrence relation $t_{n+1}=kt_n+b$tn+1=ktn+b converges to a steady state when $k$k is strictly between $-1$−1 and $1$1. Otherwise, we say the recurrence relation diverges.
The value to which a convergent recurrence relation tends is given by $t_n=\frac{b}{1-k}$tn=b1−k for large $n$n.
Consider the recurrence relation $t_{n+1}=1.05t_n-2$tn+1=1.05tn−2, $t_1=12$t1=12.
Since the coefficient of $t_n$tn is not in the interval $(-1,1)$(−1,1) we conclude that the sequence generated by this recurrence relation does not attain a steady state.
The first few terms are $\left\{12,10.6,9.13,7.5865,...\right\}${12,10.6,9.13,7.5865,...}. According to the explicit formula, the $100$100th term is $-3466.7$−3466.7 and $t_{101}=-3642.0$t101=−3642.0.
The recurrence relations defining four different sequences are plotted below.
Which sequences approach a steady-state solution as $n$n becomes large? Select all correct answers.
Consider the recurrence relation $t_{n+1}=0.2t_n+8$tn+1=0.2tn+8 where $t_1=-4$t1=−4.
Does the recurrence relation define a sequence with a long-term steady-state solution?
Yes
No
Yes
No
Which of the following statements about the steady-state is always true?
At the steady-state, $t_{n+1}=t_n$tn+1=tn.
At the steady-state, the value of the terms reach a stationary point and then begin to decrease.
At the steady-state, the value of the terms is always zero.
At the steady-state, $n+1=n$n+1=n.
At the steady-state, $t_{n+1}=t_n$tn+1=tn.
At the steady-state, the value of the terms reach a stationary point and then begin to decrease.
At the steady-state, the value of the terms is always zero.
At the steady-state, $n+1=n$n+1=n.
Find the steady state solution by setting $t_{n+1}$tn+1$=$=$t_n=x$tn=x.
The sequence defined by the recurrence relation $u_{n+1}=ku_n-16$un+1=kun−16, where $u_1=3$u1=3, approaches a long-term steady-state value of $-40$−40. Find the value of $k$k.
]