Pell number

In mathematics, the Pell numbers and companion Pell numbers (Pell-Lucas numbers) are both sequences of integers that have been known since ancient times. They are defined by a recurrence relation similar to that for the Fibonacci numbers, and grow exponentially, proportionally to powers of the silver ratio. Pell numbers arise in the approximation of the square root of 2, in the definition of square triangular numbers, in the construction of nearly-isosceles integer right triangles, and in certain combinatorial enumeration problems. [For instance, Sellers (2002) proves that the number of perfect matchings in the Cartesian product of a path graph and the graph "K"₄-"e" can be calculated as the product of a Pell number with the corresponding Fibonacci number.]

As with Pell's equation, the name of the Pell numbers stems from Leonhard Euler's mistaken attribution of the equation and the numbers derived from it to John Pell. The Pell-Lucas numbers are also named after Edouard Lucas, who studied sequences defined by recurrences of this type; the Pell and companion Pell numbers are Lucas sequences.

Pell numbers

The Pell numbers are defined by the recurrence relation:

In words, the sequence of Pell numbers starts with 0 and 1, and then each Pell number is the sum of twice the previous Pell number and the Pell number before that. The first few terms of the sequence are:num|0, 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378... OEIS|id=A000129.

The Pell numbers can also be expressed by the closed form formula:$P\_n=frac\{(1+sqrt2)^n-(1-sqrt2)^n\}\{2sqrt2\}.$For large values of "n", the $scriptstyle\; (1+sqrt\; 2)^n$ term dominates this expression, so the Pell numbers are approximately proportional to powers of the silver ratio $scriptstyle\; (1+sqrt\; 2)$, analogous to the growth rate of Fibonacci numbers as powers of the golden ratio.

A third definition is possible, from the matrix formula:

Many identities can be derived or proven from these definitions; for instance an identity analogous to Cassini's identity for Fibonacci numbers,:$P\_\{n+1\}P\_\{n-1\}-P\_n^2\; =\; (-1)^n,$is an immediate consequence of the matrix formula (found by considering determinants). [For the matrix formula and its consequences see Ercolano (1979) and Kilic and Tasci (2005). Additional identities for the Pell numbers are listed by Horadam (1971) and Bicknell (1975).]

Approximation to the square root of two

Pell numbers arise historically and most notably in the rational approximation to the square root of 2. If two large integers "x" and "y" form a solution to the Pell equation:$displaystyle\; x^2-2y^2=pm\; 1,$then their ratio $frac\{x\}\{y\}$ provides a close approximation to $scriptstylesqrt\; 2$. The sequence of approximations of this form is:$1,\; frac32,\; frac75,\; frac\{17\}\{12\},\; frac\{41\}\{29\},\; frac\{99\}\{70\},\; dots$where the denominator of each fraction is a Pell number and the numerator is the sum of a Pell number and its predecessor in the sequence. That is, the solutions have the form $frac\{P\_\{n-1\}+P\_n\}\{P\_n\}$. The approximation:$sqrt\; 2approxfrac\{577\}\{408\}$of this type was known to Indian mathematicians in the third or fourth century B.C. [As recorded in the Shulba Sutras; see e.g. Dutka (1986), who cites Thibaut (1875) for this information.] The Greek mathematicians of the fifth century B.C. also knew of this sequence of approximations [See Knorr (1976) for the fifth century date, which matches Proclus' claim that the side and diameter numbers were discovered by the Pythagoreans. For more detailed exploration of later Greek knowledge of these numbers see Thompson (1929), Vedova (1951), Ridenhour (1986), Knorr (1998), and Filep (1999).] ; they called the denominators and numerators of this sequence side and diameter numbers and the numerators were also known as rational diagonals or rational diameters. [For instance, as several of the references from the previous note observe, in Plato's Republic there is a reference to the "rational diameter of 5", by which Plato means 7, the numerator of the approximation 7/5 of which 5 is the denominator.]

