Pell number

Summary

In mathematics, the Pell numbers are an infinite sequence of integers, known since ancient times, that comprise the denominators of the closest rational approximations to the square root of 2. This sequence of approximations begins 1/1, 3/2, 7/5, 17/12, and 41/29, so the sequence of Pell numbers begins with 1, 2, 5, 12, and 29. The numerators of the same sequence of approximations are half the companion Pell numbers or Pell–Lucas numbers; these numbers form a second infinite sequence that begins with 2, 6, 14, 34, and 82.

The sides of the squares used to construct a silver spiral are the Pell numbers

Both the Pell numbers and the companion Pell numbers may be calculated by means of a recurrence relation similar to that for the Fibonacci numbers, and both sequences of numbers grow exponentially, proportionally to powers of the silver ratio 1 + 2. As well as being used to approximate the square root of two, Pell numbers can be used to find square triangular numbers, to construct integer approximations to the right isosceles triangle, and to solve certain combinatorial enumeration problems.[1]

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 Édouard Lucas, who studied sequences defined by recurrences of this type; the Pell and companion Pell numbers are Lucas sequences.

Pell numbers edit

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

0, 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741, 13860, … (sequence A000129 in the OEIS).

Analogously to the Binet formula, the Pell numbers can also be expressed by the closed form formula

  For large values of n, the (1 + 2)n term dominates this expression, so the Pell numbers are approximately proportional to powers of the silver ratio 1 + 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,

 

is an immediate consequence of the matrix formula (found by considering the determinants of the matrices on the left and right sides of the matrix formula).[2]

Approximation to the square root of two edit

 
Rational approximations to regular octagons, with coordinates derived from the Pell numbers.

Pell numbers arise historically and most notably in the rational approximation to 2. If two large integers x and y form a solution to the Pell equation

 

then their ratio x/y provides a close approximation to 2. The sequence of approximations of this form is

 

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

 

The approximation

 

of this type was known to Indian mathematicians in the third or fourth century BCE.[3] The Greek mathematicians of the fifth century BCE also knew of this sequence of approximations:[4] Plato refers to the numerators as rational diameters.[5] In the second century CE Theon of Smyrna used the term the side and diameter numbers to describe the denominators and numerators of this sequence.[6]

These approximations can be derived from the continued fraction expansion of  :

 

Truncating this expansion to any number of terms produces one of the Pell-number-based approximations in this sequence; for instance,

 

As Knuth (1994) describes, the fact that Pell numbers approximate 2 allows them to be used for accurate rational approximations to a regular octagon with vertex coordinates (± Pi, ± Pi +1) and (± Pi +1, ± Pi ). All vertices are equally distant from the origin, and form nearly uniform angles around the origin. Alternatively, the points  ,  , and   form approximate octagons in which the vertices are nearly equally distant from the origin and form uniform angles.

Primes and squares edit

A Pell prime is a Pell number that is prime. The first few Pell primes are

2, 5, 29, 5741, 33461, 44560482149, 1746860020068409, 68480406462161287469, ... (sequence A086383 in the OEIS).

The indices of these primes within the sequence of all Pell numbers are

2, 3, 5, 11, 13, 29, 41, 53, 59, 89, 97, 101, 167, 181, 191, 523, 929, 1217, 1301, 1361, 2087, 2273, 2393, 8093, ... (sequence A096650 in the OEIS)

These indices are all themselves prime. As with the Fibonacci numbers, a Pell number Pn can only be prime if n itself is prime, because if d is a divisor of n then Pd is a divisor of Pn.

The only Pell numbers that are squares, cubes, or any higher power of an integer are 0, 1, and 169 = 132.[7]

However, despite having so few squares or other powers, Pell numbers have a close connection to square triangular numbers.[8] 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.

Falcón and Díaz-Barrero (2006) proved another identity relating Pell numbers to squares and showing that the sum of the Pell numbers up to P4n +1 is always a square:

 

