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 \rightarrow \infty\) so we could see the behaviour of \(u_n\). I actually wrote a Shiny app to show the behaviour. The graphs led to a question about the relationship between \(u_n\) as \(n\) increases and exponential functions.

If we start we a recurrence relation of the form

\[u_{n+1} = au_n + b\]

with some value of \(u_0\) then we can very quickly find out what \(u_1\), \(u_2\) etc. are. If we look at the first few terms we get

\[\begin{align} u_1 &= au_0 + b \\ u_2 &= au_1 + b = a(au_0 + b) + b = a^2u_0 + ab + b \\ u_3 &= au_2 + b = a(a^2u_0 + ab + b) + b = a^3u_0 + a^2b + ab + b \\ u_4 &= au_3 + b = a(a^3u_0 + a^2b + ab + b) \\ &= a^4u_0 + a^3b + a^2b + ab + b. \end{align}\]

This pattern continues so we end up with

\[u_n = a^nu_0 + a^{n-1}b + a^{n-2}b + \cdots + a^2b + ab + b\]

or rather

\[u_n = a^nu_0 + b\left(\sum_{k = 0}^{n-1}a^k\right)\]

where \(\sum\) means sum all the terms so

\[\sum_{k = 0}^{n-1}a^k = a^{n-1} + a^{n-2} + \cdots + a^2 + a + 1.\]

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

\[\sum_{k = 0}^{n-1}a^k = \frac{a^n - 1}{a - 1}\]

and so putting all of this together gives

\[u_n = a^nu_0 + b\left(\sum_{k = 0}^{n-1}a^k\right) = a^nu_0 + \frac{b\left(a^n - 1\right)}{a - 1}.\]

We can choose \(u_0 = 0\) to simplify things and we end up with

\[u_n = \frac{b\left(a^n - 1\right)}{a - 1}.\]

So we now have an expression for \(u_n\) that involves the exponential \(a^n\) we were expecting. Remember that \(a\) and \(b\) are just numbers. If we take an example recurrence relation

\[u_{n+1} = 4u_n + 6\]

then we will have

\[u_n = \frac{b\left(a^n - 1\right)}{a - 1} = \frac{6\left(4^n - 1\right)}{4 - 1} = 2\left(4^n - 1\right).\]

This expression we now have for \(u_n\) also lets us prove the limit for a recurrence relation but when do we have a limit? The crucial term is \(a^n\).

• If \(a > 1\) then \(a^n\) will tend to infinity and so will \(u_n\).

• If \(a = -1\) then \(a^n\) will be \(1\) if \(n\) is even and \(-1\) if \(n\) is odd. Therefore \(u_n\) will either be \(0\) (as \(u_0 = 0\)) or \(b\).

• If \(a < -1\) then \(a^n\) (and therefore \(u_n\)) 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

\[u_n = a^nu_0 + b\left(\sum_{k = 0}^{n-1}a^k\right) = 1 \times u_0 + b\left(\sum_{k = 0}^{n-1}1^k\right) = u_0 + bn\]

and this will tend to infinity as \(n\) does. So in none of these cases do we get a limit. Either \(u_n\) 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 \(a^n\) will get very small as \(n\) gets very big. After a certain point \(n\) will be so big that \(a^n\) might as well be zero. We can prove this formally but we’re not going to do it here. If we take \(a^n\) to be zero then we get

\[u_n = \frac{b\left(a^n - 1\right)}{a - 1} = \frac{b\left(0 - 1\right)}{a - 1} = \frac{-b}{a - 1}\]

and if we multiply top and bottom by \(-1\) we end up with

\[u_n = \frac{b}{1 - a}.\]