Pell number

Pell numbers

The Pell numbers are defined by the recurrence relation

P n = { 0 if  n = 0 ; 1 if  n = 1 ; 2 P n − 1 + P n − 2 otherwise.

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).

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

P n = ( 1 + 2 ) n − ( 1 − 2 ) n 2 2 .

For large values of n, the (1 + √2)ⁿ 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

( P n + 1 P n P n P n − 1 ) = ( 2 1 1 0 ) n .

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 the determinants of the matrices on the left and right sides of the matrix formula).

Approximation to the square root of two

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

x 2 − 2 y 2 = ± 1 ,

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

1 1 , 3 2 , 7 5 , 17 12 , 41 29 , 99 70 , …

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

P n − 1 + P n P n .

The approximation

2 ≈ 577 408

of this type was known to Indian mathematicians in the third or fourth century B.C. The Greek mathematicians of the fifth century B.C. also knew of this sequence of approximations: Plato refers to the numerators as rational diameters. In the 2nd century CE Theon of Smyrna used the term the side and diameter numbers to describe the denominators and numerators of this sequence.

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

2 = 1 + 1 2 + 1 2 + 1 2 + 1 2 + 1 2 + ⋱ .

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

577 408 = 1 + 1 2 + 1 2 + 1 2 + 1 2 + 1 2 + 1 2 + 1 2 .

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 (±P_i, ±P_i+1) and (±P_i+1, ±P_i). All vertices are equally distant from the origin, and form nearly uniform angles around the origin. Alternatively, the points ( ± ( P i + P i − 1 ) , 0 ) , ( 0 , ± ( P i + P i − 1 ) ) , and ( ± P i , ± 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,… (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,… (sequence A096650 in the OEIS)

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

The only Pell numbers that are squares, cubes, or any higher power of an integer are 0, 1, and 169 = 13².

However, despite having so few squares or other powers, Pell numbers have a close connection to square triangular numbers. Specifically, these numbers arise from the following identity of Pell numbers:

( ( P k − 1 + P k ) ⋅ P k ) 2 = ( P k − 1 + P k ) 2 ⋅ ( ( P k − 1 + P k ) 2 − ( − 1 ) k ) 2 .

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) proved 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:

∑ i = 0 4 n + 1 P i = ( ∑ r = 0 n 2 r ( 2 n + 1 2 r ) ) 2 = ( P 2 n + P 2 n + 1 ) 2 .

For instance, the sum of the Pell numbers up to P₅, 0 + 1 + 2 + 5 + 12 + 29 = 49, is the square of P₂ + P₃ = 2 + 5 = 7. The numbers P_2n + P_2n+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

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

( 2 P n P n + 1 , P n + 1 2 − P n 2 , P n + 1 2 + P n 2 = P 2 n + 1 ) .

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

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

Q n = { 2 if  n = 0 ; 2 if  n = 1 ; 2 Q n − 1 + Q n − 2 otherwise.

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,

Q n = P 2 n P n

for all natural numbers n.

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

Q n = ( 1 + 2 ) n + ( 1 − 2 ) n .

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

Like the Lucas sequence, if a Pell–Lucas number 1/2Q_n 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

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

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

N = t ( t + 1 ) 2 = s 2 ,

which is both the tth triangular number and the sth square number. A near-isosceles Pythagorean triple is an integer solution to a² + b² = c² where a + 1 = b.

The next table shows that splitting the odd number H_n 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.

Definitions

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

Raising to powers

( 1 + 2 ) n = H n + P n 2 ( 1 − 2 ) n = H n − P n 2 .

From this it follows that there are closed forms:

H n = ( 1 + 2 ) n + ( 1 − 2 ) n 2 .

and

P n 2 = ( 1 + 2 ) n − ( 1 − 2 ) n 2 .

Paired recurrences

H n = { 1 if  n = 0 ; H n − 1 + 2 P n − 1 otherwise. P n = { 0 if  n = 0 ; H n − 1 + P n − 1 otherwise.

Matrix formulations

( H n P n ) = ( 1 2 1 1 ) ( H n − 1 P n − 1 ) = ( 1 2 1 1 ) n ( 1 0 ) .

So

( H n 2 P n P n H n ) = ( 1 2 1 1 ) n .

Approximations

The difference between H_n and P_n√2 is

( 1 − 2 ) n ≈ ( − 0.41421 ) n ,

which goes rapidly to zero. So

( 1 + 2 ) n = H n + P n 2

is extremely close to 2H_n.

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

H2 − 2P2 = ±1

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

H 2 P 2 = 2 P 2 P 2 .

The best we can achieve is either

H 2 P 2 = 2 P 2 − 1 P 2 or H 2 P 2 = 2 P 2 + 1 P 2 .

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

H n + 1 2 − 2 P n + 1 2 = ( H n + 2 P n ) 2 − 2 ( H n + P n ) 2 = − ( H n 2 − 2 P n 2 ) ,

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

( 2 P − H ) 2 − 2 ( H − P ) 2 = − ( H 2 − 2 P 2 ) .

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

Square triangular numbers

The required equation

t ( t + 1 ) 2 = s 2

is equivalent to: 4 t 2 + 4 t + 1 = 8 s 2 + 1 , which becomes H² = 2P² + 1 with the substitutions H = 2t + 1 and P = 2s. Hence the nth solution is

t n = H 2 n − 1 2 and s n = P 2 n 2 .

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

t n = { 2 P n 2 if  n  is even ; H n 2 if  n  is odd.

and s n = H n P n .

This alternate expression is seen in the next table.

Pythagorean triples

The equality c² = a² + (a + 1)² = 2a² + 2a + 1 occurs exactly when 2c² = 4a² + 4a + 2 which becomes 2P² = H² + 1 with the substitutions H = 2a + 1 and P = c. Hence the nth solution is a_n = H_2n+1 − 1/2 and c_n = P_2n+1.

The table above shows that, in one order or the other, a_n and b_n = a_n + 1 are H_nH_n+1 and 2P_nP_n+1 while c_n = H_n+1P_n + P_n+1H_n.