Learning Materials
Features
Discover
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\)
Millions of flashcards designed to help you ace your studies
Sign up for free
Achieve better grades quicker with Premium
Geld-zurück-Garantie, wenn du durch die Prüfung fällst
Review generated flashcards
Start learning or create your own AI flashcards
Team Recurrence Relation Teachers
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 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.
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:
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:
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}\]
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, 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.
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 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.
Sign up for free to gain access to all our flashcards.
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.
At StudySmarter, we have created a learning platform that serves millions of students. Meet the people who work hard to deliver fact based content as well as making sure it is verified.
Lily Hulatt is a Digital Content Specialist with over three years of experience in content strategy and curriculum design. She gained her PhD in English Literature from Durham University in 2022, taught in Durham University’s English Studies Department, and has contributed to a number of publications. Lily specialises in English Literature, English Language, History, and Philosophy.
Get to know Lily
Gabriel Freitas is an AI Engineer with a solid experience in software development, machine learning algorithms, and generative AI, including large language models’ (LLMs) applications. Graduated in Electrical Engineering at the University of São Paulo, he is currently pursuing an MSc in Computer Engineering at the University of Campinas, specializing in machine learning topics. Gabriel has a strong background in software engineering and has worked on projects involving computer vision, embedded AI, and LLM applications.
Get to know Gabriel
Explanations 
Flashcards 
StudySmarter AI 
Notes 
Study Plans 
Study Sets 
Exams 
Find a job 
Student Deals 
Magazine 
Mobile App