Recurrence Relations

πŸ†Practice series

What are Recurrence Relations?

If there is a relationship between the elements of a sequence, the recurrence relation would be the rule that connects them. It is possible to formulate the recurrence relation and use it to find the value of each of the elements of the set according to the position it occupies.

For example

Recurrence Relations

Ways to Find Recurrence Relations

There are several ways to find recurrence relations. One is to observe the sequence of elements and how they change. Another way is to write down parameters in a table.

A rule can be formulated using addition, subtraction, multiplication or divisionβ€”or several of these operations together.

Let's look at an example:

Consider the sequence of elements: 3,7,11,15,19 3,7,11,15,19 .

If we look closely at the numbers, we can see that there is a certain rule of formation between them: to get from one number to the next, we need to add 4 4 each time.

The first element is 3 3 . If we add 4 4 to this number, we will get the second element, which is 7 7 . If we add 4 4 to this number again, we will arrive at the third element (11 11 ), and so on.

Therefore the rule in this case is: +4 +4 .


Start practice

Test yourself on series!

einstein

12 ☐ 10 ☐ 8 7 6 5 4 3 2 1

Which numbers are missing from the sequence so that the sequence has a term-to-term rule?

Practice more now

Examples of Different Formation Patterns

Example No. 1

Observe the following numerical sets and determine if there is a recurrence relation (rule). If so, specify what it is.

A. 1,2,3,4,5,6 1,2,3,4,5,6

B. 9,7,3,8,5,0 9,7,3,8,5,0

C. 9,11,13,15,17 9,11,13,15,17

D. 1,100,98,85,64 1,100,98,85,64

E. 10,9,8,7,6 10,9,8,7,6

Solution:

A. If we look at this sequence, we see that each subsequent number is greater than the one that precedes it by 1. 1. . Therefore, the recurrence relation is +1. +1. .

B. For this sequence, we can see that there is no relationship between its elements. Therefore, there is no recurrence relation here.

C. Looking at this sequence, we can see that each subsequent number is greater than the one preceding it by 2. 2. . Therefore, the recurrence relation is +2 +2 .

D. In this sequence, we see that there is no relationship between its elements. Therefore, there is no recurrence relation.

E. If we look at this sequence, we will see that each subsequent number is smaller than the one preceding it by 1. 1. . Therefore, the rule is βˆ’1 -1 .

Response:

A. There is a recurrence relation: +1 +1 .

B. No recurrence relation.

C. There is a rule: +2 +2 .

D. No rule.

E. There is a recurrence relation. It is: βˆ’1 -1 .


Example No. 2

Look at the number groups below and determine if there is a recurrence relation. If there is, specify what it is and work out the next two terms:

2,βˆ’4,8,βˆ’16,32,βˆ’64 2,-4,8,-16,32,-64

Solution:

Looking at the sequence, we can see that there is a mixture of positive and negative numbers and it may seem that there is no rule. However, upon closer inspection, we should see that even though there is a combination of positives and negatives, there is still a recurrence relation to the sequence.

If we first ignore the signs, we will see that each subsequent number is equal to twice the previous one. Now, if we return the signs we should discover that each subsequence is created by multiplying the number that precedes it by βˆ’2 -2 .

2Γ—βˆ’2=βˆ’4 2\times-2=-4

βˆ’4Γ—βˆ’2=8 -4\times-2=8

8Γ—βˆ’2=βˆ’16 8\times-2=-16

βˆ’16Γ—βˆ’2=32 -16\times-2=32

32Γ—βˆ’2=βˆ’64 32\times-2=-64

Therefore, the rule for this sequence is Γ—(βˆ’2) \times(-2) .

Now let's move on to the second part of the exercise and find the next two elements of the sequence.

We will do this by performing exactly the same operation we have just shown:

βˆ’64Γ—βˆ’2=128 -64\times-2=128

128Γ—βˆ’2=βˆ’256 128\times-2=-256

Answer:

There is indeed regularity and it is: Γ—(βˆ’2) \times(-2) .

The next two elements of the sequence are: 128 128 and βˆ’256 -256 .


If you are interested in this article, you may also be interested in the following articles:

You will find a variety of useful mathematics articles in Tutorela site!


Join Over 30,000 Students Excelling in Math!
Endless Practice, Expert Guidance - Elevate Your Math Skills Today
Test your knowledge

Exercises with Different Sequences

Exercise 1

Is there a valid rule for the following sequence of numbers?

30,26,22,18 30,26,22,18

Solution:

Yes, since to get to the next number we must subtract 4 4 from the previous number.

30βˆ’4=26 30-4=26

26βˆ’4=22 26-4=22

22βˆ’4=18 22-4=18

Answer:

Yes, subtract (4) (4) .


Exercise 2

Describe the recurrence relation using the variable n n .

21,24,27,30 21,24,27,30

Solution:

To find a formula that describes the recurrence relation we use the formula:

an=a1+d(nβˆ’1) a_n = a_1+d\left(n-1\right)

Where a1 a_1 corresponds to the first element of the sequence and d d to the difference between any two consecutive numbers.

We place the corresponding data in the formula:

an=21+3(nβˆ’1) a_n=21+3\left(n-1\right)

We simplify:

an=21+3nβˆ’3 a_n = 21+3n-3

an=3n+18 a_n = 3n+18

Answer:

an=3n+18 a_n = 3n+18


