Suggested languages for you:
|
|

## All-in-one learning app

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

# Recursion and Special Sequences

An essential technique in mathematics is finding patterns in sequences of numbers and data. For example, in stock markets, people look for patterns in the changing value of a stock to be able to predict if the value of a stock will change. Professionals use highly complex algorithms to find sequences and patterns to analyse this type of data. We will be accomplishing simpler but similar types of analysis of recursive sequences.

## Recursive Sequence Definition

A recursive sequence is one in which a term of the sequence is defined as a function of one or more of its previous terms. They are generated by solving a recursive formula.

A recursive sequence is a sequence in which the next term in a sequence can be expressed as a function of its previous terms.

Let's look into a simple example.

A common example of a recursive sequence is a geometric sequence. These are sequences that have a constant ratio between terms. Take the sequence of numbers $$1,\frac{1}{2}, \frac{1}{4},\frac{1}{8}, \frac{1}{16}, \ldots,$$ in this case it is easy to see that the $$n^{th}$$ term found by the $$(n-1)^{th}$$ power of $$\frac{1}{2}.$$

## Recursive Formulas

First, let's look at the notation. Take the sequence of integers $$1, 4, 9, 16, 25, 36, 49, \ldots$$. To label the terms in the sequence, textbooks use $$a_n$$ to denote the $$n^{th}$$ term of a sequence, so the fourth term of the sequence is denoted as $$a_4=16$$, and the first term of the sequence is $$a_1=1$$.

Note that either $$a_0$$ or $$a_1$$ are used to denote the first term of the sequence.

Suppose you have a sequence

$$\{a_n\}=\{a_1, a_2, a_3, \ldots , a_n\},$$

where $$a_n$$ is defined as the $$n^{th}$$ term in the sequence. Recursion is when the output of one iteration becomes the input of the next. A recursive formula gives us a formula for the next term in the sequence as a function of its previous terms. This form of sequence explicitly demands that you know what the previous term of the term you are trying to find is. By this, there are two fundamental pieces of information you need.

• The value(s) of the first term(s) of the sequence.
• The pattern rule that gives you the subsequent terms.

A recursive formula is a formula that uses a common rule to generate the next term in the sequence from its previous term(s).

Note that recursive formulas are also often referred to as recursive relations or recurrence relations.

## Recursive Sequences: Examples

We will now have a look at a couple of examples of recursive sequences and their formulas.

Find the first four terms of the sequence where $$a_1=3$$ and $$a_{n+1}=5a_{n}+7$$, $$n \geq 1$$.

Solution:

The recursive formula for this example is $$a_{n+1}=5a_{n}+7$$, where $$a_1$$ is the first term in the sequence and $$a_n$$ is the $$n^{th}$$ term.

Using the initial value $$a_1=3$$,

\begin{align} a_{2}&=5a_{1}+7=5\cdot3+7 \\ &=22 \\ a_3&=5a_{2}+7=5\cdot22+7 \\ &=117 \\ a_{4}&=5a_{3}+7=5\cdot117+7 \\ &=592. \end{align}

Therefore, the first four terms in the sequence are $$3, 22, 117, 592$$.

Find a recursive equation for the sequence $$\{2, 4, 16, 256, 65536, \ldots\}$$.

Solution:

By inspection, you can see that the term in the sequence is the square of the previous term.

Therefore, the recursive formula is given by:

$$a_n=(a_{n-1})^2 \text{ with } a_1=2.$$

## Iteration

Iteration is defined as when the same procedure is repeated many times and is the process of composing a function with itself repeatedly. Recursion is when the output of an iteration is used as the input for the next iteration.

Iteration is the process of composing a function with itself repeatedly.

Let $$f(x)$$ be a function, then the iterates of this function are:

$$f(x), f(f(x)), f(f(f(x))), f(f(f(f(x)))), \ldots$$

Starting with an initial value, you can use iteration to recursively generate a sequence.

Use iteration to find the first three iterates of the function $$f(x)=4x^2-x+3$$ for the initial value $$x_1=\frac{1}{2}$$.

