View source for Examples and counterexamples in mathematics/Infinite sequences

{{Wikipedia-inline|Sequence}}
296280 more-or-less notable sequences are collected on [http://oeis.org/ The On-Line Encyclopedia of Integer Sequences]. See also [https://mathigon.org/world/Sequences mathigon], [https://www.mathsisfun.com/algebra/sequences-series.html mathsisfun] etc.

==A sequence of equal members==
(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==
(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 <math>(a_1,a_2,a_3,\dots)</math> one may consider its odd subsequence <math>(a_1,a_3,a_5,\dots)</math> and even subsequence <math>(a_2,a_4,a_6,\dots).</math>

==All integers in a sequence==
(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
:<math>\begin{cases} -(n-1)/2 &\text{for odd } n,\\ n/2 &\text{for even } n.\end{cases}</math>
Just for fun, these two formulas may be combined,
:<math>\frac{1+(-1)^n(2n-1)}4,</math>
but this is not required. Two (and more) formulas are a legitimate way to define a sequence. More generally, any two sequences <math>(a_1,a_2,\dots)</math> and <math>(b_1,b_2,\dots)</math> may be interspersed into a single sequence <math>(c_1,c_2,\dots)=(a_1,b_1,a_2,b_2,\dots);</math> here
:<math>c_n = \begin{cases} a_{(n+1)/2} &\text{for odd } n,\\ b_{n/2} &\text{for even } n.\end{cases}</math>
The odd subsequence <math>(c_1,c_3,c_5,\dots)</math> of the new sequence <math>(c_1,c_2,\dots)</math> is equal to the first sequence <math>(a_1,a_2,\dots);</math> similarly, the even subsequence <math>(c_2,c_4,c_6,\dots)</math> equals <math>(b_1,b_2,\dots).</math>

==A sequence containing every natural number infinitely many times==
(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 <math>a_n,</math> we have <math>a_{2n}=a_n+1.</math>

The ''n''-th member is equal to the number ''q'' such that <math>\frac n{2^{q-1}}</math> is an odd integer. Thus, <math>\frac n{2^{q-1}}=2p-1</math> for some integer ''p''. Using this ''p'' instead of ''q'' we get another sequence containing every natural number infinitely many times:<br>
(1,1,2,1,3,2,4,1,5,3,6,2,7,4,...)<br>
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 <math>b_n,</math> we have <math>b_{2n}=b_n.</math>

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

==All positive rationals in a sequence==
<math>\textstyle\Big(1,\frac12,2,\frac13,3,1,4,\frac14,5,\frac32,6,\frac23,\dots\Big)</math>

The ''n''-th member is equal to <math>\frac p q</math> for positive integers ''p'', ''q'' such that <math>n=(2p-1)\cdot 2^{q-1}.</math> That is, <math>a_{(2p-1)\cdot 2^{q-1}}=\frac p q.</math> Thus,
<math>\textstyle a_1=a_{1\cdot2^0}=a_{(2\cdot1-1)\cdot 2^{1-1}}=\frac11=1;</math>
<math>\textstyle a_2=a_{1\cdot2^1}=a_{(2\cdot1-1)\cdot 2^{2-1}}=\frac12;</math>
<math>\textstyle a_3=a_{3\cdot2^0}=a_{(2\cdot2-1)\cdot 2^{1-1}}=\frac21=2;</math>
<math>\textstyle a_4=a_{1\cdot2^2}=a_{(2\cdot1-1)\cdot 2^{3-1}}=\frac13;</math>
<math>\textstyle a_5=a_{5\cdot2^0}=a_{(2\cdot3-1)\cdot 2^{1-1}}=\frac31=3;</math>
<math>\textstyle a_6=a_{3\cdot2^1}=a_{(2\cdot2-1)\cdot 2^{2-1}}=\frac22=1;</math>
and so on. Every positive rational number <math>\frac p q</math> appears in this sequence as ''n''-th member <math>a_n</math> for <math>n=(2p-1)\cdot 2^{q-1}.</math>

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

And moreover, <math>\frac p q</math> appears infinitely many times, not only for <math>n=(2p-1)\cdot 2^{q-1},</math> but also for <math>n=(4p-1)\cdot 2^{2q-1},</math> <math>n=(6p-1)\cdot 2^{3q-1}</math> 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 <math>f(q-1,p-1)+1=(2p-1)\cdot 2^{q-1}</math> for integer <math>p,q>0,</math> that is, <math>f(x,y)=(2y+1)\cdot 2^x -1</math> for integer <math>x,y\ge0,</math> is an example of the so-called pairing function.
{{Wikipedia-inline|Pairing function}}

==Factorials==
{{Wikipedia-inline|Factorial}}
(1,2,6,24,120,720,...)

The ''n''-th member is equal ''n'' times the (''n''-1)-th member: <math>a_n=na_{n-1}</math> for all <math>n>1.</math> This is a so-called recurrence relation: each further member is defined as a function of its number and the preceding member.
{{Wikipedia-inline|Recurrence relation}}
And the first member is equal to one: <math>a_1=1.</math>
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 <math>n!\,.</math> For instance, <math>5! = 1\cdot2\cdot3\cdot4\cdot5 = 120.</math>

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 <math>\textstyle n! \sim \sqrt{2 \pi n} \, n^n e^{-n}.</math>
Its relative error <math>\textstyle \big| 1 - \frac{\sqrt{2 \pi n} \, n^n e^{-n}}{n!} \big|</math> tends to zero (as ''n'' tends to infinity), but the absolute error <math>|n!-\sqrt{2 \pi n} \, n^n e^{-n}|</math> tends to infinity.
{{Wikipedia-inline|Stirling's approximation}}

==Fibonacci numbers==
{{Wikipedia-inline|Fibonacci number}}
(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: <math>a_n=a_{n-1}+a_{n-2}</math> for all <math>n>2</math> (a recurrence relation, again). And the first two members are equal to one: <math>a_1=a_2=1.</math> Thus, <math>a_3=a_2+a_1=1+1=2;</math> <math>a_4=a_3+a_2=2+1=3;</math>  <math>a_5=a_4+a_3=3+2=5;</math> and so on.

In the 17th century Johannes Kepler observed that ratios of consecutive Fibonacci numbers <math>\textstyle \big( \frac11, \frac21, \frac32, \frac53, \dots \big)</math> converge to a limit: <math>\tfrac{a_{n+1}}{a_n} \to \varphi</math> (as <math>n\to\infty</math>) for some number <math>\varphi.</math> If so, then necessarily <math>\tfrac{a_{n+2}}{a_{n+1}} \to \varphi,</math> therefore <math>\tfrac{a_{n+1}+a_n}{a_{n+1}} \to \varphi,</math> that is, <math>1+\tfrac{a_n}{a_{n+1}} \to \varphi;</math> taking into account that <math>\tfrac{a_n}{a_{n+1}} \to \tfrac1\varphi</math> we get <math>1+\tfrac1\varphi = \varphi,</math> that is, <math>\varphi+1=\varphi^2;</math> a quadratic equation on <math>\varphi.</math> It has two roots, <math>(1\pm\sqrt5)/2,</math> one greater than 1, another smaller than 1. Clearly, the limit <math>\varphi</math> cannot be smaller than 1 (since <math>\tfrac{a_{n+1}}{a_n}</math> cannot); thus, this limit (if exists) must be <math>\varphi=(1+\sqrt5)/2.</math> This number is the famous "golden ratio" treated already by Euclid about 2300 years ago.
{{Wikipedia-inline|Golden ratio}}
We wonder about the error of the approximate equality <math>\tfrac{a_{n+1}}{a_n} \approx \varphi</math> (for large ''n''), that is, <math>a_{n+1} \approx \varphi a_n.</math> The absolute error being <math>|a_{n+1}-\varphi a_n|,</math> we investigate the difference <math>a_{n+1}-\varphi a_n;</math> how does it change with ''n''? Is <math>a_{n+2}-\varphi a_{n+1}</math> greater or smaller (in absolute value) than <math>a_{n+1}-\varphi a_n?</math>

Using the recurrence relation and the property of <math>\varphi</math> we get <math>a_{n+2}-\varphi a_{n+1} = a_{n+1}+a_n-\varphi a_{n+1} = (1-\varphi)a_{n+1}+a_n = -\frac1\varphi a_{n+1}+a_n = -\frac1\varphi (a_{n+1}-\varphi a_n),</math> which shows that the investigated difference changes the sign and decreases in the absolute value. By induction, <math>a_{n+1}-\varphi a_n = \big(-\tfrac1\varphi\big)^{n-1} (a_2-\varphi a_1)</math> for all ''n''. Introducing <math>\psi=-\tfrac1\varphi,</math> noting that <math>\psi=1-\varphi</math> and recalling that <math>a_1=a_2=1</math> we get <math>a_{n+1}-\varphi a_n = \psi^n,</math> which shows that the absolute error is decreasing and converges to 0 (since <math>-1<\psi<0</math>).
Existence of the limit follows: <math>\tfrac{a_{n+1}}{a_n} = \varphi+\tfrac{a_{n+1}-\varphi a_n}{a_n} \to \varphi.</math> 

Interestingly, the property <math>1+\tfrac1\varphi = \varphi</math> of <math>\varphi</math> leads to a similar property <math>1+\tfrac1\psi = \psi</math> of <math>\psi,</math> as follows: <math>1+\tfrac1\psi = 1-\varphi = -\tfrac1\varphi = \psi.</math> Thus, <math>\psi</math> is nothing but the other root of the quadratic equation: <math>\psi=(1-\sqrt5)/2.</math>

The proof of the equality <math>a_{n+1}-\varphi a_n = \big(-\tfrac1\varphi\big)^{n-1} (a_2-\varphi a_1)</math> given above does not use any other property of <math>\varphi,</math> and therefore it holds for <math>\psi</math> as well: <math>a_{n+1}-\psi a_n = \big(-\tfrac1\psi\big)^{n-1} (a_2-\psi a_1),</math> that is (as before) <math>a_{n+1}-\psi a_n = \varphi^n.</math>

Having explicit formulas for <math>a_{n+1}-\varphi a_n = \psi^n</math> and <math>a_{n+1}-\psi a_n = \varphi^n</math> it is easy to get an explicit formula for <math>a_n.</math> We just subtract the first formula from the second and get <math>(\varphi-\psi)a_n=\varphi^n-\psi^n,</math> that is, the wonderful formula
: <math>a_n = \frac{(1+\sqrt5)^n-(1-\sqrt5)^n}{2^n \sqrt5}.</math>
It follows that <math>a_n</math> is the closest integer to <math>\varphi^n/\sqrt5.</math>

==The decimal digits of the number <math>\pi</math>==
{{Wikipedia-inline|Pi#Irrationality and normality}}
(3,1,4,1,5,9,2,6,5,...)<br>
By definition, ''n''-th member of this sequence is equal to <math>\lfloor 10 \cdot \{ 10^{n-2}\pi \} \rfloor;</math> here <math>\lfloor x \rfloor</math> is the integral part of ''x'', and <math>\{x\}=x-\lfloor x \rfloor</math> is the fractional part of ''x''. Thus,<br>
the first member is <math>\lfloor 10 \cdot \{ 10^{-1}\pi \} \rfloor = \lfloor 10 \cdot \{ 0.3141\dots \} \rfloor = \lfloor 10 \cdot 0.3141\dots \rfloor = \lfloor 3.141\dots \rfloor = 3;</math><br>
the second member is <math>\lfloor 10 \cdot \{ 10^0\pi \} \rfloor = \lfloor 10 \cdot \{ 3.141\dots \} \rfloor = \lfloor 10 \cdot 0.141\dots \rfloor = \lfloor 1.41\dots \rfloor = 1;</math><br>
the third member is <math>\lfloor 10 \cdot \{ 10^1\pi \} \rfloor = \lfloor 10 \cdot \{ 31.41\dots \} \rfloor = \lfloor 10 \cdot 0.41\dots \rfloor = \lfloor 4.1\dots \rfloor = 4;</math> and so on.

In order to calculate <math>\pi</math> one may use the formula
<math>\textstyle \pi = 3 + \frac{4}{2\cdot3\cdot4} - \frac{4}{4\cdot5\cdot6} + \frac{4}{6\cdot7\cdot8} - \frac{4}{8\cdot9\cdot10} + \dots.</math> Trillions (that is, millions of millions) of decimal digits of <math>\pi</math> 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 <math>\lfloor 10 \cdot \{ 10^1\pi \} \rfloor = 4</math> is a mathematical theorem, as well as the equality <math>\lfloor 10 \cdot \{ 10^{41}\pi \} \rfloor = 9</math>, and the same can be said about <math>\lfloor 10 \cdot \{ 10^{n-2}\pi \} \rfloor</math> 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 [https://blogs.sas.com/content/iml/2015/03/12/digits-of-pi.html Wicklin], [http://www2.lbl.gov/Science-Articles/Archive/pi-random.html Preuss], [https://mathoverflow.net/questions/26942/is-pi-a-good-random-number-generator 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..." (''[[w:Stan Wagon|Stan Wagon]]'', [http://pi314.at/math/normal.html Is Pi normal?])

{{BookCat}}