Examples and counterexamples in mathematics/Infinite sequences

From Wikibooks, open books for an open world
Jump to navigation Jump to search

296280 more-or-less notable sequences are collected on The On-Line Encyclopedia of Integer Sequences. See also mathigon, mathsisfun etc.

A sequence of equal members[edit]

(0,0,0,0,...)

Unlike a set, a sequence may contain nothing but zero and still be infinite. That is, all members (in other words, elements or terms) of a sequence may be equal to 0; or, say, to 71, if you prefer: (71,71,71,71,...).

The sequence of natural numbers[edit]

(1,2,3,...)

The n-th member is equal to n.

This sequence is strictly increasing (that is, each member is less than the next member).

The odd subsequence (1,3,5,...) contains all odd natural numbers; the even subsequence (2,4,6,...) contains all even natural numbers. More generally, for every sequence one may consider its odd subsequence and even subsequence

All integers in a sequence[edit]

(0,1,-1,2,-2,...)

Existence of such sequence shows that the set of all integers (including negative) is countable.

This sequence is non-monotone (that is, neither increasing nor decreasing). All integers cannot be contained in a monotone sequence, since an increasing sequence is bounded from below, and a decreasing sequence is bounded from above (think, why).

The n-th member is equal to

Just for fun, these two formulas may be combined,

but this is not required. Two (and more) formulas are a legitimate way to define a sequence. More generally, any two sequences and may be interspersed into a single sequence here

The odd subsequence of the new sequence is equal to the first sequence similarly, the even subsequence equals

A sequence containing every natural number infinitely many times[edit]

(1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,...)

The odd subsequence (1,1,1,...) contains only 1. The even subsequence (2,3,2,4,2,3,2,5,2,...) differs from the whole sequence only by 1 added to every member. Thus, the odd subsequence of the even subsequence contains only 2. And so on... That is, denoting n-th member by we have

The n-th member is equal to the number q such that is an odd integer. Thus, for some integer p. Using this p instead of q we get another sequence containing every natural number infinitely many times:
(1,1,2,1,3,2,4,1,5,3,6,2,7,4,...)
The odd subsequence is just (1,2,3,...). The even subsequence (1,1,2,1,3,2,4,...) is equal to the whole sequence. That is, denoting n-th member by we have

In contrast, a monotone sequence cannot contain both 1 and 2 infinitely many times (think, why).

All positive rationals in a sequence[edit]

The n-th member is equal to for positive integers p, q such that That is, Thus, and so on. Every positive rational number appears in this sequence as n-th member for

Existence of such sequence shows that the set of all positive rational numbers is countable.

And moreover, appears infinitely many times, not only for but also for and so on.

Every number is an accumulation point of this sequence (that is, every neighborhood of the given number contains infinitely many members of the sequence; equivalently, the given number is the limit of some subsequence). In contrast, a monotone sequence may have only one accumulation point, namely, the limit of the whole sequence (think, why).

The function f defined by for integer that is, for integer is an example of the so-called pairing function.

Factorials[edit]

(1,2,6,24,120,720,...)

The n-th member is equal n times the (n-1)-th member: for all This is a so-called recurrence relation: each further member is defined as a function of its number and the preceding member.

And the first member is equal to one: Thus, the n-th member is the product of all natural numbers from 1 to n; it is called the factorial of n and denoted by For instance,

Factorials are widely used. They appear in the binomial theorem, Taylor's theorem, most of well-known discrete probability distributions (binomial, negative binomial, multinomial, Poisson, hypergeometric) etc.

A wonderful approximation for large factorials is given by Stirling's formula Its relative error tends to zero (as n tends to infinity), but the absolute error tends to infinity.

Fibonacci numbers[edit]

(1,1,2,3,5,8,13,21,...)

The n-th member is equal the (n-1)-th member plus the (n-2)-th member: for all (a recurrence relation, again). And the first two members are equal to one: Thus, and so on.

In the 17th century Johannes Kepler observed that ratios of consecutive Fibonacci numbers converge to a limit: (as ) for some number If so, then necessarily therefore that is, taking into account that we get that is, a quadratic equation on It has two roots, one greater than 1, another smaller than 1. Clearly, the limit cannot be smaller than 1 (since cannot); thus, this limit (if exists) must be This number is the famous "golden ratio" treated already by Euclid about 2300 years ago.

We wonder about the error of the approximate equality (for large n), that is, The absolute error being we investigate the difference how does it change with n? Is greater or smaller (in absolute value) than

Using the recurrence relation and the property of we get which shows that the investigated difference changes the sign and decreases in the absolute value. By induction, for all n. Introducing noting that and recalling that we get which shows that the absolute error is decreasing and converges to 0 (since ). Existence of the limit follows:

Interestingly, the property of leads to a similar property of as follows: Thus, is nothing but the other root of the quadratic equation:

The proof of the equality given above does not use any other property of and therefore it holds for as well: that is (as before)

Having explicit formulas for and it is easy to get an explicit formula for We just subtract the first formula from the second and get that is, the wonderful formula

It follows that is the closest integer to

The decimal digits of the number [edit]

(3,1,4,1,5,9,2,6,5,...)
By definition, n-th member of this sequence is equal to here is the integral part of x, and is the fractional part of x. Thus,
the first member is
the second member is
the third member is and so on.

In order to calculate one may use the formula Trillions (that is, millions of millions) of decimal digits of are calculated using better formulas. They look as if they are random! On one hand, this is natural, since we do not know any reason for any regularity in this sequence. On the other hand, this is paradoxical, since in these digits there is not the slightest chance. The equality is a mathematical theorem, as well as the equality , and the same can be said about for every n. (See also Numerical calculations and rigorous mathematics.) Each of these (seemingly random) digits, being an eternal mathematical truth, could not be different. Тhis puzzling situation is vividly discussed, see Wicklin, Preuss, mathoverfow etc. "To put our ignorance in perspective, note that it is not even known that all digits appear infinitely often: perhaps Pi = 3.1415926.....01001000100001000001..." (Stan Wagon, Is Pi normal?)