NZ Level 7 (NZC) Level 2 (NCEA)
topic badge
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(ktn1+b)+b
  $=$= $k^2t_{n-1}+kb+b$k2tn1+kb+b
  $=$= $k^2(kt_{n-2}+b)+kb+b$k2(ktn2+b)+kb+b
  $=$= $k^3t_{n-2}+k^2b+kb+b$k3tn2+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

We have already dealt with the case $|k|\ge1$|k|1. So, we focus on what happens when $-11<k<1

Notice that $k^n\rightarrow0$kn0 when $n$n is large and that $\frac{k^n-1}{k-1}\rightarrow\frac{1}{1-k}$kn1k111k. This means that $t_n\rightarrow\frac{b}{1-k}$tnb1k 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=b1k for large $n$n.

 

 

Example 2

Consider the recurrence relation $t_{n+1}=1.05t_n-2$tn+1=1.05tn2,  $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

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.

  1. Loading Graph...

    A

    Loading Graph...

    B

    Loading Graph...

    C

    Loading Graph...

    D

    Loading Graph...

    A

    Loading Graph...

    B

    Loading Graph...

    C

    Loading Graph...

    D

Question 2

Consider the recurrence relation $t_{n+1}=0.2t_n+8$tn+1=0.2tn+8 where $t_1=-4$t1=4.

  1. Does the recurrence relation define a sequence with a long-term steady-state solution?

    Yes

    A

    No

    B

    Yes

    A

    No

    B
  2. Which of the following statements about the steady-state is always true?

    At the steady-state, $t_{n+1}=t_n$tn+1=tn.

    A

    At the steady-state, the value of the terms reach a stationary point and then begin to decrease.

    B

    At the steady-state, the value of the terms is always zero.

    C

    At the steady-state, $n+1=n$n+1=n.

    D

    At the steady-state, $t_{n+1}=t_n$tn+1=tn.

    A

    At the steady-state, the value of the terms reach a stationary point and then begin to decrease.

    B

    At the steady-state, the value of the terms is always zero.

    C

    At the steady-state, $n+1=n$n+1=n.

    D
  3. Find the steady state solution by setting $t_{n+1}$tn+1$=$=$t_n=x$tn=x.

Question 3

The sequence defined by the recurrence relation $u_{n+1}=ku_n-16$un+1=kun16, where $u_1=3$u1=3, approaches a long-term steady-state value of $-40$40. Find the value of $k$k.

 

 

 

 

 

 

 

 

 

 

]

Outcomes

M7-3

Use arithmetic and geometric sequences and series

91258

Apply sequences and series in solving problems

What is Mathspace

About Mathspace