Select your language

Suggested languages for you:
Log In Start studying!
StudySmarter - The all-in-one study app.
4.8 • +11k Ratings
More than 3 Million Downloads
Free
|
|

All-in-one learning app

  • Flashcards
  • NotesNotes
  • ExplanationsExplanations
  • Study Planner
  • Textbook solutions
Start studying

Recurrence Relation

Recurrence Relation

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\).

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.

Frequently Asked Questions about 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.

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.

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.

We use recurrence relations to simplify a sequence of numbers using a common rule that governs them.

The Fibonacci sequence has the recurrence relation

F= Fn-1 + Fn-2.

Final Recurrence Relation Quiz

Question

What is a recurrence relation?

Show answer

Answer

A recurrence relation for a sequence is a formula for the next term in the sequence as a function of the previous terms. 

Show question

Question

What is the closed-form of a recurrence relation?

Show answer

Answer

The closed-form of a recurrence relation is a formula for the nth term  in the sequence in terms of n.

Show question

Question

What is the order of the recurrence relation un+1 = 5un + 6n. Is it homogeneous or non-homogeneous?

Show answer

Answer

It is a first-order recurrence relation and it is non-homogenous.

Show question

Question

What is the method used for proving the closed-form of a recurrence relation?

Show answer

Answer

Proof by Induction

Show question

Question

What two methods can be used to solve first-order recurrence relations?

Show answer

Answer

The Characteristic Method and iteration

Show question

Question

What is the method used to solve second-order recurrence relations?

Show answer

Answer

The Characteristic Technique

Show question

Question

How many initial values/boundary conditions do you need to solve a second-order recurrence relation?

Show answer

Answer

2

Show question

Question

Which method is used to prove closed forms of recurrence relations?

Show answer

Answer

Mathematical induction

Show question

Question

What is a recurrence relation?

Show answer

Answer

A recurrence relation gives a formula for the next term in a sequence as a function of its previous terms.

Show question

Question

What is the closed-form of a recurrence relation?

Show answer

Answer

The closed-form is a formula for the nth term in the sequence in terms of n.

Show question

Question

What are the four steps of proving a mathematical statement by induction?

Show answer

Answer

1. Basis Step

2. Inductive Hypothesis

3. Inductive Step

4. Conclusion

Show question

Question

How many steps are there in proving a mathematical statement by induction?

Show answer

Answer

4

Show question

Question

Assume that the mathematical statement P(n) is true for n = k. 


Which step of proof by induction is this?


Show answer

Answer

Inductive Hypothesis

Show question

Question

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 principle of mathematical induction, the statement P(n) holds for all natural numbers n = 1, 2, 3, ...


Which step of proof by induction is this?

Show answer

Answer

Conclusion

Show question

Question

True or false, we prove closed-forms of recurrence relations using proof by contradiction?

Show answer

Answer

True

Show question

Question

What is the definition of the closed form of a first-order recurrence relation?

Show answer

Answer

The closed-form of a first-order recurrence relation is a formula for the nth term in the sequence in terms of n.

Show question

More about Recurrence Relation
60%

of the users don't pass the Recurrence Relation quiz! Will you pass the quiz?

Start Quiz

Discover the right content for your subjects

No need to cheat if you have everything you need to succeed! Packed into one app!

Study Plan

Be perfectly prepared on time with an individual plan.

Quizzes

Test your knowledge with gamified quizzes.

Flashcards

Create and find flashcards in record time.

Notes

Create beautiful notes faster than ever before.

Study Sets

Have all your study materials in one place.

Documents

Upload unlimited documents and save them online.

Study Analytics

Identify your study strength and weaknesses.

Weekly Goals

Set individual study goals and earn points reaching them.

Smart Reminders

Stop procrastinating with our study reminders.

Rewards

Earn points, unlock badges and level up while studying.

Magic Marker

Create flashcards in notes completely automatically.

Smart Formatting

Create the most beautiful study materials using our templates.

Sign up to highlight and take notes. It’s 100% free.