Math for Non-Geeks/Explicit and recursive description

{{#invoke:Math for Non-Geeks/Seite|oben}}

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

Template:Math

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:

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.

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:

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:

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:

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.

Math for Non-Geeks/Template:Frage

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:

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,\dots$. 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.

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:

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:

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

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=\dots$ 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:

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:

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:

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

{{#invoke:Math for Non-Geeks/Seite|unten}}