User:Gentlemath/Sandbox

In mathematics, the Pell numbers are an integer sequence that has been known at least since 400 BCE.^[1] 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... (sequence A000129 in the OEIS).

The Half companion Pell numbers are another sequence which begins 1, 1, 3, 7, 17, 41... and has the same recurrence. Theon of Smyrna defined the two sequences by a paired recurrence and observed that the square of each number in this second sequence is one more or one less than the square of the corresponding Pell number (3²=2•2²+1 and 7²=2•5²-1 and so on). Consequently, this second sequence suplies the numerators, and the Pell numbers the denominators, of the sequence 1/1, 3/2, 7/5, 17/12, 41/29 ... of closest rational approximations to the square root of 2. The doubles of the numerators are sometimes called companion Pell numbers or Pell-Lucas numbers; these numbers form a second infinite sequence that begins with 2, 2, 6, 14, 34, and 82.

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 nearly-isosceles integer right triangles, and to solve certain combinatorial enumeration problems.^[2]

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.

The Pell numbers are defined by the recurrence relation

${\displaystyle P_{n}={\begin{cases}0&{\mbox{if }}n=0;\\1&{\mbox{if }}n=1;\\2P_{n-1}+P_{n-2}&{\mbox{otherwise.}}\end{cases}}}$

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 Pell numbers can also be expressed by the closed form formula

${\displaystyle P_{n}={\frac {(1+{\sqrt {2}})^{n}-(1-{\sqrt {2}})^{n}}{2{\sqrt {2}}}}.}$

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

${\displaystyle {\begin{pmatrix}P_{n+1}&P_{n}\\P_{n}&P_{n-1}\end{pmatrix}}={\begin{pmatrix}2&1\\1&0\end{pmatrix}}^{n}.}$

Many identities can be derived or proven from these definitions; for instance an identity analogous to Cassini's identity for Fibonacci numbers,

${\displaystyle 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).^[3]

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 \displaystyle x^{2}-2y^{2}=\pm 1,}$

then their ratio ${\displaystyle {\tfrac {x}{y}}}$ provides a close approximation to ${\displaystyle \scriptstyle {\sqrt {2}}}$. The sequence of approximations of this form is

