Pell number
Encyclopedia
In mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, the Pell numbers are an infinite sequence
Sequence
In mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence...

of integers that have been known since ancient times, the denominators of the closest rational approximations to the square root of 2
Square root of 2
The square root of 2, often known as root 2, is the positive algebraic number that, when multiplied by itself, gives the number 2. It is more precisely called the principal square root of 2, to distinguish it from the negative number with the same property.Geometrically the square root of 2 is the...

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

Both the Pell numbers and the companion Pell numbers may be calculated by means of a recurrence relation
Recurrence relation
In mathematics, a recurrence relation is an equation that recursively defines a sequence, once one or more initial terms are given: each further term of the sequence is defined as a function of the preceding terms....

similar to that for the Fibonacci number
Fibonacci number
In mathematics, the Fibonacci numbers are the numbers in the following integer sequence:0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\; \ldots\; ....

s, and both sequences of numbers grow exponentially
Exponential growth
Exponential growth occurs when the growth rate of a mathematical function is proportional to the function's current value...

, proportionally to powers of the silver ratio
Silver ratio
In mathematics, two quantities are in the silver ratio if the ratio between the sum of the smaller plus twice the larger of those quantities and the larger one is the same as the ratio between the larger one and the smaller. This defines the silver ratio as an irrational mathematical constant,...

1 + √2. As well as being used to approximate the square root of two, Pell numbers can be used to find square triangular number
Square triangular number
In mathematics, a square triangular number is a number which is both a triangular number and a perfect square....

s, to construct integer approximations to the right isosceles triangle, and to solve certain combinatorial enumeration problems.

As with Pell's equation
Pell's equation
Pell's equation is any Diophantine equation of the formx^2-ny^2=1\,where n is a nonsquare integer. The word Diophantine means that integer values of x and y are sought. Trivially, x = 1 and y = 0 always solve this equation...

, the name of the Pell numbers stems from Leonhard Euler's
Leonhard Euler
Leonhard Euler was a pioneering Swiss mathematician and physicist. He made important discoveries in fields as diverse as infinitesimal calculus and graph theory. He also introduced much of the modern mathematical terminology and notation, particularly for mathematical analysis, such as the notion...

mistaken attribution of the equation and the numbers derived from it to John Pell
John Pell
-Early life:He was born at Southwick in Sussex. He was educated at Steyning Grammar School, and entered Trinity College, Cambridge, at the age of thirteen. During his university career he became an accomplished linguist, and even before he took his B.A. degree corresponded with Henry Briggs and...

. The Pell-Lucas numbers are also named after Édouard Lucas
Edouard Lucas
François Édouard Anatole Lucas was a French mathematician. Lucas is known for his study of the Fibonacci sequence. The related Lucas sequences and Lucas numbers are named after him.-Biography:...

, who studied sequences defined by recurrences of this type; the Pell and companion Pell numbers are Lucas sequence
Lucas sequence
In mathematics, the Lucas sequences Un and Vn are certain integer sequences that satisfy the recurrence relationwhere P and Q are fixed integers...

s.

## Pell numbers

The Pell numbers are defined by the recurrence relation
Recurrence relation
In mathematics, a recurrence relation is an equation that recursively defines a sequence, once one or more initial terms are given: each further term of the sequence is defined as a function of the preceding terms....

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
, 1, 2, 5, 12
12 (number)
12 is the natural number following 11 and preceding 13.The word "twelve" is the largest number with a single-morpheme name in English. Etymology suggests that "twelve" arises from the Germanic compound twalif "two-leftover", so a literal translation would yield "two remaining [after having ten...

, 29
29 (number)
29 is the natural number following 28 and preceding 30.-In mathematics:It is the tenth prime number, and also the fourth primorial prime. It forms a twin prime pair with thirty-one, which is also a primorial prime. Twenty-nine is also the sixth Sophie Germain prime. It is also the sum of three...

, 70
70 (number)
70 is the natural number following 69 and preceding 71.-In mathematics:Its factorization makes it a sphenic number. 70 is a Pell number and a generalized heptagonal number, one of only two numbers to be both. Also, it is the seventh pentagonal number and the fourth 13-gonal number, as well as the...

, 169
169 (number)
169 is the natural number following 168 and preceding 170.-In mathematics:* 169 is an odd number* 169 is a square number. 13 x 13 = 169, and the reverse 31 x 31 = 961...

, 408, 985, 2378... .

The Pell numbers can also be expressed by the closed form formula
For large values of n, the term dominates this expression, so the Pell numbers are approximately proportional to powers of the silver ratio
Silver ratio
In mathematics, two quantities are in the silver ratio if the ratio between the sum of the smaller plus twice the larger of those quantities and the larger one is the same as the ratio between the larger one and the smaller. This defines the silver ratio as an irrational mathematical constant,...

, analogous to the growth rate of Fibonacci numbers as powers of the golden ratio
Golden ratio
In mathematics and the arts, two quantities are in the golden ratio if the ratio of the sum of the quantities to the larger quantity is equal to the ratio of the larger quantity to the smaller one. The golden ratio is an irrational mathematical constant, approximately 1.61803398874989...

.

A third definition is possible, from the matrix
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...

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 determinant
Determinant
In linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific arithmetic expression, while other ways to determine its value exist as well...

s 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
Diophantine approximation
In number theory, the field of Diophantine approximation, named after Diophantus of Alexandria, deals with the approximation of real numbers by rational numbers....

to the square root of 2
Square root of 2
The square root of 2, often known as root 2, is the positive algebraic number that, when multiplied by itself, gives the number 2. It is more precisely called the principal square root of 2, to distinguish it from the negative number with the same property.Geometrically the square root of 2 is the...