Solution:

\begin{align} x_2&=f(x_1) \text{ iterate the function} \\ &=f\left(\frac{1}{2}\right) \text{ using initial value given in question} \\ &=4\left(\frac{1}{2}\right)^2-\frac{1}{2}+3 \\ &=\frac{7}{2} \\ x_3&=f(x_2) \text{ iterate the function} \\ &=f\left(\frac{7}{2}\right) \\ &=4\left(\frac{7}{2}\right)^2-\frac{7}{2}+3 \\ &=\frac{97}{2}. \end{align}.

Therefore, the first three iterates are $$\frac{1}{2}, \frac{7}{2}, \frac{97}{2}.$$

Iteration is also useful for modelling real-life situations.

If the rate of inflation is $$18 \%$$, the cost of an item in future years can be found by iterating the function $$c(x) = 1.18x$$. Find the cost of a $$500$$ laptop in four years if the rate of inflation remains constant.

Solution:

We have an initial value which we will denote as $$x_0=500$$,

\begin{align} x_1&=f(x_0) \text{ iterate the function} \\ &=f(500) \text{ using initial value given in question} \\ &=1.18(500) \\ &=590 \\ x_2&=f(x_1) \text{ iterate the function} \\ &=f(590) \\ &=1.18(590) \\ &=696.2 \\ x_3&=f(x_2) \text{ iterate the function} \\ &=f(696.2) \\ &=1.18(696.2) \\ &=821.516 \\ x_4&=f(x_3) \text{ iterate the function} \\ &=f(821.516) \\ &=1.18(821.516) \\ &=969.38888. \end{align}

Therefore, $$x_4=969.39$$.

So the cost of a $$500$$ laptop after four years is $$969.39$$.

## Special Sequences

Special sequences are sequences that have a unique pattern. Let's look at how to generate and spot them.

### Special Sequences: Examples

There are many examples of special sequences. Let's take a close look at some well-known examples.

#### Fibonacci

The Fibonacci sequence, named after a 13th-century century Italian mathematician, is a sequence in which each term is the sum of the two previous terms. The sequence is given by the following recursion equation,

$$F_n=F_{n-1}+F_{n-2}.$$

Setting $$F_0=0$$ and $$F_1=1$$, we have:

\begin{align} 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 \text{ etc.} \end{align}

This gives us the sequence:

$$\{0,1,1,2,3,5,8,13,21,34,55,89, \ldots \}.$$

The Fibonacci sequence is demonstrated in numerous patterns occurring in nature. For example, the petals of many plants are usually arranged in several clockwise and anti-clockwise spirals, and often the number of spirals in one direction and the other is given as consecutive Fibonacci numbers.

#### Square Numbers

The square numbers form a sequence with a formula given by $$S_n=n^2$$:

\begin{align} S_0&=0^2=0 \\ S_1&=1^2=1 \\ S_2&=2^2=4 \\ S_3&=3^2=9 \\ S_4&=4^2=16 \text{ etc.} \end{align}

#### Triangle Numbers

The number of dots in each of the triangles in the above diagram represents the triangle numbers. Each triangle is made by increasing the number of dots in the base by one and then building an equilateral triangle.

The triangular numbers can be generated by the formula $$T_n=\sum_{k=0}^{n} k=0+1+2+\cdots+n=\frac{n(n+1)}{2}$$, for example, the first $$6$$ terms of the sequence are given by:

\begin{align} T_0&=0 \\ T_1&=0+1=\frac{1(1+1)}{2}=1 \\ T_2&=\sum_{k=0}^{2} k=0+1+2=\frac{2(2+1)}{2}=3 \\ T_3&=\sum_{k=0}^{3} k=0+ 1+2+3=\frac{3(3+1)}{2}=6 \\ T_4&=\sum_{k=0}^{4} k=0+1+2+3+4=\frac{4(4+1)}{2}=10 \\ T_5&=\sum_{k=0}^{5} k=0+1+2+3+4+5=\frac{5(5+1)}{2}=15. \end{align}