${\displaystyle 1,{\frac {3}{2}},{\frac {7}{5}},{\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 ${\displaystyle {\tfrac {P_{n-1}+P_{n}}{P_{n}}}}$. The approximation

${\displaystyle {\sqrt {2}}\approx {\frac {577}{408}}}$

of this type was known to Indian mathematicians in the third or fourth century B.C.^[4] The Greek mathematicians of the fifth century B.C. also knew of this sequence of approximations;^[5] 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.^[6]

These approximations can be derived from the continued fraction expansion of ${\displaystyle \scriptstyle {\sqrt {2}}}$:

${\displaystyle {\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,

${\displaystyle {\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 ${\displaystyle \scriptstyle {\sqrt {2}}}$ allows them to be used for accurate rational approximations to a regular octagon with vertex coordinates ${\displaystyle (\pm P_{i},\pm P_{i+1})}$ and ${\displaystyle (\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 ${\displaystyle (\pm (P_{i}+P_{i-1}),0)}$, ${\displaystyle (0,\pm (P_{i}+P_{i-1}))}$, and ${\displaystyle (\pm P_{i},\pm P_{i})}$ form approximate octagons in which the vertices are nearly equally distant from the origin and form uniform angles.

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

As with the Fibonacci numbers, a Pell number ${\displaystyle P_{n}}$ 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 = 13².^[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:

${\displaystyle {\bigl (}(P_{k-1}+P_{k})\cdot P_{k}{\bigr )}^{2}={\frac {(P_{k-1}+P_{k})^{2}\cdot \left((P_{k-1}+P_{k})^{2}-(-1)^{k}\right)}{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) prove another identity relating Pell numbers to squares and showing that the sum of the Pell numbers up to ${\displaystyle P_{4n+1}}$ is always a square:

${\displaystyle \sum _{i=0}^{4n+1}P_{i}=\left(\sum _{r=0}^{n}2^{r}{2n+1 \choose 2r}\right)^{2}=(P_{2n}+P_{2n+1})^{2}.}$

For instance, the sum of the Pell numbers up to ${\displaystyle P_{5}}$, ${\displaystyle 0+1+2+5+12+29=49}$, is the square of ${\displaystyle P_{2}+P_{3}=2+5=7}$. The numbers ${\displaystyle 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 NSW numbers.

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

${\displaystyle (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), ....

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

${\displaystyle Q_{n}={\begin{cases}2&{\mbox{if }}n=0;\\2&{\mbox{if }}n=1;\\2Q_{n-1}+Q_{n-2}&{\mbox{otherwise.}}\end{cases}}}$

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. T he first few terms of the sequence are (sequence A002203 in the OEIS): 2, 2, 6, 14, 34, 82, 198, 478...

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

${\displaystyle 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 ${\displaystyle \scriptstyle {\sqrt {2}}}$ discussed above.

The following table gives the first few powers of the silver ratio ${\displaystyle \delta =\delta _{S}=1+{\sqrt {2}}}$ and its conjugate ${\displaystyle {\bar {\delta }}=1-{\sqrt {2}}}$.

${\displaystyle n}$	${\displaystyle (1+{\sqrt {2}})^{n}}$	${\displaystyle (1-{\sqrt {2}})^{n}}$
0	${\displaystyle 1+0{\sqrt {(}}2)=1.0}$	${\displaystyle 1-0{\sqrt {(}}2)=1.0}$
1	${\displaystyle 1+1{\sqrt {2}}=2.41421...}$	${\displaystyle 1-1{\sqrt {2}}=-0.41421...}$
2	${\displaystyle 3+2{\sqrt {2}}=5.82842...}$	${\displaystyle 3-2{\sqrt {2}}=0.17157...}$
3	${\displaystyle 7+5{\sqrt {2}}=14.07106...}$	${\displaystyle 7-5{\sqrt {2}}=-0.07106...}$
4	${\displaystyle 17+12{\sqrt {2}}=33.97056...}$	${\displaystyle 17-12{\sqrt {2}}=0.02943...}$
5	${\displaystyle 41+29{\sqrt {2}}=82.01219...}$	${\displaystyle 41-29{\sqrt {2}}=-0.01219...}$
6	${\displaystyle 99+70{\sqrt {2}}=197.9949...}$	${\displaystyle 99-70{\sqrt {2}}=0.0050...}$
7	${\displaystyle 239+169{\sqrt {2}}=478.00209...}$	${\displaystyle 239-169{\sqrt {2}}=-0.00209...}$
8	${\displaystyle 577+408{\sqrt {2}}=1153.99913...}$	${\displaystyle 577-408{\sqrt {2}}=0.00086...}$
9	${\displaystyle 1393+985{\sqrt {2}}=2786.00035...}$	${\displaystyle 1393-985{\sqrt {2}}=-0.00035...}$
10	${\displaystyle 3363+2378{\sqrt {2}}=6725.99985...}$	${\displaystyle 3363-2378{\sqrt {2}}=0.00014...}$
11	${\displaystyle 8119+5741{\sqrt {2}}=16238.00006...}$	${\displaystyle 8119-5741{\sqrt {2}}=-0.00006...}$
12	${\displaystyle 19601+13860{\sqrt {2}}=39201.99997...}$	${\displaystyle 19601-13860{\sqrt {2}}=0.00002...}$

The coefficients are the Pell numbers and the Half companion Pell numbers ${\displaystyle H_{n}}$ and The Pell numbers ${\displaystyle P_{n}}$ which are the (non-negative) solutions to ${\displaystyle H^{2}-2P^{2}=\pm 1}$. A Square triangular number is a number ${\displaystyle N={\frac {t(t+1)}{2}}=s^{2}}$ which is both the ${\displaystyle t\,}$th triangular number and the ${\displaystyle s\,}$th square number. A near isosceles Pythagorean triple is an integer solution to ${\displaystyle a^{2}+b^{2}=c^{2}}$ where ${\displaystyle a+1=b}$. $H_n$ is always odd. The next table shows that splitting $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.

${\displaystyle n}$	${\displaystyle H_{n}}$	${\displaystyle P_{n}}$	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

The half companion Pell Numbers ${\displaystyle H_{n}}$ and the Pell numbers ${\displaystyle P_{n}}$ can be derived in a number of easily equivalent ways:

Raising to powers:

${\displaystyle (1+{\sqrt {2}})^{n}=H_{n}+P_{n}{\sqrt {2}}}$

${\displaystyle (1-{\sqrt {2}})^{n}=H_{n}-P_{n}{\sqrt {2}}}$

From this it follows that there are closed forms:

${\displaystyle H_{n}={\frac {(1+{\sqrt {2}})^{n}+(1-{\sqrt {2}})^{n}}{2}}.}$

and

${\displaystyle P_{n}{\sqrt {2}}={\frac {(1+{\sqrt {2}})^{n}-(1-{\sqrt {2}})^{n}}{2}}.}$

Paired recurrences:

${\displaystyle H_{n}={\begin{cases}1&{\mbox{if }}n=0;\\H_{n-1}+2P_{n-1}&{\mbox{otherwise.}}\end{cases}}}$

${\displaystyle P_{n}={\begin{cases}0&{\mbox{if }}n=0;\\H_{n-1}+P_{n-1}&{\mbox{otherwise.}}\end{cases}}}$

and Matrix formulations:

${\displaystyle {\begin{pmatrix}H_{n}\\P_{n}\end{pmatrix}}={\begin{pmatrix}1&2\\1&1\end{pmatrix}}{\begin{pmatrix}H_{n-1}\\P_{n-1}\end{pmatrix}}={\begin{pmatrix}1&2\\1&1\end{pmatrix}}^{n}{\begin{pmatrix}1\\0\end{pmatrix}}.}$

So

${\displaystyle {\begin{pmatrix}H_{n}&2P_{n}\\P_{n}&H_{n}\end{pmatrix}}={\begin{pmatrix}1&2\\1&1\end{pmatrix}}^{n}.}$

The difference between ${\displaystyle H_{n}\,}$ and ${\displaystyle P_{n}{\sqrt {2}}}$ is ${\displaystyle (1-{\sqrt {2}})^{n}\approx (-0.41421)^{n}}$ which goes rapidly to zero. So ${\displaystyle (1+{\sqrt {2}})^{n}=H_{n}+P_{n}{\sqrt {2}}}$ is extremely close ${\displaystyle 2H_{n}\,}$.

From this last observation it follows that the integer ratios ${\displaystyle {\frac {H_{n}}{P_{n}}}}$ rapidly approach ${\displaystyle {\sqrt {2}}\,}$ while ${\displaystyle {\frac {H_{n}}{H_{n-1}}}\,}$ and ${\displaystyle {\frac {P_{n}}{P_{n-1}}}\,}$ rapidly approach ${\displaystyle 1+{\sqrt {2}}\,}$.

Since ${\displaystyle {\sqrt {2}}}$ is irrational, we can't have ${\displaystyle {\frac {H}{P}}=2\,}$ i.e. ${\displaystyle {\frac {H^{2}}{P^{2}}}={\frac {2P^{2}}{P^{2}}}\,}$. The best we can achieve is either ${\displaystyle {\frac {H^{2}}{P^{2}}}={\frac {2P^{2}-1}{P^{2}}}\,}$ or ${\displaystyle {\frac {H^{2}}{P^{2}}}={\frac {2P^{2}+1}{P^{2}}}}$.

The (non-negative) solutions to ${\displaystyle H^{2}-2P^{2}=1\,}$ are exactly the pairs ${\displaystyle H_{n},P_{n}{\mbox{ with }}n\,}$ even and the solutions to ${\displaystyle H^{2}-2P^{2}=-1\,}$ are exactly the pairs ${\displaystyle H_{n},P_{n}{\mbox{ with }}n\,}$ odd. To see this, note first that

${\displaystyle H_{n+1}^{2}-2P_{n+1}^{2}=(H_{n}+2P_{n})^{2}-2(H_{n}+P_{n})^{2}=-(H_{n}^{2}-2P_{n}^{2})\,}$

so that these differences, starting with ${\displaystyle H_{0}^{2}-2P_{0}^{2}=1\,}$ are alternately ${\displaystyle 1{\mbox{ and }}-1\,}$. Then note that that every positive solution comes in this way from a solution with smaller integers since ${\displaystyle (2P-H)^{2}-2(H-P)^{2}=-(H^{2}-2P^{2})\,}$. The smaller solution also has positive integers with the one exception ${\displaystyle H=P=1\,}$ which comes from ${\displaystyle H_{0}=1{\mbox{ and }}P_{0}=0\,}$.

The required equation ${\displaystyle {\frac {t(t+1)}{2}}=s^{2}\,}$ is equivalent to ${\displaystyle 4t^{2}+4t+1=8s^{2}+1\,}$ which becomes ${\displaystyle H^{2}=2P^{2}+1}$ with the substitutions ${\displaystyle H=2t+1{\mbox{ and }}P=2s}$. Hence the nth solution is ${\displaystyle t_{n}={\frac {H_{2n}-1}{2}}}$ and ${\displaystyle s_{n}={\frac {P_{2n}}{2}}.}$

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

${\displaystyle t_{n}={\begin{cases}2P_{n}^{2}&{\mbox{if }}n{\mbox{ is even}};\\H_{n}^{2}&{\mbox{if }}n{\mbox{ is odd.}}\end{cases}}}$

and ${\displaystyle s_{n}=H_{n}P_{n}\,}$

This alternate expression is seen in the next table.

${\displaystyle n}$	${\displaystyle H_{n}}$	${\displaystyle P_{n}}$		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

The equality ${\displaystyle c^{2}=a^{2}+(a+1)^{2}=2a^{2}+2a+1}$ occurs exactly when ${\displaystyle 2c^{2}=4a^{2}+4a+2}$ which becomes ${\displaystyle 2P^{2}=H^{2}+1}$ with the substitutions ${\displaystyle H=2a+1{\mbox{ and }}P=c}$. Hence the nth solution is ${\displaystyle a_{n}={\frac {H_{2n+1}-1}{2}}}$ and ${\displaystyle c_{n}={P_{2n+1}}.}$

The table above shows that in one order or the other ${\displaystyle a_{n}{\mbox{ and}}b_{n}=a_{n}+1}$ are ${\displaystyle H_{n}H_{n+1}{\mbox{ and}}2P_{n}P_{n+1}}$ while ${\displaystyle c_{n}=H_{n+1}P_{n}+P_{n+1}H_{n}.}$

• Weisstein, Eric W. "Pell Number". MathWorld.