. If two large integers x and y form a solution to the Pell equation
then their ratio provides a close approximation to . 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 B.C. The Greek mathematicians of the fifth century B.C. also knew of this sequence of approximations; 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.

These approximations can be derived from the continued fraction
Continued fraction
In mathematics, a continued fraction is an expression obtained through an iterative process of representing a number as the sum of its integer part and the reciprocal of another number, then writing this other number as the sum of its integer part and another reciprocal, and so on...

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 allows them to be used for accurate rational approximations to a regular octagon with vertex coordinates and . 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

A Pell prime is a Pell number that is prime
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...

. The first few Pell primes are
2, 5, 29, 5741, ... .

As with the Fibonacci numbers, a Pell number can only be prime if n itself is prime.

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

However, despite having so few squares or other powers, Pell numbers have a close connection to square triangular number
Square triangular number
In mathematics, a square triangular number is a number which is both a triangular number and a perfect square....

s. Specifically, these numbers arise from the following identity of Pell numbers:
The left side of this identity describes a square number
Square number
In mathematics, a square number, sometimes also called a perfect square, is an integer that is the square of an integer; in other words, it is the product of some integer with itself...

, while the right side describes a triangular number
Triangular number
A triangular number or triangle number numbers the objects that can form an equilateral triangle, as in the diagram on the right. The nth triangle number is the number of dots in a triangle with n dots on a side; it is the sum of the n natural numbers from 1 to n...

, 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 is always a square:
For instance, the sum of the Pell numbers up to , , is the square of . The numbers forming the square roots of these sums,
1, 7, 41, 239, 1393, 8119, 47321, ... ,

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

## Pythagorean triples

If a right triangle
Right triangle
A right triangle or right-angled triangle is a triangle in which one angle is a right angle . The relation between the sides and angles of a right triangle is the basis for trigonometry.-Terminology:The side opposite the right angle is called the hypotenuse...

has integer side lengths a, b, c (necessarily satisfying the Pythagorean theorem
Pythagorean theorem
In mathematics, the Pythagorean theorem or Pythagoras' theorem is a relation in Euclidean geometry among the three sides of a right triangle...

a2+b2=c2), then (a,b,c) is known as a Pythagorean triple
Pythagorean triple
A Pythagorean triple consists of three positive integers a, b, and c, such that . Such a triple is commonly written , and a well-known example is . If is a Pythagorean triple, then so is for any positive integer k. A primitive Pythagorean triple is one in which a, b and c are pairwise coprime...

. 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, (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
Recurrence relation
In mathematics, a recurrence relation is an equation that recursively defines a sequence, once one or more initial terms are given: each further term of the sequence is defined as a function of the preceding terms....

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 : 2, 2, 6, 14
14 (number)
14 is the natural number following 13 and preceding 15.In speech, the numbers 14 and 40 are often confused. When carefully enunciated, they differ in which syllable is stressed: 14 vs 40...

, 34
34 (number)
34 is the natural number following 33 and preceding 35.-In mathematics:34 is the ninth distinct semiprime and has four divisors including unity and itself. Its neighbors, 33 and 35, also are distinct semiprimes, having four divisors each, and 34 is the smallest number to be surrounded by numbers...

, 82
82 (number)
82 is the natural number following 81 and preceding 83.-In mathematics:Eighty-two is the twenty-third biprime and the twelfth of the form...

, 198
198 (number)
198 is the natural number following 197 and preceding 199.-In mathematics:* 198 is an even number* 198 is an abundant number, as 270 is greater than 198* 198 is a composite number* 198 is a Harshad number, divisible by the sum of its digits...

, 478...

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.

## Computations and connections

The following table gives the first few powers of the silver ratio
Silver ratio
In mathematics, two quantities are in the silver ratio if the ratio between the sum of the smaller plus twice the larger of those quantities and the larger one is the same as the ratio between the larger one and the smaller. This defines the silver ratio as an irrational mathematical constant,...

and its conjugate .
0
1
2
3
4
5
6
7
8
9
10
11
12

The coefficients are the Half companion Pell numbers and The Pell numbers which are the (non-negative) solutions to
. A Square triangular number
Square triangular number
In mathematics, a square triangular number is a number which is both a triangular number and a perfect square....

is a number which is both the th triangular number and the th square number. A near isosceles Pythagorean triple is an integer solution to where .

The next table shows that splitting the odd number 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.
 t t+1 s a b c 0 1 0 0 0 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

The half companion Pell Numbers and the Pell numbers
can be derived in a number of easily equivalent ways:

Raising to powers:

From this it follows that there are closed forms:

and

Paired recurrences:

and matrix formulations:

So

### Approximations

The difference between and is which goes rapidly to zero. So
is extremely close .

From this last observation it follows that the integer ratios rapidly approach while and rapidly approach .

### H2 − 2P2 = ±1

Since is irrational, we can't have i.e. . The best we can achieve is either or .

The (non-negative) solutions to are exactly the pairs even and the solutions to are exactly the pairs odd. To see this, note first that

so that these differences, starting with are alternately
. 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
which comes from .

### Square triangular numbers

The required equation is equivalent to which becomes
with the substitutions . Hence the nth solution is and

Observe that and are relatively prime so that happens exactly when they are adjacent integers, one a square and the other twice a square . Since we know all solutions of that equation, we also have

and

This alternate expression is seen in the next table.
 t t+1 s a b c 0 1 0 1 1 1 1 2 1 1 0 1 2 3 2 8 9 6 3 4 5 3 7 5 49 50 35 21 20 29 4 17 12 288 289 204 119 120 169 5 41 29 1681 1682 1189 697 696 985 6 99 70 9800 9801 6930 4059 4060 5741

### Pythagorean triples

The equality occurs exactly when which becomes with the substitutions
. Hence the nth solution is and

The table above shows that, in one order or the other, are while