Do you know what the answer is?

Exercise 3

In the classroom there are 10 10 numbered seats.

Complete the seating progression:

20,18 20,18

16,14 16,14

__ , __

8,6 8,6

2,4 2,4

Solution:

Each time we subtract 4 4 from the two sides, therefore:

14βˆ’4=10 14-4=10

16βˆ’4=12 16-4=12

Answer:

12,10 12,10


Exercise 4

Describe the recurrence relation using the variable n n .

50,75,100 50,75,100

Solution:

We substitute the data according to the formula:

an=a1+d(nβˆ’1) a_n=a1+d\left(n-1\right)

an=50+25(nβˆ’1) a_n = 50+25(n-1)

an=25n+50βˆ’25 a_n = 25n+50-25

an=25n+25 a_n = 25n+25

Answer:

an=25n+25 a_n = 25n+25


Check your understanding

Exercise 5

A handful of mathematicians decided in advance on a recurrence relation. They found people whose ages matched the rule and placed them in the following progression:

A. 9n+4βˆ’2nβˆ’2 9n+4-2n-2

B. x2+5nβˆ’x2+2nβˆ’2 x^2+5n-x^2+2n-2

C. 7nβˆ’2 7n-2

D. 9n+4βˆ’nβˆ’6βˆ’n 9n+4-n-6-n

Figure:

Exercise 5 three people

5+7=12 5+7=12

12+7=19 12+7=19

Is there a 7n 7n in the age equation? (The position increases by 1 1 , so the age increases by 7 7 )

Let's look at the first element:

5=7Γ—n+? 5=7\times n+\text{?}

We replace n=1 n=1 .

We move 7 7 to the corresponding section.

5βˆ’7=? 5-7=?

βˆ’2=? -2=?

Rule:

7nβˆ’2 7n-2

Answer:

B. x2+5nβˆ’x2+2nβˆ’2=7nβˆ’2 x^2+5n-x^2+2n-2=7n-2

C. 7nβˆ’2 7n-2

D. 9n+4βˆ’nβˆ’6βˆ’n=7nβˆ’2 9n+4-n-6-n=7n-2

Therefore we have 3 correct answers since they are all equal to 7nβˆ’2 7n-2 .


Review Questions

What is a recurrence relation in mathematics?

When we have a set of ordered numbers, we can say that there is a recurrence relation if there is a pattern or rule that connects these numbers.


Do you think you will be able to solve it?

How do you work out the recurrence relation of a sequence?

To find the recurrence relation we must analyze the set of numbers and try to use the operations of addition, subtraction, multiplication, or division (or a combination thereof) to describe the set.


How do you work out the recurrence relation of geometric figures?

Geometric figures can also have a recurrence relation. To work it out, you must create a numerical sequence that describes them.


Test your knowledge

Examples with solutions for Series

Exercise #1

12 ☐ 10 ☐ 8 7 6 5 4 3 2 1

Which numbers are missing from the sequence so that the sequence has a term-to-term rule?

Video Solution

Step-by-Step Solution

It is possible to see that there is a difference of one number between each number.

That is, 1 is added to each number and it will be the next number:

1+1=2 1+1=2

2+1=3 2+1=3

3+1=4 3+1=4

Etcetera. Therefore, the next numbers missing in the sequence will be:8+1=9 8+1=9

10+1=11 10+1=11

Answer

11 , 9

Exercise #2

Look at the following set of numbers and determine if there is any property, if so, what is it?

94,96,98,100,102,104 94,96,98,100,102,104

Video Solution

Step-by-Step Solution

One can observe that the difference between each number is 2.

That is, with each leap the next number increases by 2:

94+2=96 94+2=96

96+2=98 96+2=98

98+2=100 98+2=100

and so forth......

Answer

+2 +2

Exercise #3

The table shows the number of balls and the number of courts at the school:

246123BallsCourts

.

Complete:

Number of balls is _________ than the number of courts

Video Solution

Step-by-Step Solution

It is possible to see that if you multiply each number from the right column by 2, you get the number from the left column.

That is:1Γ—2=2 1\times2=2

2Γ—2=4 2\times2=4

3Γ—2=6 3\times2=6

Therefore, the number of balls is 2 times greater than the number of courts.

Answer

2 times greater

Exercise #4

The sequence below is structured according to a term-to-term rule.

What is the first element?

?+? \text{?}+\text{?}

2+4 2+4

3+7 3+7

4+10 4+10

5+13 5+13

Video Solution

Step-by-Step Solution

We start with the right column in the exercises.

Between each number there is a jump of +3:4+3=7 4+3=7

7+3=10 7+3=10

Etcetera.

Now we move to the left column of the exercises.

Between each number there is a jump of +1:

2+1=3 2+1=3

3+1=4 3+1=4

Now we can figure out which exercise is missing:

The left digit will be:2βˆ’1=1 2-1=1

The right digit will be:4βˆ’3=1 4-3=1

And the missing exercise is:1+1 1+1

Answer

1+1 1+1

Exercise #5

Below is a sequence represented by squares. How many squares will there be in the 8th element?

Video Solution

Step-by-Step Solution

It is apparent, that for each successive number, a square is added in length and one in width.

Hence, the rule using the variable n is:

a(n)=n2 a(n)=n^2

Therefore, the eighth term will be:

n2=8Γ—8=16 n^2=8\times8=16

Answer

64 64

Start practice