Explicit and recursive description – Serlo

In order to define a sequence, one must fix a rule which assigns to each index an element. This rule of construction can be explicit, meaning it is directly stated which element is to be assigned to an index. However, there are also recursive rules, where for a given amount of elements it is stated how the next element has to look like. The recursive rule also fixes what all elements are (provided that some starting elements are given), although it may not be clear what the element assigned to a specific index looks like. In order to find this out, we need to translate the recursive into an explicit rule.

Explicit rules

An explicit rule provides for any given index $n$ the corresponding sequence element $a_{n}$. Explicit rules are hence usually written down as follows: For all $n\in \mathbb {N}$ there is

$a_{n}:={\text{ any term with }}n$

An example is the rule $a_{n}=n^{2}$ for all $n\in \mathbb {N}$ , which defines the sequence of square numbers. It can be written down as follows:

${\begin{aligned}(a_{n})_{n\in \mathbb {N} }=\left(n^{2}\right)_{n\in \mathbb {N} }&=(1^{2},\,{\color {OliveGreen}2^{2}},\,{\color {RedOrange}3^{2}},\,{\color {Fuchsia}4^{2}},\ldots )\\&=(1,\,{\color {OliveGreen}4},\,{\color {RedOrange}9},\,{\color {Fuchsia}16},\ldots )\end{aligned}}$

An explicit rule characterized by the fact that the individual sequence elements can be calculated without having to know other sequence elements. So if you want to calculate a certain sequence element, you only have to insert the desired index into the formula of the explicit rule and calculate the value given by the formula.

Question: What are the explicit formulas for the following sequences?

1. Sequence of cubic numbers
2. Sequence of odd numbers
3. Sequence of powers of $2$

Solution:

1. $a_{n}=n^{3}$ for all $n\in \mathbb {N}$
2. $b_{n}=2n-1$ for all $n\in \mathbb {N}$
3. $c_{n}=2^{n}$ for all $n\in \mathbb {N}$

Recursive rules

A recursive law is characterized by the fact that you have to know the preceding sequence elements in order to compute a new element. You can easily spot a recursive law when taking a look at the formula: it always contains preceding sequence elements. In general, a real-valued sequence $(a_{n})_{n\in \mathbb {N} }$ is recursively defined as follows:

${\begin{aligned}a_{1}&:=r{\text{ for some }}r\in \mathbb {R} \\[0.3em]a_{n+1}&:={\text{any term with }}n,a_{1},a_{2},\ldots ,a_{n}\ {\text{ for all }}n\in \mathbb {N} \end{aligned}}$

Since predecessors have to be known in order to get a new sequence element, one needs to state what the first element is / the first elements are. Otherwise, there is not element to begin with. The $a_{1}$ above is this first element. An example for a recursive law is:

${\begin{aligned}a_{1}&=-6\\a_{n+1}&=a_{n}+2\ {\text{ for all }}n\in \mathbb {N} \end{aligned}}$

The formula $a_{1}=-6$ defines the first sequence element and is called recursion base. The second formula is called recursion step and specifies haw new elements are computed from known predecessors. The first recursion steps applied read as follows:

${\begin{aligned}a_{1}&={\color {Blue}-6}\\a_{2}&=a_{1+1}=a_{1}+2={\color {Blue}-6}+2={\color {OliveGreen}-4}\\a_{3}&=a_{2+1}=a_{2}+2={\color {OliveGreen}-4}+2={\color {RedOrange}-2}\\a_{4}&=a_{3+1}=a_{3}+2={\color {RedOrange}-2}+2=0\\&\vdots \end{aligned}}$

Recursive laws for sequences are usually easier to find than explicit ones. However, with explicit rules given, the characteristics of a sequence are usually easier to read off than with recursively rules given. The calculation of sequence elements is also easier with explicit rules. Suppose we want to calculate the $1000$-th sequence element. With an explicit rule we can insert $1000$ directly into the given formula. With a recursive rule, we first have to calculate all unknown $998$ predecessors.

Question: Why does stating $a_{n+1}=a_{n}+2$ for all $n\in \mathbb {N}$ not uniquely define a sequence $(a_{n})_{n\in \mathbb {N} }$?

The recursion base is missing. Depending on what we plug in as the base case $a_{1}$, we get a lot of distinct sequences. For instance, with $a_{1}=-6$ we get the sequence $(a_{n})_{n\in \mathbb {N} }=(-6,\,-4,\,-2,\,0,\,2,\,\ldots )$ and for $a_{1}=10$ we get the sequence $(a_{n})_{n\in \mathbb {N} }=(10,\,12,\,14,\,16,\,18,\,\ldots )$. Both sequences satisfy $a_{n+1}=a_{n}+2$ for all $n\in \mathbb {N}$, but they are distinct. It is always important to state what the first element is in order to get a unique sequence out of a recursive rule.

Further remarks

If the rule how to get the sequence is particularly simple, sometimes only the first elements of a sequence are written down and the reader is left with the task of finding the rule (which is a trivial task). An example is:

$(a_{n})_{n\in \mathbb {N} }=(1,\,2,\,3,\,4,\,5,\,\ldots )$

