First Order Linear Recurrences Introduction

Recall that for many sequences, we can express them either by explicit equations, such as for example $a_n=n^2$an​=n2 (the sequence of square numbers) or as recurrence equations such as $a_{n+2}=a_n+a_{n+1}$an+2​=an​+an+1​, with $a_1=1,a_2=1$a1​=1,a2​=1 (the Fibonacci sequence). The essential difference in the two methods is that an explicit formula allows us to directly determine any term whatsoever, where as the recurrence formula develops sequentially new terms from previous ones. In our two examples, we can say immediately for the squaring sequence, that $a_{25}=625$a25​=625 , but to determine the $25$25th Fibonacci number using the recurrence formula in the second example would require knowledge of all previous terms.

To "solve" a recurrence equation really means to find its explicit equivalent, and there is a general theory of recurrence equations that has been developed over many years to effect that task. Some of the techniques are extremely difficult to understand. However, there is a class of recurrence equations called first order linear recurrence equations with constant coefficients that, for at least some of them, we can solve fairly easily. 

A first order recurrence equation uses a single previous term to determine other terms. For example the recurrence formula $a_{n+1}=a_n+3$an+1​=an​+3, with $a_1=4$a1​=4 is a first order equation where $a_2$a2​ is only determined from one previous term. Note that the first part of the formula implies that n is greater than or equal to 2. So, since $a_1=4$a1​=4 , then $a_2$a2​ is $4+3=7$4+3=7. Each new term is determined by a formula that involves only one previous term.

The rest of the phrase - "linear recurrence equations with constant coefficients" ...  is a little more difficult to explain, but it essentially means that the formula looks like $a_n=m\times a_{n-1}+b$an​=m×an−1​+b where $m$m is a non-zero constant and $b$b is any constant. So if you see recurrence formulae like $a_n=3a_{n-1}-1$an​=3an−1​−1 or $a_n=5-2a_{n-1}$an​=5−2an−1​, or even $a_n=\sqrt{2}a_{n-1}$an​=√2an−1​, you know you are dealing with a linear first order equation with constant coefficients.

On the other hand, a recurrence equation like $a_n=n\times a_{n-1}$an​=n×an−1​ which doesn't have a constant coefficient ($n$n changes for each term being calculated), or a recurrence equation like $a_n=4\left(a_{n-1}\right)^2$an​=4(an−1​)2 which shows the term  $a_{n-1}$an−1​ being squared, do not qualify.

Nevertheless, each one of the above recurrence equations can be developed term by term if we are given the value of $a_1$a1​. For example suppose  $a_n=4\left(a_{n-1}\right)^2$an​=4(an−1​)2 with $a_1=3$a1​=3. The sequence term by term becomes $3,36,5184,...$3,36,5184,... growing extremely rapidly. 

The reason we have defined the class of linear first order recurrence equations with constant coefficients is that all arithmetic and geometric sequences belong to this class.

Every geometric sequence can be written $a_n=r\times a_{n-1}$an​=r×an−1​ with $a_1$a1​ given as the first term and the constant coefficient $r$r becoming the common ratio. 

Also every arithmetic sequence can be written $a_n=a_{n-1}+d$an​=an−1​+d with $a_1=k$a1​=k. Here the constant coefficient $d$d is the common difference and the constant $k$k as the first term.

Consider these two examples.

The first is given as $a_n=a_{n-1}-7,a_1=100$an​=an−1​−7,a1​=100. Using the recurrence equation, the terms are worked out as $100,93,86,79,...$100,93,86,79,... which is clearly arithmetic with the first term $100$100 and the common difference $-7$−7. This means that the explicit formula can be written down as $a_n=100+\left(n-1\right)\times-7$an​=100+(n−1)×−7, and this can be simplified to $a_n=107-7n$an​=107−7n. 

The second is given $a_n=\left(\frac{1}{2}\right)a_{n-1},a_1=128$an​=(12​)an−1​,a1​=128. Using the recurrence formula, the first few terms are $128,64,32,16,...$128,64,32,16,... which is clearly geometric with the first term $128$128 and the common ratio $\left(\frac{1}{2}\right)$(12​). This means that the explicit formula can be written down as $a_n=128\times\left(\frac{1}{2}\right)^{n-1}$an​=128×(12​)n−1. 

Note that the recurrence equation $a_n=3a_{n-1}+1$an​=3an−1​+1 with $a_1=3$a1​=3 is neither geometric nor arithmetic, but nevertheless is still a linear first order equation with constant coefficients. Such an equation also has an explicit formula, but it is slightly more difficult to find. 

Worked Examples

QUESTION 1

QUESTION 2

QUESTION 3