For instance, the sum of the Pell numbers up to P5, 0 + 1 + 2 + 5 + 12 + 29 = 49, is the square of P2 + P3 = 2 + 5 = 7. The numbers P2n + P2n +1 forming the square roots of these sums,

1, 7, 41, 239, 1393, 8119, 47321, … (sequence A002315 in the OEIS),

are known as the Newman–Shanks–Williams (NSW) numbers.

Pythagorean triples edit

 
Integer right triangles with nearly equal legs, derived from the Pell numbers.

If a right triangle has integer side lengths a, b, c (necessarily satisfying the Pythagorean theorem a2 + b2 = c2), 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

 

The sequence of Pythagorean triples formed in this way is

(4,3,5), (20,21,29), (120,119,169), (696,697,985), …

Pell–Lucas numbers edit

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, or equivalently, by adding the next Pell number to the previous Pell number: thus, 82 is the companion to 29, and 82 = 2 × 34 + 14 = 70 + 12. The first few terms of the sequence are (sequence A002203 in the OEIS): 2, 2, 6, 14, 34, 82, 198, 478, …

Like the relationship between Fibonacci numbers and Lucas numbers,

 

for all natural numbers n.

The companion Pell numbers can be expressed by the closed form formula

 

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

Like the Lucas sequence, if a Pell–Lucas number 1/2Qn is prime, it is necessary that n be either prime or a power of 2. The Pell–Lucas primes are

3, 7, 17, 41, 239, 577, … (sequence A086395 in the OEIS).

For these n are

2, 3, 4, 5, 7, 8, 16, 19, 29, 47, 59, 163, 257, 421, … (sequence A099088 in the OEIS).

Computations and connections edit

The following table gives the first few powers of the silver ratio δ = δ S = 1 + 2 and its conjugate δ = 1 − 2.

n (1 + 2)n (1 − 2)n
0 1 + 02 = 1 1 − 02 = 1
1 1 + 12 = 2.41421… 1 − 12 = −0.41421…
2 3 + 22 = 5.82842… 3 − 22 = 0.17157…
3 7 + 52 = 14.07106… 7 − 52 = −0.07106…
4 17 + 122 = 33.97056… 17 − 122 = 0.02943…
5 41 + 292 = 82.01219… 41 − 292 = −0.01219…
6 99 + 702 = 197.9949… 99 − 702 = 0.0050…
7 239 + 1692 = 478.00209… 239 − 1692 = −0.00209…
8 577 + 4082 = 1153.99913… 577 − 4082 = 0.00086…
9 1393 + 9852 = 2786.00035… 1393 − 9852 = −0.00035…
10 3363 + 23782 = 6725.99985… 3363 − 23782 = 0.00014…
11 8119 + 57412 = 16238.00006… 8119 − 57412 = −0.00006…
12 19601 + 138602 = 39201.99997… 19601 − 138602 = 0.00002…

The coefficients are the half-companion Pell numbers Hn and the Pell numbers Pn which are the (non-negative) solutions to H  2 − 2P  2 = ±1. A square triangular number is a number

 

which is both the t-th triangular number and the s-th square number. A near-isosceles Pythagorean triple is an integer solution to a 2 + b 2 = c 2 where a + 1 = b.

The next table shows that splitting the odd number Hn into nearly equal halves gives a square triangular number when n is even and a near isosceles Pythagorean triple when n is odd. All solutions arise in this manner.

n Hn Pn t t + 1 s a b c
0 1 0 0 1 0      
1 1 1       0 1 1
2 3 2 1 2 1      
3 7 5       3 4 5
4 17 12 8 9 6      
5 41 29       20 21 29
6 99 70 49 50 35      
7 239 169       119 120 169
8 577 408 288 289 204      
9 1393 985       696 697 985
10 3363 2378 1681 1682 1189      
11 8119 5741       4059 4060 5741
12 19601 13860 9800 9801 6930      

