Steady state solutions to recurrence relations

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.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−1<k<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.

 

 

Example 2

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.

Worked examples

Question 1

Question 2

Question 3

 

 

 

 

 

 

 

 

 

 

]