Steady state solutions to recurrence relations

Lesson

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

Example 1

Consider the recurrence relation $t_{n+1}=0.5t_n-2,\ t_1=12$tn+1=0.5tn2, t1=12

Since $t_1=12$t1=12, the formula says $t_2=0.5\times12-2=4$t2=0.5×122=4. Then, $t_3=0.5\times4-2=0$t3=0.5×42=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+1tn. 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+1tn it follows that $t_n\approx kt_n+b$tnktn+b. We treat this as an equation and solve for $t_n$tn and find that

$t_n=\frac{b}{1-k}$tn=b1k

In the case of the recurrence relation in Example $1$1,  we must have $t_n\rightarrow\frac{-2}{1-0.5}=-4$tn210.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+1tn| 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+1tn| is $|kt_n+b-(kt_{n-1}+b)|$|ktn+b(ktn1+b)|, which simplifies to $|k||(t_n-t_{n-1})|$|k||(tntn1)|.

From this expression, we can see that the successive differences between terms do not get smaller when $k\le-1$k1 and when $k\ge1$k1. 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}$tn1 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=ktn1+b and then $t_{n-1}=kt_{n-2}+b$tn1=ktn2+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(kn1+kn2+...+1)

The term on the right in brackets is a geometric series. Its sum is $\frac{k^n-1}{k-1}$kn1k1 if $k\ne1$k1 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+bkn1k1   if $k\ne1$k1 and

$t_{n+1}=t_1+bn$tn+1=t1+bn   if $k=1$k=1

What the explicit formula tells us

]