Explanations 
Exams 
Magazine 
A recurrence relation for a sequence is a formula for the next term in the sequence as a function of the previous terms. A famous example that you may have heard of is the recurrence relation for the Fibonacci sequence where each term is the sum of the two previous terms. Here are the first few terms of the Fibonacci sequence: \(0,1,1,2,3,5,8,\dots\)
The Meaning of Recurrence Relations
Recurrence relations give a formula for the common rule that governs a given sequence of numbers. They are recursive, meaning that the recurrence relation formula for the next term in the sequence is given as a function of it's previous terms. They allow us to simplify sequences making it easier to analyse its characteristics and patterns.
A recurrence relation is a formula for the next term in a sequence as a function of its previous terms.
An example of a recurrence relation is \(u_{n+1}=4u_n+5\). Where \(u_n\) is the \(n^{th}\) term in a sequence and the recurrence relation gives us a formula for working out the next term, \(u_{n+1}\).
Recurrence Relation Formula
Recurrence relation formulas can take many different forms. Commonly used notation uses \(u_{n}\) to denote the \(n^{th}\) term in a sequence and \(u_{n+1}\) to denote the following (or next) term in a sequence. The formula of a recurrence relation depends on the order, also referred to as the degree, of the recurrence relation.
Order/Degree of a Recurrence Relation
A recurrence relation of order \(k\) is a formula for the \(n^{th}+1\) term of the sequence as a function of the previous \(k\) terms of the sequence. Another way to put it is that the order \(k\) is the difference between the highest and lowest subscripts of the recurrence relation.
A recurrence relation of order/degree \(k\) is an equation which is in the form:
$$u_{n}=a_{1}u_{n-1}+a_{2}u_{n-2}+a_{3}u_{n-3}+...+a_{k}u_{n-k} + f(n).$$
Where \(a_1,...,a_k\) are constants and \(f(n)\) is a function in terms of \(n\).
A recurrence relation is non-homogenous if \(f(n)\) is a polynomial or of the form \(a\times b^{n}\).
If \(f(n)=0\) then the recurrence relation is homogenous.
What is the order of the recurrence relation \(u_{n+1}=u_{n}+5n\). Is it homogeneous or non-homogeneous?
Answer:
The formula for recurrence relations is \(u_{n}=a_{1}u_{n-1}+a_{2}u_{n-2}+a_{3}u_{n-3}+...+a_{k}u_{n-k} + f(n)\).
Comparing this with \(u_{n+1}=u_{n}+5n\) gives:
- \(k=1\) since the difference between \(n+1\), the highest subscript, and \(n\), the lowest subscript, is \(1\),
- \(a_1=1\) the coefficient of \(u_n\),
- \(f(n)=5n\).
Therefore, this is a non-homogenous first-order recurrence relation.
What is the order of the recurrence relation \(u_{n+1}=2u_{n}+3u_{n-1}\)? Is it homogeneous or non-homogeneous?
Answer:
The formula for recurrence relations is \(u_{n}=a_{1}u_{n-1}+a_{2}u_{n-2}+a_{3}u_{n-3}+...+a_{k}u_{n-k} + f(n)\).
Comparing this with \(u_{n+1}=2u_{n}+3u_{n-1}\) gives:
- \(k=2\) since the difference between \(n+1\), the highest subscript, and \(n-1\), the lowest subscript, is \(2\),
- \(u_1=2\) and \(u_2=3\) the coefficients of \(u_n\) and \(u_{n-1}\) respectively,
- \(f(n)=0\).
Therefore, this is a homogenous second-order recurrence relation.
When given a recurrence relation, to work out the terms in a sequence you will need initial conditions, sometimes called boundary conditions. You will need the same number of initial conditions as the order of a recurrence relation to be able to find the terms of the sequence, i.e. for a \(k^{th}\) order recurrence relation you will need \(k\) initial conditions to find the terms of the sequence. These initial conditions will normally be given as the first \(k\) terms in the sequence.
The formula for the Fibonacci sequence is a second-order recurrence relation given by:
$$F_{n}=F_{n-1}+F_{n-2}$$
Suppose we are given two initial conditions \(F_0=0\) and \(F_1=1\).
Now we can work out the terms of the sequence.
Here are the first few terms written out with the formula:
\[\begin{align} F_0&=0\\F_1&=1\\F_2&=F_1+F_0=1+0=1\\F_3&=F_2+F_1=1+1=2\\F_4&=F_3+F_2=2+1=3\\F_5&=F_4+F_3=3+2=5\\F_6&=F_5+F_4=5+3=8. \end{align}\]
Recurrence Relations: Examples
Let's look at some examples of sequences and find their recurrence relation formulas.
Can we find a recurrence relation for the following sequence of numbers?
$$3, 9, 21, 45, 93... $$
Solution:
The common notation used for sequences is given as:
\[\begin{align} u_1&=3\\u_2&=9\\u_3&=21\\u_4&=45\\u_5&=93. \end{align}\]
i.e. \(u_{n}\) is the \(n^{th}\) term of the sequence.
Note that some textbooks and questions start sequences with \(n=0\) so make sure to check before attempting a question.
Now, we can find a formula for working out a particular term in the sequence. First look at the differences between consecutive terms:
\[\begin{align} u_2-u_1 &=9-3=6\\u_3-u_2&=21-9=12\\u_4-u_3&=45-21=24\\u_5-u_4&=93-45=48. \end{align}\]
This sequence is growing by a factor of 2 each time. With this in mind, look again at the original sequence:
\[\begin{align} u_1&=3\\u_2&=9=2\cdot3+3\\u_3&=21=2\cdot9+3\\u_4&=45=2\cdot21+3\\u_5&=93=2\cdot45+3. \end{align}\]
Therefore, with initial value \(u_{1}=3\) the recurrence relation for this sequence is \(u_{n+1}=2u_{n}+3\).
Suppose you have a sequence \(u_1,u_2,u_3, ...\) defined by the recurrence relation \(u_{n+1}=u_n+2n+1\) with initial value \(u_1=1\).
Show that \(u_4=16\) and hence find an expression for \(u_n\) in terms \(n\).
Solution:
The best way to go about this question is to write out the first four terms of the sequence.
\[\begin{align} u_1&=1\\u_2&=u_1+2\cdot1+1=1+2+1=4\\u_3&=u_2+2\cdot2+1=4+4+1=9\\u_4&=u_3+2\cdot3+1=9+6+1=16. \end{align}\]
Hence \(u_4=16\).
From these values, we can also see that this is a sequence of square numbers. Therefore, an expression for \(u_n\) in terms \(n\) is \(u_n=n^{2}\).
Closed-Form of Recurrence Relations
Closed-form, or position-to-term, is the term we use to describe the formula for the \(n^{th}\) term in terms of \(n\). Either closed-form or position-to-term may be used in textbooks, either way is considered correct. These closed-form equations are useful if we want to find a particular term even when \(n\) is large.
The closed-form is a formula for the \(n^{th}\) term in the sequence in terms of \(n\).
