Episode (math)
In mathematics, a sequence or sequence is a list ( family ) of finitely or infinitely many consecutively numbered objects (e.g. numbers). The same object can appear several times in a sequence. The object with the number , one also says here with the index , is called the -th member or -th component of the sequence. Finite and infinite sequences can be found in all areas of mathematics. Analysis is primarily concerned with infinite sequences whose terms are numbers .
If the number of terms is a finite sequence, one speaks of a sequence of length , of a- termed sequence or of a - tuple . The sequence without terms, whose index area is empty, is called an empty sequence, 0-element sequence or 0-tuple.
Examples
- 5-tuples of whole numbers
- 4-tuples of trigonometric functions
- Sequence of the prime numbers
- Infinite sequence of sets
- General infinite sequence whose terms are continuously indexed. Zero is selected here as the start of indexing.
Notation
In general, one writes for a finite sequence , therefore , and for infinite sequences , therefore . This stands for any term in a sequence; the round brackets summarize these in a sequence, then the index range is displayed (this can be omitted if it is implicitly clear). Instead of round brackets, pointed ones are sometimes used (ie ); Semicolons can be used instead of commas if there is a risk of confusion with the decimal separator.
The difference to the set of sequence members or is that it depends on the order of the sequence members and that several sequence members can have the same value.
- Example: The sequence (0, 1, 0, 2, 0, 4, 0, 8, ...) has the image set (or underlying set) {0, 1, 2, 4, 8, ...}. The sequence (1, 0, 2, 0, 0, 4, 0, 0, 0, 0, 8, ...) has the same amount of images. The value 0 occurs several times in both sequences.
Formal definition
Formally defined, an infinite sequence is a mapping ,
which assigns a sequence member from the target set to each index from the set of natural numbers used as the index set . However, the choice of the initial index is ultimately arbitrary. In school math and most common use cases, the set of real numbers is . However, for example, sequences of sets and sequences of functions are also considered.
For a finite sequence ( tuple ) with terms, the index is defined from a finite set, usually either from the set or from the set . The notation is occasionally used for such index sets .
Applications
Infinite sequences can converge towards a limit . The theory of limit values of infinite sequences is an important basis of analysis , because it is the basis for the calculation of limit values of functions , the definition of the derivative (differential quotient as limit value of a sequence of difference quotients) and the Riemannian concept of integral . Important sequences are obtained as coefficients of Taylor series of analytical functions . Some elementary functions lead to special sequences, such as the tangent function on Bernoulli's numbers or the hyperbolic secant on Euler's numbers . The method of complete induction is a useful tool for proving the convergence of a sequence .
A series is a special sequence of numbers, the -th member of which results from the sum of the first members of another number sequence. For example, the series (1, 3, 6, 10, 15, ...) results from the sequence (1, 2, 3, 4, 5, ...). Series are used in many areas of mathematics. See the article series (mathematics) .
Law of formation of a sequence
There are several ways to specify a sequence:
- Name of all sequence members (only possible for finite sequences)
- Function equation
- line
- Recursion
- algorithm
A finite sequence can be given by naming all the members of the sequence. This is not possible with an infinite sequence, instead you have to communicate the formation law to the sequence in another form.
Sequences, the formation of which can be communicated as a functional rule or recursion, are sometimes called regular sequences.
Specification of initial terms
The task set in some intelligence tests of continuing a sequence whose first terms are given is problematic from a mathematical point of view. No matter how many initial members, the further course of a sequence is not clearly determined. There are only more or less plausible sequels.
- Examples:
- The given is 0, 1, 2, 3. The most plausible is the continuation 4, 5, 6, ..., ie the sequence of all natural numbers. However, the continuation 0, 1, 2, 3, 0, ... is also possible, namely as the periodic sequence of the smallest positive remainders of the natural numbers modulo 4. In a computer, whole numbers are often 32 bits in two's complement , i.e. as the absolute smallest residues modulo 2 ^{32} shown. When gradually increasing a register, one then runs through the sequence of numbers 0, 1, 2, 3,…, 2147483647, −2147483648, −2147483647,…, −1 and continue periodically.
- For the number sequence 3, 1, 4, 1, 5, a plausible continuation is 1, 6, 1, 7, ... Others would recognize the decimal representation of the circle number and suggest the continuation 9, 2, 6, ....
The online encyclopedia of number sequences (OEIS) contains tens of thousands of mathematically relevant sequences. You can search for a given partial sequence in it .
Specification of a functional rule
For many, but by no means all consequences, one can use the functional rule
given as a closed equation.
In the following examples we use indices from the set :
- The sequence of the natural numbers 0, 1, 2, 3, ... This example is special because the values of the sequence member and index match. The operating rule is simple
- The sequence of the odd numbers 1, 3, 5, 7, ... has the functional rule
- The sequence of powers of two 1, 2, 4, 8, ...
Related tasks
The problem of determining the initial terms for a given functional rule can be easily solved. Successively taking the values , , etc., puts each one in the function rule and calculated in this way, the followers , , etc. The purpose of this bill is to make a first impression of the course of a series. But be careful: a sequence can take a completely different course for really large indices than was to be expected after the first ten or one hundred terms. Example: the sequence that increases monotonically, but then decreases again, as can be checked by inserting higher powers of ten.
The reverse task of determining a function rule for given initial terms is, however, much more difficult. Strictly speaking, there can be no unambiguous solution, because the beginning of each episode can be continued in different ways, as described above. In practice, this task will be provided only for sequences whose members , , and so in a reasonably foreseeable manner by the Index depend. The following properties can be checked in detail:
- Is the sequence alternating? If so, you can get the correct sign from a factor in the function specification. Example: 0, −1, 2, −3, 4, ... has the rule .
- Are the sequential terms fractions? If so, construct functional rules for numerator and denominator independently of one another. Example: 1/1, 2/2, 3/4, 4/8, ... has the rule .
- Do the terms of the sequence increase (or decrease, with ) by constant differences ? If so, you have an arithmetic sequence . Example: 1, 3, 5, 7, ... has the rule .
- Do the differences between successive members satisfy a simpler law of formation than the successive members themselves? If so, the sequence can be viewed as a series (see below). Example: For 1, 3, 6, 10, 15, ... the differences are 1, 2, 3, 4, ...
- Are consecutive members of the series in a constant relationship to one another? If so, you have a geometric sequence . Example: The sequence 100; 80; 64; 51.2; ... decreases from link to link by a factor of 0.8; so the rule is .
The search for a function rule is made more difficult by the fact that the first one or two elements of the sequence (for the indices 0 and 1) often seem out of the ordinary. This is because a summand 0, a factor 1 or an exponent 0 or 1 are usually not written out, but are calculated immediately. In the abbreviated form 1, 1, 3/4, 1/2, ... the above-mentioned example 1/1, 2/2, 3/4, 4/8, ... the functional rule is difficult to see.
Specified as a series
A sequence whose -th term is the sum of the first terms of another sequence is called a series :
The expression written with the help of the summation sign is therefore an abbreviation for the expression . Different indices are to be used inside and outside the summation symbol. The fact that special and were chosen corresponds to a widespread convention, but is not mandatory.
In order to calculate as a specific numerical value, a specific numerical value must be specified for the index . In contrast to this, the index is not a value to be specified (externally), but is determined by the summation rule itself. Which is always given for the running index successively the values 0, 1, ..., have used and the sum of the associated , ..., are calculated.
Each sequence can be regarded as a series by creating an associated sequence from the differences in successive terms
constructed. Sequence and series cannot be clearly separated from one another. The economists' time series are actually consequences. Many explanatory models do not model absolute values, but their changes over time, which speaks in favor of understanding absolute values as members of a series.
The interpretation of a sequence as a series brings concrete benefit if the summation can be carried out for any number . Summation formulas are known, for example, for the arithmetic series and the geometric series .
The interpretation of an infinite sequence as a series makes it easier to determine whether and, if so, to which limit value the sequence converges. There are separate convergence criteria for infinite series . Conversely, from the convergence of a series (i.e., in the above notation, the convergence of ), one can always conclude that the sequence of the summands (in the above notation, the sequence ) converges to zero.
Specification of a recursion
The formation law of a sequence can also be specified recursively . For this purpose, one calls initial values (with ; mostly is or ) as well as a rule how a sequence term can be calculated from the preceding terms .
The best-known example of a sequence that can be described much more easily by a recursion rule than a function rule is the Fibonacci sequence 0, 1, 1, 2, 3, 5, 8, ... For it , the two initial terms are given and as well as the recursion rule
The explicit formula of Moivre and Binet for the terms of the sequence
is closely related to the golden ratio and the golden number . Note that they are all integers, since the odd powers of the subtract out.
For some sequences, conversely, a recursion rule can be derived from the function rule. For example, it follows for the geometric sequence from the functional rule
the recursion rule
The recursion
defines the sequence of rational numbers 2, 3/2, 17/12, ... which converges to.
Specification via an algorithm
For some sequences there is a clearly defined construction rule ( algorithm ), but no functional rule. The best known example is the sequence of the prime numbers 2, 3, 5, 7, 11, ... The ancient Greeks (possibly also Indians) knew how to calculate more and more terms of this sequence. One possibility is to use the sieve of Eratosthenes . However, there is no method of specifying the -th prime number for a given one without first determining the entire sequence from the first to the -th prime number. If you do not want to know the tenth or the hundredth, but the -th prime number, this increases the computational effort considerably.
The length of the shortest algorithm that produces a sequence is called its Kolmogorov complexity (sometimes this term is used in a narrow sense only for character sequences , i.e. finite sequences with finite target sets). It depends on the programming language used; however, according to the invariance theorem, the lengths for different languages only differ by a language-dependent additive constant.
Characterization of consequences
Like functions, number sequences can also be characterized by their gradient behavior and their image area.
monotony
term
One consequence is monotonically increasing, if it stays the same or increases from member to member, so if all of the following applies: . The result is strictly increasing when increases from term to term, so if all of the following applies: . The terms monotonically decreasing and strictly monotonically decreasing are defined analogously. However, the concept of monotony is not limited to real numbers: any ordered set allows a meaningful use of the term.
Evidence of monotony
If one suspects that a sequence is not monotonic (or strictly monotonic), one inserts a few indices into the function rule, calculates the associated sequence members and hopes to find a counterexample. Example: The sequence given by is not monotonic, because but .
If, for example, one suspects that a sequence is strictly monotonous, one writes , evaluates the function rule on both sides (by inserting in the rule instead of on the right ), and checks the resulting inequality by simplifying it through equivalence transformations . Example: Lists that is equivalent to or to the true statement .
Some functional rules can be broken down into a sum of constant terms and a known, simpler sequence, whose slope behavior is already known, by means of term transformations. Example: . If one knows that strictly monotonically falls, one can conclude that strictly monotonically increases. Because the term 2 is constant, it also increases strictly monotonically.
Narrow-mindedness
term
A sequence of real numbers is upwards limited if it is an upper bound has, so for all of the following applies: . The smallest upper bound of a sequence is also called its supremum . The terms below restricted, lower bound and infimum are defined analogously. A sequence that is bounded both upwards and downwards is called bounded.
Proof of restriction and determination of a limit
Proof of a counterexample is not possible here, because no matter how many examples you cannot ensure that there is not some very large or very small number that limits the sequence.
It must therefore be assumed that there is a limit. Now the appropriate inequality is applied, i.e. H. for an upper bound . On the left side of the inequality, the function rule is applied and then solved for. This gives (with a bit of luck) a result of the form or , where stands for a term that is dependent on. In the first case it has been found that the sequence is not bounded upwards (no matter how large it is, it is always possible to find an even larger one that violates the inequality). In the second case one tries to find one that is for . For this is always fulfilled and thus the proof has been successful that there is an upper bound.
Here, too, the verification can be made simpler if it is possible to break down the function rule into a sum of simpler terms.
Others
- A sequence whose values are alternately positive and negative is called alternating.
- A sequence whose terms all match is called a constant sequence.
- A sequence whose members all agree on a certain element is stationary sequence called
- A sequence that converges to 0 is called a null sequence .
- A sequence is called terminating if it is 0 from a certain term, i.e. H. a stationary zero sequence.
- A sequence that consists of repetitions of a finite partial sequence is called periodic. There is a period length , and for all of the following applies: . Partial sequence is to be understood here as a sequence of in the selected set.
An interesting task in calculus is to determine whether a sequence is converging and, if it does, to what limit . An infinite sequence that does not converge can nevertheless have accumulation points ( example: the sequence −1/2, 3/4, −5/6, 7/8, ... has accumulation points −1 and 1). In particular, every restricted sequence in the set of real numbers has at least one accumulation point ( Bolzano-Weierstrasse theorem ).
The aforementioned characterization of a sequence via its gradient behavior and its image area can help to determine whether and, if so, to which limit value it converges. The monotonicity criterion is particularly useful here , according to which a monotonically increasing, upwardly restricted sequence in the set of real numbers always converges, whereby its limit value corresponds to its supremum ( example: the sequence 0, 1/2, 2/3, 3 / 4, ... converges against their supremum 1). Accordingly, a monotonically falling, downwardly bounded sequence converges towards its infimum.
The characterization criteria monotony and limitation can be generalized for all sequences whose target set is ordered . Constant, stationary and periodic sequences can be defined for any target area, convergent sequences for any metric space as target area.
Important consequences
Most known number sequences can be looked up in the On-Line Encyclopedia of Integer Sequences (OEIS) by Neil Sloane . In February 2009 this database contained over 155,000 descriptions of number sequences.
Other number sequences often mentioned are, for example, the constant sequences with the function rule with a number that is fixed for all and the harmonic sequence defined by ( ) .
Arithmetic sequences and series
An arithmetic sequence is a sequence with a constant difference between successive terms. Examples are the frequently used sequences of the even numbers 2, 4, 6, ... with the function rule
and that of the odd numbers with the function rule
In general, the functional rule is
where denotes the constant difference.
Sequences that can be traced back to arithmetic sequences are called higher-order arithmetic sequences. So the sequence of triangular numbers is an arithmetic sequence of the 2nd order.
Episode: | |||||||||||
1. Difference sequence: | |||||||||||
2nd difference sequence: |
-Th order arithmetic sequences are precisely those sequences that can be described by a -th degree polynomial . This polynomial can be found using Lagrange interpolation from any number of terms in the sequence. The triangular numbers obey z. B. the Education Act .
Consequences based on the power function
A power sequence is a sequence for which the power function provides the terms ( generating function )
The sequence of the square numbers : 0, 1, 4, 9, ... has the function specification . The sequence of square numbers is also an arithmetic sequence of the 2nd order, as it can be understood as a series based on the sequence of odd numbers.
The sequence of the cube numbers 0, 1, 8, 27, ... has the rule
what you get for -th powers of natural numbers
can generalize, where any real number may be. With one gets the sequence of the square roots of the natural numbers,
- .
With negative exponents it should be noted that does not exist. For example, it is not possible to use and the function rule
- the following link to the index
to calculate. You can exclude the index 0, i.e. limit yourself to the index set . However, it is often more useful to leave the index set unchanged and instead use the function rule in
to change. Then the first terms of the sequence are 1, 1/2, 1/3, 1/4, ... In the same way, you can set up a function rule for any exponent :
Geometric sequences
Just as successive terms in an arithmetic sequence have a constant difference, so are terms in a geometric sequence
successive links in a constant ratio to each other . For example, with and results in the sequence of powers of two
For example, for the first ten terms the sequence 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024 (each term is twice the size of the previous one). This sequence is particularly important for the conversion of the in the computer science used binary numbers in decimal numbers (and vice versa). A geometric sequence with converges to zero, such as sequence 1; 0.1; 0.01; ... to :
If you get the trivial sequence 1, 1, 1,…; if you get out
the fundamental alternating sequence 1, −1, 1, −1, ...
An example of the everyday use of the geometric sequence is the equal tuning of the musical scale - the successive elements, here semitone steps, have a constant frequency relationship to one another.
Generalizations
In topology , a network is a generalization of a sequence.
As with functions , in addition to the sequences defined here with values in sets, you can also define sequences with values in a real class , for example sequences of sets or groups.
Sequence rooms
The sequence spaces can be formed from sequences , which are mainly used in functional analysis to construct examples.
literature
- Bourbaki : Eléments de mathématique. Theory of the ensemble II / III, Paris 1970
- Harro Heuser : Textbook of Analysis, Part 1, Teubner Verlag, Stuttgart
Individual evidence
- ↑ M. Li, PMB Vitányi: Kolmogorov Complexity and its Applications. In: Jan van Leeuwen (Ed.): Algorithms and Complexity (= Handbook of Theoretical Computer Science , Volume A ). Elsevier, 1990, pp. 187-254, here: p. 198.