Definitions edit

The half-companion Pell numbers Hn and the Pell numbers Pn can be derived in a number of easily equivalent ways.

Raising to powers edit

 
 

From this it follows that there are closed forms:

 

and

 

Paired recurrences edit

 
 

Reciprocal recurrence formulas edit

Let n be at least 2.

 
 

Matrix formulations edit

 

So

 

Approximations edit

The difference between Hn and Pn2 is

 

which goes rapidly to zero. So

 

is extremely close to 2Hn.

From this last observation it follows that the integer ratios Hn/Pn rapidly approach 2; and Hn/Hn −1 and Pn/Pn −1 rapidly approach 1 + 2.

H  2 − 2P  2 = ±1 edit

Since 2 is irrational, we cannot have H/P = 2, i.e.,

 

The best we can achieve is either

 

The (non-negative) solutions to H  2 − 2P  2 = 1 are exactly the pairs (Hn, Pn) with n even, and the solutions to H  2 − 2P  2 = −1 are exactly the pairs (Hn, Pn) with n odd. To see this, note first that

 

so that these differences, starting with H  2
  0
− 2P  2
  0
= 1
, are alternately 1 and −1. Then note that every positive solution comes in this way from a solution with smaller integers since

 

The smaller solution also has positive integers, with the one exception: H = P = 1 which comes from H0 = 1 and P0 = 0.

Square triangular numbers edit

The required equation

 

is equivalent to   which becomes H  2 = 2P  2 + 1 with the substitutions H = 2t + 1 and P = 2s. Hence the n-th solution is

 

Observe that t and t + 1 are relatively prime, so that t (t + 1)/2 = s 2 happens exactly when they are adjacent integers, one a square H  2 and the other twice a square 2P  2. Since we know all solutions of that equation, we also have

 

and  

This alternate expression is seen in the next table.

n Hn Pn t t + 1 s a b c
0 1 0            
1 1 1 1 2 1 3 4 5
2 3 2 8 9 6 20 21 29
3 7 5 49 50 35 119 120 169
4 17 12 288 289 204 696 697 985
5 41 29 1681 1682 1189 4059 4060 5741
6 99 70 9800 9801 6930 23660 23661 33461

Pythagorean triples edit

The equality c 2 = a 2 + (a + 1) 2 = 2a 2 + 2a + 1 occurs exactly when 2c 2 = 4a 2 + 4a + 2 which becomes 2P  2 = H  2 + 1 with the substitutions H = 2a + 1 and P = c. Hence the n-th solution is an = H2n +1 − 1/2 and cn = P2n +1.

The table above shows that, in one order or the other, an and bn = an + 1 are HnHn +1 and 2PnPn +1 while cn = Hn +1Pn + Pn +1Hn.

Notes edit

  1. ^ For instance, Sellers (2002) proves that the number of perfect matchings in the Cartesian product of a path graph and the graph K4 − e can be calculated as the product of a Pell number with the corresponding Fibonacci number.
  2. ^ 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).
  3. ^ As recorded in the Shulba Sutras; see e.g. Dutka (1986), who cites Thibaut (1875) for this information.
  4. ^ 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).
  5. ^ 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.
  6. ^ Heath, Sir Thomas Little (1921), History of Greek Mathematics: From Thales to Euclid, Courier Dover Publications, p. 112, ISBN 9780486240732.
  7. ^ 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, this was proven in 2006 by Bugeaud et al.)
  8. ^ Sesskin (1962). See the square triangular number article for a more detailed derivation.