But this definition of a sequence has the disadvantage that it is not unique. It is not clearly defined, how such a sequence has to be continued. Rather there is to assume, that every reader continues the sequence in the same way. Thus the above way to state a sequence is not a mathematically exact definition!

Furthermore there are construction rules, which can be given by an algorithm, but for which neither explicit nor recursive rules are known so far. An example is the sequence of prime numbers $2,\,3,\,5,\,7,\,11,\,\ldots$. It is possible to specify an algorithm, which calculates all prime numbers one after the other (for example with the help of the Sieve of Eratosthenes). But there is no explicit or recursive formation law of this sequence known.

Examples for constructing sequences

Example (Directly computing a term (explicit rule))

We define a sequence $(a_{n})_{n\in \mathbb {N} }$ in $\mathbb {N}$ by $a_{n}:=n^{3}+7$ for all $n\in \mathbb {N}$. Instead of $(a_{n})_{n\in \mathbb {N} }$ we write $(n^{3}+7)_{n\in \mathbb {N} }$.

Example (Computing an element based on its predecessors (recursive rule))

We define the sequence $(a_{n})_{n\in \mathbb {N} }$ in $\mathbb {R}$ by $a_{1}:=1$ and for all $n\geq 2$ we set $a_{n}:=(a_{n-1}+1)^{2}$. This is a recursion rule for the sequence $(a_{n})_{n\in \mathbb {N} }$.

If we were to compute the $n$-th element, we could first compute $a_{2}=(a_{1}+1)^{2}$ using $a_{1}$. Then we would compute $a_{3}$ based on $a_{2}$ by the formula $a_{3}=(a_{2}+1)^{2}$ . This is done step by step until we reach $n$ . So the above rule uniquely specifies a sequence.

Example (Sequence of prime numbers)

Let the sequence $(p_{n})_{n\in \mathbb {N} }=(2,3,5,7,11,\ldots )$ in $\mathbb {N}$ be defined as the ascending sequence of prime numbers, i.e. $p_{n}<p_{n+1}$ for all $n\in \mathbb {N}$ and $\{p_{n}:n\in \mathbb {N} \}$ has to be the set of primes.

This definition sounds very abstract and it is not clear how to calculate a certain sequence element. Nevertheless it defines a sequence unambiguously. This is shown by the following consideration:

The set of all prime numbers is a subset of natural numbers. So we can order the prime numbers by size and number them consecutively. Since there are infinitely many prime numbers, every natural number $n$ is uniquely associated with a prime number $p_{n}$, so that $p_{n}<p_{n+1}$ is valid for all $n\in \mathbb {N}$ and for every prime number $p$ there is a $n\in \mathbb {N}$ with $p=p_{n}$.

More complex examples

Example (Sequence of positive zeros of polynomials)

For all $n\in \mathbb {N}$ we define the function $f_{n}:\mathbb {R} \to \mathbb {R} ,x\mapsto x^{n}+4n^{2}x-10$. For all $n\in \mathbb {N}$ there is exactly one positive number $a_{n}$, so that $f_{n}(a_{n})=0$. We hence get a sequence $(a_{n})_{n\in \mathbb {N} }$.

Of course we have to show that $(a_{n})_{n\in \mathbb {N} }$ is well-defined. So we have to show that for all $n\in \mathbb {N}$ there is exactly one $a_{n}\in \mathbb {R} ^{+}$ with $f_{n}(a_{n})=0$. One can use the intermediate value theorem and a monotonicity rule for the derivation to show this.

Although we cannot give a function term which allows to compute $a_{n}$ directly, we have a well-defined sequence here. By the way, without noticing it, we have defined a sequence of functions $(f_{n})_{n\in \mathbb {N} }$.

Example (Sequence of prime numbers (algorithm))

For the sequence of prime numbers there are construction rules explicitly given by an algorithm. For example, with the help of the Sieve of Eratosthenes all prime numbers can be calculated successively. But there is no explicit or recursive construction rules of this sequence known so far.

Example (Conway-sequence (algorithm))

The Conway-sequence $(c_{n})_{n\in \mathbb {N} }$ is also given by an algorithm. A sequence element is calculated from the previous sequence element as follows:

You set $c_{1}:=1$. Each sequence element $c_{n}$ is a sequence of digits, which are not separated by a comma. For example $c_{5}=111221$.

Let $c_{n}$ be given for a $n\in \mathbb {N}$. Now we write down how often a digit occurs in $c_{n}$ before (read from left to right) another digit occurs. In the case $n=5$ we write: $3$ times a $1$, then $2$ times a $2$ and then $1$ times a $1$.

The sequence element $c_{n+1}$ consists of the sequence of the digits, which we just noted down from $c_{n}$. For $n=5$ this means $c_{6}=312211$.

See also the Wikipedia article about the Conway sequence (Look-and-say-sequence).

Finding rules

Sometimes one is faced with the task of finding construction rules for sequences for which the first elements have been given as examples. For instance, one could be interested in n explicit or recursive for the following sequence:

$1,{\color {OliveGreen}4},{\color {RedOrange}9},{\color {Fuchsia}16},{\color {Blue}25},\ldots$