These approximations can be derived from the continued fraction expansion of $scriptstylesqrt\; 2$::$sqrt\; 2\; =\; 1\; +\; cfrac\{1\}\{2\; +\; cfrac\{1\}\{2\; +\; cfrac\{1\}\{2\; +\; cfrac\{1\}\{2\; +\; cfrac\{1\}\{ddots,\}.$Truncating this expansion to any number of terms produces one of the Pell-number-based approximations in this sequence; for instance,:$frac\{577\}\{408\}\; =\; 1\; +\; cfrac\{1\}\{2\; +\; cfrac\{1\}\{2\; +\; cfrac\{1\}\{2\; +\; cfrac\{1\}\{2\; +\; cfrac\{1\}\{2\; +\; cfrac\{1\}\{2\; +\; cfrac\{1\}\{2\}.$

As Knuth (1994) describes, the fact that Pell numbers approximate $scriptstylesqrt\; 2$ allows them to be used for accurate rational approximations to a regular octagon with vertex coordinates $(pm\; P\_i,pm\; P\_\{i+1\})$ and $(pm\; P\_\{i+1\},pm\; P\_i)$. All vertices are equally distant from the origin, and form nearly uniform angles around the origin. Alternatively, the points $(pm(P\_i+P\_\{i-1\}),0)$, $(0,pm(P\_i+P\_\{i-1\}))$, and $(pm\; P\_i,pm\; P\_i)$ form approximate octagons in which the vertices are nearly equally distant from the origin and form uniform angles.

Primes and squares

A Pell prime is a Pell number that is prime. The first few Pell primes are:2, 5, 29, 5741, ... OEIS|id=A086383.As with the Fibonacci numbers, a Pell number $P\_n$ can only be prime if "n" itself is prime.

The only Pell numbers that are squares, cubes, or any higher power of another integer are 0, 1, and 169 = 13². [Pethő (1992); Cohn (1996). Although the Fibonacci numbers are defined by a very similar recurrence to the Pell numbers, Cohn writes that an analogous result for the Fibonacci numbers seems much more difficult to prove.]

However, despite having so few squares or other powers, Pell numbers have a close connection to square triangular numbers. [Sesskin (1962). See the square triangular number article for a more detailed derivation.] Specifically, these numbers arise from the following identity of Pell numbers::The left side of this identity describes a square number, while the right side describes a triangular number, so the result is a square triangular number.

Santana and Diaz-Barrero (2006) prove another identity relating Pell numbers to squares and showing that the sum of the Pell numbers up to $P\_\{4n+1\}$ is always a square::$sum\_\{i=0\}^\{4n+1\}\; P\_i\; =\; left(sum\_\{r=0\}^n\; 2^r\{2n+1choose\; 2r\}\; ight)^2\; =\; (P\_\{2n\}+P\_\{2n+1\})^2.$For instance, the sum of the Pell numbers up to $P\_5$, $0+1+2+5+12+29=49$, is the square of $P\_2+P\_3=2+5=7$. The numbers $P\_\{2n\}+P\_\{2n+1\}$ forming the square roots of these sums,:1, 7, 41, 239, 1393, 8119, 47321, ... OEIS|id=A002315,are known as the NSW numbers.

Pythagorean triples

If a right triangle has integer side lengths "a", "b", "c" (necessarily satisfying the Pythagorean theorem "a"²+"b"²="c"²), then ("a","b","c") is known as a Pythagorean triple. As Martin (1875) describes, the Pell numbers can be used to form Pythagorean triples in which "a" and "b" are one unit apart, corresponding to right triangles that are nearly isosceles. Each such triple has the form:$(2P\_\{n\}P\_\{n+1\},\; P\_\{n+1\}^2\; -\; P\_\{n\}^2,\; P\_\{n+1\}^2\; +\; P\_\{n\}^2=P\_\{2n+1\}).$The sequence of Pythagorean triples formed in this way is:(4,3,5), (20,21,29), (120,119,169), (696,697,985), ...

Companion Pell numbers (Pell-Lucas numbers)

The companion Pell numbers or Pell-Lucas numbers are defined by the recurrence relation:

In words: the first two numbers in the sequence are both 2, and each successive number is formed by adding twice the previous Pell-Lucas number to the Pell-Lucas number before that. The first few terms of the sequence are OEIS|id=A002203: 2, 2, 6, 14, 34, 82, 198, 478...

The companion Pell numbers can be expressed by the closed form formula:$Q\_n=(1+sqrt\; 2)^n+(1-sqrt\; 2)^n.$

These numbers are all even; each such number is twice the numerator in one of the rational approximations to $scriptstylesqrt\; 2$ discussed above.

Notes

References

*cite journal
author = Bicknell, Marjorie
title = A primer on the Pell sequence and related sequences
journal = Fibonacci Quarterly
volume = 13
year = 1975
issue = 4
pages = 345–349
id = MathSciNet | id = 0387173

*cite journal
author = Cohn, J. H. E.
title = Perfect Pell powers
journal = Glasgow Mathematical Journal
volume = 38
year = 1996
issue = 1
pages = 19–20
id = MathSciNet | id = 1373953

*cite journal
author = Dutka, Jacques
title = On square roots and their representations
journal = Archive for History of Exact Sciences
volume = 36
issue = 1
year = 1986
pages = 21–39
doi = 10.1007/BF00357439
id = MathSciNet | id = 0863340

*cite journal
author = Ercolano, Joseph
title = Matrix generators of Pell sequences
journal = Fibonacci Quarterly
volume = 17
year = 1979
issue = 1
pages = 71–77
id = MathSciNet | id = 0525602

*cite journal
author = Filep, László
title = Pythagorean side and diagonal numbers
journal = Acta Mathematica Academiae Paedagogiace Nyíregyháziensis
volume = 15
year = 1999
pages = 1–7
url = http://www.emis.de/journals/AMAPN/vol15/filep.pdf

*cite journal
author = Horadam, A. F.
title = Pell identities
journal = Fibonacci Quarterly
volume = 9
year = 1971
issue = 3
pages = 245–252, 263
id = MathSciNet | id = 0308029

*cite journal
author = Kilic, Emrah; Tasci, Dursun
title = The linear algebra of the Pell matrix
journal = Boletín de la Sociedad Matemática Mexicana, Tercera Serie
volume = 11
year = 2005
issue = 2
pages = 163–174
id = MathSciNet | id = 2207722

*cite journal
author = Knorr, Wilbur
authorlink = Wilbur Knorr
title = Archimedes and the measurement of the circle: A new interpretation
journal = Archive for History of Exact Sciences
volume = 15
issue = 2
year = 1976
pages = 115–140
doi = 10.1007/BF00348496
id = MathSciNet | id = 0497462

*cite journal
author = Knorr, Wilbur
authorlink = Wilbur Knorr
title = "Rational diameters" and the discovery of incommensurability
journal = American Mathematical Monthly
volume = 105
issue = 5
pages = 421–429
year = 1998
doi = 10.2307/3109803

*cite journal
author = Knuth, Donald E.
authorlink = Donald Knuth
title = Leaper graphs
journal = The Mathematical Gazette
volume = 78
year = 1994
pages = 274–297
id = arxiv | archive = math.CO | id = 9411240
doi = 10.2307/3620202

*cite journal
author = Martin, Artemas
title = Rational right angled triangles nearly isosceles
journal = The Analyst
volume = 3
issue = 2
pages = 47–50
year = 1875
url = http://www.jstor.org/stable/2635906
doi = 10.2307/2635906

*cite conference
author = Pethő, A.
title = The Pell sequence contains only trivial perfect powers
booktitle = Sets, graphs, and numbers (Budapest, 1991)
publisher = Colloq. Math. Soc. János Bolyai, 60, North-Holland
date = 1992
pages = 561–568
id = MathSciNet | id = 1218218

*cite journal
author = Ridenhour, J. R.
title = Ladder approximations of irrational numbers
journal = Mathematics Magazine
year = 1986
volume = 59
issue = 2
pages = 95–105
url = http://www.jstor.org/stable/2690427

*cite journal
author = Santana, S. F.; Diaz-Barrero, J. L.
year = 2006
title = Some properties of sums involving Pell numbers
journal = Missouri Journal of Mathematical Sciences
volume = 18
issue = 1
url = http://www.math-cs.cmsu.edu/~mjms/2006.1/diazbar.pdf

*cite journal
author = Sellers, James A.
title = Domino tilings and products of Fibonacci and Pell numbers
year = 2002
journal = Journal of Integer Sequences
volume = 5
url = http://www.emis.de/journals/JIS/VOL5/Sellers/sellers4.pdf
id = MathSciNet | id = 1919941

*cite journal
author = Sesskin, Sam
title = A "converse" to Fermat's last theorem?
journal = Mathematics Magazine
volume = 35
issue = 4
year = 1962
pages = 215–217
url = http://links.jstor.org/sici?sici=0025-570X(196209)35%3A4%3C215%3AA%22TFLT%3E2.0.CO%3B2-6

*cite journal
author = Thibaut, George
authorlink = George Thibaut
title = On the Súlvasútras
journal = Journal of the Royal Asiatic Society of Bengal
volume = 44
pages = 227–275
year = 1875

*cite journal
author = Thompson, D'Arcy Wentworth
authorlink = D'Arcy Wentworth Thompson
title = III.—Excess and defect: or the little more and the little less
journal =
year = 1929
volume = 38
issue = 149
pages = 43–55
url = http://www.jstor.org/stable/2249223

*cite journal
author = Vedova, G. C.
title = Notes on Theon of Smyrna
journal = American Mathematical Monthly
year = 1951
volume = 58
issue = 10
pages = 675–683
doi = 10.2307/2307978

External links

*mathworld | title = Pell Number | urlname = PellNumber