References edit

  • Bicknell, Marjorie (1975). "A primer on the Pell sequence and related sequences". Fibonacci Quarterly. 13 (4): 345–349. MR 0387173.
  • Cohn, J. H. E. (1996). "Perfect Pell powers". Glasgow Mathematical Journal. 38 (1): 19–20. doi:10.1017/S0017089500031207. MR 1373953.
  • Dutka, Jacques (1986). "On square roots and their representations". Archive for History of Exact Sciences. 36 (1): 21–39. doi:10.1007/BF00357439. MR 0863340. S2CID 122277481.
  • Ercolano, Joseph (1979). "Matrix generators of Pell sequences". Fibonacci Quarterly. 17 (1): 71–77. MR 0525602.
  • Filep, László (1999). "Pythagorean side and diagonal numbers" (PDF). Acta Mathematica Academiae Paedagogicae Nyíregyháziensis. 15: 1–7. Archived from the original (PDF) on 2020-07-06. Retrieved 2007-01-29.
  • Horadam, A. F. (1971). "Pell identities". Fibonacci Quarterly. 9 (3): 245–252, 263. MR 0308029.
  • Kilic, Emrah; Tasci, Dursun (2005). "The linear algebra of the Pell matrix". Boletín de la Sociedad Matemática Mexicana, Tercera Serie. 11 (2): 163–174. MR 2207722.
  • Knorr, Wilbur (1976). "Archimedes and the measurement of the circle: A new interpretation". Archive for History of Exact Sciences. 15 (2): 115–140. doi:10.1007/BF00348496. MR 0497462. S2CID 120954547.
  • Knorr, Wilbur (1998). ""Rational diameters" and the discovery of incommensurability". American Mathematical Monthly. 105 (5): 421–429. doi:10.2307/3109803. JSTOR 3109803.
  • Knuth, Donald E. (1994). "Leaper graphs". The Mathematical Gazette. 78 (483): 274–297. arXiv:math.CO/9411240. Bibcode:1994math.....11240K. doi:10.2307/3620202. JSTOR 3620202. S2CID 16856513.
  • Martin, Artemas (1875). "Rational right angled triangles nearly isosceles". The Analyst. 3 (2): 47–50. doi:10.2307/2635906. JSTOR 2635906.
  • Pethő, A. (1992). "The Pell sequence contains only trivial perfect powers". Sets, graphs, and numbers (Budapest, 1991). Colloq. Math. Soc. János Bolyai, 60, North-Holland. pp. 561–568. MR 1218218.
  • Ridenhour, J. R. (1986). "Ladder approximations of irrational numbers". Mathematics Magazine. 59 (2): 95–105. doi:10.2307/2690427. JSTOR 2690427.
  • Falcón Santana, Sergio; Díaz-Barrero, José Luis (2006). "Some properties of sums involving Pell numbers". Missouri Journal of Mathematical Sciences. 18 (1). doi:10.35834/2006/1801033. hdl:10553/72698.
  • Sellers, James A. (2002). "Domino tilings and products of Fibonacci and Pell numbers" (PDF). Journal of Integer Sequences. 5: 12. Bibcode:2002JIntS...5...12S. MR 1919941. Archived from the original (PDF) on 2020-07-05. Retrieved 2007-01-28.
  • Sesskin, Sam (1962). "A "converse" to Fermat's last theorem?". Mathematics Magazine. 35 (4): 215–217. doi:10.2307/2688551. JSTOR 2688551.
  • Thibaut, George (1875). "On the Súlvasútras". Journal of the Royal Asiatic Society of Bengal. 44: 227–275.
  • Thompson, D'Arcy Wentworth (1929). "III.—Excess and defect: or the little more and the little less". Mind. New Series. 38 (149): 43–55. doi:10.1093/mind/XXXVIII.149.43. JSTOR 2249223.
  • Vedova, G. C. (1951). "Notes on Theon of Smyrna". American Mathematical Monthly. 58 (10): 675–683. doi:10.2307/2307978. JSTOR 2307978.

External links edit

  • Weisstein, Eric W. "Pell Number". MathWorld.
  • OEIS sequence A001333 (Numerators of continued fraction convergents to sqrt(2))—The numerators of the same sequence of approximations