Where does such a problem play a role? First of all, it is a popular problem type given by teachers to students when they introduce the sequence term in class. As a student you can improve your ability to recognize patterns and express them through mathematical functions.

But mathematicians also encounter such a problem. It is sometimes possible to calculate the first sequence elements of a sequence without knowing a rule. The mathematician then tries to guess a construction rule from these sequence elements. Then he can try to prove that this construction rule really describes the sequence he is looking for. Of course, this strategy is not always successful, but often leads to the goal.

Remarks

Construction rules like the one above, which only state the first sequence elements, are not unique. There is nowhere defined, how the reader has to continue the sequence. In this respect there is also no unique construction rule which solves the problem of continuing the started sequence. One can even show that there are always infinitely many construction rules, whose sequence has the given few elements as first sequence elements. Therefore one only looks for a possible construction rule. This rule should be as simple as possible. However, what a "simple" construction rule is, is again a subjective question where people agree about in many but not all cases.

In addition there is no standard way to solve the continuation problem. Here you have to puzzle (sometimes for a long time) and try a lot. In this respect, it is completely normal if you have problems finding a construction rule. The more experience you gain with sequences, the easier you will be able to solve such problems.

General procedure

Regardless of whether one wants to find a recursive or an explicit construction rule, the following approach is recommended:

1. Identify a pattern in the sequence. For this, one should first ask oneself what the next sequence elements should be. Once you have found them, you can then ask yourself why they have to be these sequence elements. The answer to this question is then the pattern of the sequence elements.
2. Express the found pattern by a mathematical function. If an explicit rule of construction is required, it must be a function of the form $n\mapsto a_{n}$, while in case of recursive rules of construction you are looking for an assignment rule of the form $(a_{n},n)\mapsto a_{n+1}$

Finding the explicit rule

The goal here is to find a construction rule of the form $n\mapsto a_{n}$, which assigns elements to indices. Let's try to find an explicit rule for the example:

$1,{\color {OliveGreen}4},{\color {RedOrange}9},{\color {Fuchsia}16},{\color {Blue}25},\ldots$

Which means, we need a function (as simple as possible) which satisfies:

${\begin{aligned}1&\mapsto 1\\2&\mapsto {\color {OliveGreen}4}\\3&\mapsto {\color {RedOrange}9}\\4&\mapsto {\color {Fuchsia}16}\\5&\mapsto {\color {Blue}25}\\&\vdots \end{aligned}}$

So the function must map the number $1$ to $1$, $2$ to $4$ and so on. You might have recognized already, that the elements are always the squares of their indices. So it is possible, that the next elements are the numbers $36$, $49$ and so on.

The mathematical expression for square numbers is $n^{2}$. Accordingly, the simplest explicit law is $a_{n}=n^{2}$.

Finding the recursuve rule

Recursive construction rules describe how a sequence element is computed from its predecessors. A recursive rule is often composed of the recursion base $a_{1}=\ldots$ and the recursion step $a_{n+1}=f(a_{n},n)$. So here you look for a function $f$, which allows to calculate $a_{n+1}$based on $a_{n}$ and $n$.

In our example, the base case of the recursion is already known: $a_{1}=1$. For the recursion step we now look for a function, which has the following mappings:

${\begin{array}{lll}n=2,&a_{1}=1&\mapsto a_{2}={\color {OliveGreen}4}\\n=3,&a_{2}={\color {OliveGreen}4}&\mapsto a_{3}={\color {RedOrange}9}\\n=4,&a_{3}={\color {RedOrange}9}&\mapsto a_{4}={\color {Fuchsia}16}\\n=5,&a_{4}={\color {Fuchsia}16}&\mapsto a_{5}={\color {Blue}25}\\&&\vdots \end{array}}$

It is not obvious what this mapping is. Maybe, on a second glance one can see that the difference $a_{n}-a_{n-1}$ is always an odd number:

$n$	$a_{n-1}$	$a_{n}$	$a_{n}-a_{n-1}$
2	1	4	3
3	4	9	5
4	9	16	7
5	16	25	9

For $n=2$ we have the odd number $3$, for $n=3$ the odd number $5$ and so on. These odd numbers can now be expressed by $n$. The difference is equal to $2n-1$. Thus we get $a_{n}-a_{n-1}=2n-1$, or equivalently:

$a_{n}=a_{n-1}+2n-1$

But now we want to have a recursion step of the form $a_{n+1}=...$. So let us use the number $m+1$ instead of $n$ in the above equation. Every natural number $n$ greater than or equal to 2 can be represented as the sum $m+1$, where $m$ is the predecessor of $n$ (this is just an index shift). We obtain:

${\begin{aligned}&&a_{n}&=a_{n-1}+2n-1\\&\implies &a_{m+1}&=a_{(m+1)-1}+2(m+1)-1\\&\implies &a_{m+1}&=a_{m}+2m+1\end{aligned}}$

Now we can again use $n$ instead of $m$. Finally, the recursive formation reads:

${\begin{aligned}a_{1}&=1\\a_{n+1}&=a_{n}+2n+1\end{aligned}}$