In my Higher Maths class we have just finished the recurrence relations topic and as part of that we investigated the limit of recurrence relations. We also plotted some example as n→∞ so we could see the behaviour of un. I actually wrote a Shiny app to show the behaviour. The graphs led to a question about the relationship between un as n increases and exponential functions.

If we start we a recurrence relation of the form

un+1=aun+b

with some value of u0 then we can very quickly find out what u1, u2 etc. are. If we look at the first few terms we get

u1=au0+bu2=au1+b=a(au0+b)+b=a2u0+ab+bu3=au2+b=a(a2u0+ab+b)+b=a3u0+a2b+ab+bu4=au3+b=a(a3u0+a2b+ab+b)=a4u0+a3b+a2b+ab+b.

This pattern continues so we end up with

un=anu0+an−1b+an−2b+⋯+a2b+ab+b

or rather

un=anu0+b(n−1∑k=0ak)

where ∑ means sum all the terms so

n−1∑k=0ak=an−1+an−2+⋯+a2+a+1.

It can be shown (and I’ve included a quick proof at the bottom of this post) that provided a≠1

n−1∑k=0ak=an−1a−1

and so putting all of this together gives

un=anu0+b(n−1∑k=0ak)=anu0+b(an−1)a−1.

We can choose u0=0 to simplify things and we end up with

un=b(an−1)a−1.

So we now have an expression for un that involves the exponential an we were expecting. Remember that a and b are just numbers. If we take an example recurrence relation

un+1=4un+6

then we will have

un=b(an−1)a−1=6(4n−1)4−1=2(4n−1).

This expression we now have for un also lets us prove the limit for a recurrence relation but when do we have a limit? The crucial term is an.

• If a>1 then an will tend to infinity and so will un.

• If a=−1 then an will be 1 if n is even and −1 if n is odd. Therefore un will either be 0 (as u0=0) or b.

• If a<−1 then an (and therefore un) will tend to postive infinity if n is even (and getting bigger) but negative infinity if n is odd (and getting bigger).

• If a=1 then we have to go back to our equation

un=anu0+b(n−1∑k=0ak)=1×u0+b(n−1∑k=01k)=u0+bn

and this will tend to infinity as n does. So in none of these cases do we get a limit. Either un will tend to infinity or flip-flop between positive and negative values, depending on whether n is even or odd.

Finally we can consider that if −1<a<1 then an will get very small as n gets very big. After a certain point n will be so big that an might as well be zero. We can prove this formally but we’re not going to do it here. If we take an to be zero then we get

un=b(an−1)a−1=b(0−1)a−1=−ba−1

and if we multiply top and bottom by −1 we end up with

un=b1−a.