Explanations 
Flashcards 
StudySmarter IA 
Notes 
Study Plans 
Study Sets 
Exams 
Magazine 
Find a job 
Mobile App 
Jump to a key chapter
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\).
An example of closed-form for a sequence is \(u_{n}=4n-12\).
Suppose you want to find the \(1000^{th}\) term of this sequence, then you can simply substitute \(n=1000\) into the equation and get:
$$u_{1000}=4(1000)-12=3988.$$
The closed form for the Fibonacci sequence is:
$$F_n=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2} \right)^{n}-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^{n}.$$
Find the recurrence relation and closed-form for the sequence: \(27, 9, 3, 1, \frac{1}{3},\dots\). Assume the initial value is denoted as \(u_0=27\).
Solution:
Firstly, we can see that the terms in the sequence are decreasing by a factor of 3 each time. You can see this by dividing each term by its previous term which gives us 3 each time:
\[\begin{align} \frac{u_0}{u_1}&=\frac{27}{9}=3\\ \frac{u_1}{u_2}&=\frac{9}{3}=3 \\ \frac{u_2}{u_3}&=\frac{3}{1}=3\\ \frac{u_3}{u_4}&=\frac{1}{\frac{1}{3}}=3. \end{align}\]
Assuming this factor is constant throughout the sequence, the recurrence relation for the sequence is given by:
$$u_{n+1}=3u_n$$
with initial value \(u_{0}=27\).
For the closed form of the sequence:
$$u_n=27\cdot \left(\frac{1}{3}\right)^{n}.$$
This sequence is also called a geometric sequence with a common ratio of 3.
Proving Closed Forms of Recurrence Relations
The technique used for proving the closed-form of recurrence relations is proof by induction. You may have come across this technique before but the proof is structured as follows:
Let \(P(n)\) be a mathematical statement such that \(n\) is a natural number. Then \(P(n)\) is true for values of \(n\) if the following are satisfied:
Step 1. \(n=1\) is true, i.e. \(P(1)\) holds.
Step 2. Given/Assuming that \(n=k\) is true, then \(n=k+1\), i.e. if \(P(k)\) holds then \(P(k+1)\) holds.
Step 3: Conclusion: Since the statement was true for \(n=1\) and assuming true for \(n=k\), the statement is true for \(n=k+1\). Therefore by the principal of mathematical induction, the statement holds for all natural numbers \(n=1,2,3,...\).
For more information on using proof by induction "see Proof by Induction".
Prove by induction that \(u_{n}=5^{n-1}+1\) is the closed form of the sequence defined by \(u_{n+1}=5u_{n}-4\) with initial value \(u_{1}=2\), for all natural numbers n.
Solution:
For this particular example \(P(n)=u_n=5^{n-1}+1\).
Step 1: Let \(n=1\),
$$u_{1}=5^{0}+1=1.$$
Therefore the statement holds for \(n=1\).
Step 2: Assume the statement is true for \(n=k\), i.e. assume \(u_{k}=5^{k-1}+1\).
Show that \(u_{n}=5^{n-1}+1\) is true for \(n=k+1\):
\[\begin{align} u_{k+1}&=5u_{k}-4\\ &=5(5^{k-1}+1)-4\\ &=5^{1+k-1}+5-4\\ &=5^{k}+1.\end{align}\]
Therefore the statement holds for \(n=k+1\).
Step 3: Conclusion: Since the statement was true for \(n=1\) and assuming true for \(n=k\), the statement is true for \(n=k+1\). Therefore by the principal of mathematical induction, the statement holds for all natural numbers \(n=1,2,3,...\).
Solving Recurrence Relations
Solving recurrence relations involves finding the closed-form of a recurrence relation given certain initial values or boundary conditions. There are different methods for solving recurrence relations. Sometimes they are simple enough to solve by inspection (as we have seen above) but for more complex first-order and second-order recurrence relations, the best methods to use are iteration or the Characteristic Root Technique. If you would like to go through these techniques in depth, have a look at the following articles on Solving First-Order Recurrence Relations and Solving Second-Order Recurrence Relations.
Recurrence Relations - Key takeaways
- A recurrence relation gives a formula for the next term in a sequence as a function of its previous terms.
- The closed-form of a recurrence relation is a formula for the \(n^{th}\) term in the sequence in terms of \(n\).
- 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.
- Mathematical induction may be used to prove results relating to recurrence relations.
Learn with 1 Recurrence Relation flashcards in the free StudySmarter app
Already have an account? Log in
Frequently Asked Questions about Recurrence Relation
What is meant by recurrence relation?
A recurrence relation for a sequence is a formula for the next term in a sequence as a function of it's previous terms.
What is the formula of recurrence relation?
Depending on the order of a recurrence relation, the formula for a recurrence relation of order k is a formula for the (n+1)th term of the sequence as a function of the previous k terms of the sequence.
How to solve recurrence relations?
There are many methods to solving recurrence relations. For simple recurrence relations we can use inspection and for more complex recurrence relations we use iteration or the Characteristic Root Technique.
Why do we use recurrence relations?
We use recurrence relations to simplify a sequence of numbers using a common rule that governs them.
What is an example of a recurrence relation?
The Fibonacci sequence has the recurrence relation
Fn = Fn-1 + Fn-2.
About StudySmarter
StudySmarter is a globally recognized educational technology company, offering a holistic learning platform designed for students of all ages and educational levels. Our platform provides learning support for a wide range of subjects, including STEM, Social Sciences, and Languages and also helps students to successfully master various tests and exams worldwide, such as GCSE, A Level, SAT, ACT, Abitur, and more. We offer an extensive library of learning materials, including interactive flashcards, comprehensive textbook solutions, and detailed explanations. The cutting-edge technology and tools we provide help students create their own learning materials. StudySmarter’s content is not only expert-verified but also regularly updated to ensure accuracy and relevance.
Learn more