The recursive formula for this sequence of numbers is given as $$T_n=T_{n-1}+n$$, so with a starting value of $$T_0=0$$ we can yield the same result:

\begin{align} T_0&=0 \\ T_1&=T_{0}+1=0+1=1 \\ T_2&=T_{1}+2=1+2=3 \\ T_3&=T_{2}+3=3+3=6 \\ T_4&=T_{3}+4=6+4=10 \\ T_5&=T_{4}+5=10+5=15. \end{align}

An interesting feature of triangle numbers is that if you add consecutive triangle numbers, you will get a sequence of square numbers as follows:

\begin{align} T_0+T_1&=0+1=1\times1=1^2=S_1 \\ T_1+T_2&=1+3=4=2\times2=2^2=S_2 \\ T_2+T_3&=3+6=9=3\times3=3^2=S_3 \\ T_3+T_4&=6+10=16=4\times4=4^2=S_4 \\ T_4+T_5&=10+15=25=5\times5=5^2=S_5 \text{ etc.} \end{align}

#### Cube Numbers

The general formula of cube numbers is $$C_n=n^3$$. The first five terms of the sequence of cube numbers a given by:

\begin{align} C_0&=0^3=0 \\ C_1&=1^3=1 \\ C_2&=2^3=8 \\ C_3&=3^3=27 \\ C_4&=4^3=64. \end{align}

The sum of the first $$n$$ cube numbers is equal to the square of their sum:

$$C_1+C_2+\ldots+C_n=1^3+2^3+\ldots+n^3=(1+2+\ldots+n)^2.$$

Alternatively, you can use the following formula for the sum of the first $$n$$ cube numbers

$$\sum_{k=1}^{n} k^3= \frac{n^2(n+1)^2}{4},$$

Which has been derived from the triangle numbers, $$T_n=\sum_{k=1}^{n} k=\frac{n(n+1)}{2}$$. The sum of the first $$n$$ cube numbers is equal to the square of the $$n^{th}$$ triangular number, as follows:

$$\sum_{k=1}^{n} k^3=\left(\frac{n(n+1)}{2}\right)^2=\frac{n^2(n+1)^2}{4}.$$

## Arithmetic Sequences and Recursive Formulas

Another important type of special sequence is an arithmetic sequence. These are sequences where there is a common difference that remains constant between any two consecutive terms. You will need to be able to identify arithmetic sequences by looking at the difference between terms and find the corresponding recursive formula.

An arithmetic sequence is one where there is a constant difference between terms.

Let's look at an example:

$$\{4, 10, 16, 22, 28, \ldots\}.$$

This sequence is an example of an arithmetic sequence since there is a common difference of $$6$$ between each consecutive terms.

Suppose you are given the $$n^{th}$$ term and common difference of an arithmetic sequence, you can then find the next term in the sequence, $$a_{n+1}$$ using the recursive formula for an arithmetic sequence.

The recursive formula for an arithmetic sequence is given by $$a_{n+1}=a_n+d.$$ Where $$a_{n+1}$$ is the $$(n+1)^{th}$$ term of the sequence, $$a_n$$ is the $$n^{th}$$ term and $$d$$ is the common difference.

## Examples of Arithmetic Sequences and Recursive Formulas

Now, let's explore some examples.

Take the sequence of numbers $$\{18, 15, 12, 9, \ldots\}.$$ This is an example of an arithmetic sequence.

You can find the common difference by subtracting the $$n^{th}$$ term of the sequence by the previous term, as follows:

$$a_{n}-a_{n-1}=d.$$

In this case,

\begin{align} a_2-a_1&=15-18=-3 \\ a_3-a_2&=12-15=-3 \\ a_4-a_3&=9-12=-3. \end{align}

So the common difference is $$d=-3$$.

Hence, using the formula above, the recursive formula for this arithmetic sequence is,

$$a_n=a_{n-1}-3.$$

Find the recursive formula of the arithmetic sequence $$\{0.6, 0.45, 0.3, 0.15, 0, \ldots\}$$.

Solution:

First you need to find the common difference.

\begin{align} a_{n}-a_{n-1}&=d \\ a_2-a_1&=0.45-0.6 \\ d&=-0.15. \end{align}

So the common difference is $$d=-0.15$$.

Using the arithmetic sequence recursive formula given above, you have that

\begin{align} a_n&=a_{n-1}+d \\ a_n&=a_{n-1}-0.15. \end{align}

Hence, the recursive formula for this arithmetic sequence is,

$$a_n=a_{n-1}-0.15.$$

## Recursion and Special Sequences - Key takeaways

• Recursive sequences are sequences where previous terms given, define the terms of the sequence.
• Two pieces of information are always needed for recursion; the first term of the sequence and the pattern rule that gives you the subsequent terms.
• Sequences that do not follow a simple and regular pattern like arithmetic sequences or geometric sequences are called special sequences.
• Examples of a special sequence are the Fibonacci sequence, triangle numbers, cube numbers, and square numbers.

There are two fundamental pieces of information you need

• The first term of the sequence.
•  The pattern rule that gives you the subsequent terms.

How the general recursive formula is

an+1 = an + d

Special sequences on the other hand do not follow a regular pattern like arithmetic and geometric sequences.

an=2an-1+3 is a recursive formula because each term, an, refers back to the previous term, an-1.

There are countless sequences that do not follow a simple and regular pattern like the arithmetic sequences or geometric sequences.

Special sequences are a string of numbers that have a unique pattern to them.

A recursive sequence is one in which the next term of the sequence can be expressed as a function of its previous terms.

## Final Recursion and Special Sequences Quiz

Question

What are recursive sequences?

Recursive sequences are sequences where previous terms given define the terms of the sequence.

Show question

Question

Which of these is not required to know before one can solve recursive problems?

The 9th term of a sequence.

Show question

Question

What is the recursive formula?

A recursive formula is a formula that defines each term of a sequence using the preceding term.

Show question

Question

What are the two pieces of information one would need to solve a recursive problem?

• The first term of the sequence
• The pattern rule that gives you the subsequent terms.

Show question

Question

Find the next term of a sequence that has the first term of $$a_1=4$$ and $$n^{th}$$ term given by $$a_n=2a_{n-1}+3?$$

$a_2=11$

Show question

Question

Given $$a_1=2$$ and $$a_n=a_{n-1}\left(\frac{n+1}{n}\right)$$, find the first five terms of the sequence.

$$2, 3, 4, 5, 6$$.

Show question

Question

What is a special sequence?

Special sequences are sequences that have a unique pattern.

Show question

Question

True/False: The sequence $$1, -2, 4, -8, \ldots$$ is an arithmetic sequence?

False.

Show question

Question

What is the $$4^{th}$$ square number?

$$4^2=16$$

Show question

Question

What is iteration?

Iteration is the process of composing a function with itself repeatedly.

Show question

Question

Find a square number that is also a triangular number.

36 is a square number ($$6^2=36)$$ as well as a triangular number (36 is the 8th triangular number).

There are are infinitely many more examples.

Show question

Question

What is an arithmetic sequence?

An arithmetic sequence is one where there is a constant difference between terms.

Show question

Question

What are two types of Special sequences?

Fibonacci sequence and Cube numbers

Show question

Question

Find the next term of a sequence that has the first term of $$a_1=3$$ and the $$n^{th}$$ term given by the formula $$a_n=a_{n-1}+2.$$

$a_2=5$

Show question

Question

If $$a_1=10$$ and $$a_n=2a_{n-1}+1$$, find the next $$3$$ terms of the sequence.

• $$a_2=2a_1+1=21$$
• $$a_3=2a_2+1=43$$
• $$a_4=2a_3+1=87$$

Show question

More about Recursion and Special Sequences
60%

of the users don't pass the Recursion and Special Sequences quiz! Will you pass the quiz?

Start Quiz

## 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.