Число Пелля

Числа Пелля задаются линейным рекуррентным соотношением:

${\displaystyle P_{n}={\begin{cases}0,n=0;\\1,n=1\\2P_{n-1}+P_{n-2},n>1\end{cases}}}$

и являются частным случаем последовательности Люка.

Первые несколько чисел Пелля

0, 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, … (последовательность A000129 в OEIS).

Числа Пелля можно выразить формулой

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

Для больши́х значений n член ${\displaystyle \scriptstyle (1+{\sqrt {2}})^{n}}$ доминирует в этом выражении, так что числа Пелля примерно пропорциональны степеням серебряного сечения ${\displaystyle \scriptstyle (1+{\sqrt {2}})}$, аналогично тому, как числа Фибоначчи примерно пропорциональны степеням золотого сечения.

Возможно и третье определение — в виде матричной формулы

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

Многие тождества могут быть доказаны из этих определений, например тождество, аналогичное тождеству Кассини для чисел Фибоначчи,

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

как немедленное следствие матричной формулы (подставляя определители матриц слева и справа)^[2].

Числа Пелля возникли исторически из рациональных приближений к квадратному корню из 2. Если два больших целых x и y дают решение уравнения Пелля

${\displaystyle \displaystyle x^{2}-2y^{2}=\pm 1,}$

то их отношение ${\displaystyle {\tfrac {x}{y}}}$ дает близкое приближение к ${\displaystyle \scriptstyle {\sqrt {2}}}$. Последовательность приближений этого вида

${\displaystyle 1,{\frac {3}{2}},{\frac {7}{5}},{\frac {17}{12}},{\frac {41}{29}},{\frac {99}{70}},\dots }$

где знаменатель каждой дроби — число Пелля, а числитель равен сумме числа Пелля и его предшественника в последовательности. Таким образом, приближения имеют вид ${\displaystyle {\tfrac {P_{n-1}+P_{n}}{P_{n}}}}$.

Приближение

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

этого типа было известно математикам Индии в третьем—четвертом столетии до нашей эры^[3]. Греческие математики пятого столетия до нашей эры также знали об этом приближении^[4]. Платон (Plato) ссылается на числители как рациональные диаметры^[5]. Во втором столетии нашей эры Теон Смирнский использовал термины сторона и диаметр для описания знаменателя и числителя этой последовательности^[6].

Эти приближения могут быть получены из цепной дроби ${\displaystyle \scriptstyle {\sqrt {2}}}$:

${\displaystyle {\sqrt {2}}=1+{\cfrac {1}{2+{\cfrac {1}{2+{\cfrac {1}{2+{\cfrac {1}{2+{\cfrac {1}{2+\ddots \,}}}}}}}}}}.}$

Конечная часть цепной дроби дает аппроксимацию в виде чисел Пелля. Например,

${\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}}}}}}}}}}}}}}.}$

Как писал Кнут (1994), факт аппроксимации числами Пелля ${\displaystyle \scriptstyle {\sqrt {2}}}$ позволяет использовать их для рационального приближения к правильному восьмиугольнику с координатами вершин ${\displaystyle (\pm P_{i},\pm P_{i+1})}$ и ${\displaystyle (\pm P_{i+1},\pm P_{i})}$. Все вершины этого восьмиугольника одинаково удалены от центра и формируют почти одинаковые углы. Также точки ${\displaystyle (\pm (P_{i}+P_{i-1}),0)}$, ${\displaystyle (0,\pm (P_{i}+P_{i-1}))}$ и ${\displaystyle (\pm P_{i},\pm P_{i})}$ формируют восьмиугольник, у которого вершины почти одинаково удалены от центра и формируют одинаковые углы.

Простым числом Пелля называется число Пелля, являющееся также простым. Несколько первых простых чисел Пелля

2, 5, 29, 5741, … (последовательность A086383 в OEIS)

Как и в случае с числами Фибоначчи, число Пелля ${\displaystyle P_{n}}$ может быть простым только если n само просто.

Имеется всего три числа Пелля, являющимися квадратами, кубами и другими более высокими степенями, — это 0, 1 и 169 = 13^2[7].

Несмотря на то, что имеется столь мало квадратов и других степеней среди чисел Пелля, они имеют близкую связь с квадратными треугольными числами^[8]. Эти числа возникают из следующего тождества:

${\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}}.}$

Левая часть этого тождества даёт квадратное число, в то время как правая часть даёт треугольное число, так что в результате получим квадратное треугольное число.

Сантана (Santana) и Диац-Барреро (Diaz-Barrero) (2006) доказали другое тождество, связывающее числа Пелля с квадратами, показав, что сумма чисел Пелля до ${\displaystyle P_{4n+1}}$ всегда квадрат:

${\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}.}$

Например, сумма чисел Пелля до ${\displaystyle P_{5}}$, ${\displaystyle 0+1+2+5+12+29=49}$, является квадратом числа ${\displaystyle P_{2}+P_{3}=2+5=7}$.

Числа ${\displaystyle P_{2n}+P_{2n+1}}$, образующие квадратные корни таких сумм,

1, 7, 41, 239, 1393, 8119, 47 321, … (последовательность A002315 в OEIS),

известны как простые числа Ньюмена — Шэнкса — Уильямса.

Если прямоугольный треугольник имеет стороны a, b, c (по теореме Пифагора a²+b²=c²), то (a,b,c) известны как пифагоровы тройки. Мартин (Martin) (1875) пишет, что числа Пелля могут быть использованы для формирования пифагоровых троек, в которых a и b отличаются на единицу, что соответствует почти равнобедренному прямоугольному треугольнику. Каждая такая тройка имеет вид

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

Последовательность пифагоровых троек, полученного таким способом

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

Сопутствующие числа Пелля или числа Пелля — Люка определяются линейным рекуррентным соотношением:

${\displaystyle Q_{n}={\begin{cases}2,n=0\\2,n=1\\2Q_{n-1}+Q_{n-2},n>1\end{cases}}}$

То есть, первые два числа в последовательности равны 2, а все остальные формируются как сумма удвоенного предыдущего числа Пелля — Люка и предшествующего ему, или, что эквивалентно, сложением следующего числа Пелля и предыдущего числа. Так, сопровождающим для 82 является число 29, и 82 = 2 · 34 + 14 = 70 + 12.

Сопутствующие числа Пелля образуют последовательность:

2, 2, 6, 14, 34, 82, 198, 478, … (последовательность A002203 в OEIS)

Сопутствующие числа Пелля можно выразить формулой:

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

Все эти числа чётны, каждое из них является удвоенным числителем в приближении рациональными числами к ${\displaystyle \scriptstyle {\sqrt {2}}}$.

Следующая таблица даёт несколько первых степеней серебряного сечения ${\displaystyle \delta =\delta _{S}=1+{\sqrt {2}}}$ и связанного с ним ${\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\ldots }$	${\displaystyle 1-1{\sqrt {2}}=-0.41421\ldots }$
2	${\displaystyle 3+2{\sqrt {2}}=5.82842\ldots }$	${\displaystyle 3-2{\sqrt {2}}=0.17157\ldots }$
3	${\displaystyle 7+5{\sqrt {2}}=14.07106\ldots }$	${\displaystyle 7-5{\sqrt {2}}=-0.07106\ldots }$
4	${\displaystyle 17+12{\sqrt {2}}=33.97056\ldots }$	${\displaystyle 17-12{\sqrt {2}}=0.02943\ldots }$
5	${\displaystyle 41+29{\sqrt {2}}=82.01219\ldots }$	${\displaystyle 41-29{\sqrt {2}}=-0.01219\ldots }$
6	${\displaystyle 99+70{\sqrt {2}}=197.9949\ldots }$	${\displaystyle 99-70{\sqrt {2}}=0.0050\ldots }$
7	${\displaystyle 239+169{\sqrt {2}}=478.00209\ldots }$	${\displaystyle 239-169{\sqrt {2}}=-0.00209\ldots }$
8	${\displaystyle 577+408{\sqrt {2}}=1153.99913\ldots }$	${\displaystyle 577-408{\sqrt {2}}=0.00086\ldots }$
9	${\displaystyle 1393+985{\sqrt {2}}=2786.00035\ldots }$	${\displaystyle 1393-985{\sqrt {2}}=-0.00035\ldots }$
10	${\displaystyle 3363+2378{\sqrt {2}}=6725.99985\ldots }$	${\displaystyle 3363-2378{\sqrt {2}}=0.00014\ldots }$
11	${\displaystyle 8119+5741{\sqrt {2}}=16238.00006\ldots }$	${\displaystyle 8119-5741{\sqrt {2}}=-0.00006\ldots }$
12	${\displaystyle 19601+13860{\sqrt {2}}=39201.99997\ldots }$	${\displaystyle 19601-13860{\sqrt {2}}=0.00002\ldots }$

Коэффициенты представляют собой половины сопутствующих чисел Пелля ${\displaystyle H_{n}}$ и числа Пелля ${\displaystyle P_{n}}$, являющиеся неотрицательными решениями уравнения ${\displaystyle H^{2}-2P^{2}=\pm 1}$.

Квадратное треугольное число — это число ${\displaystyle N={\frac {t(t+1)}{2}}=s^{2}}$, которое является как ${\displaystyle t}$-м треугольным числом так и ${\displaystyle s}$-м квадратным. Почти равнобедеренные пифагоровы тройки являются целыми решениями ${\displaystyle a^{2}+b^{2}=c^{2}}$, где ${\displaystyle a+1=b}$.

Следующая таблица показывает разложение нечетных ${\displaystyle H_{n}}$ на две почти одинаковые половинки, дающее квадратное треугольное число когда n четно и почти равнобедренную пифагорову тройку, когда n нечетно.

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

Половины сопутствующих чисел Пелля ${\displaystyle H_{n}}$ и числа Пелля ${\displaystyle P_{n}}$ могут быть получены несколькими эквивалентными путями:

Возведение в степень:

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

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

Откуда следует:

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

и

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

Парные рекуррентные отношения:

${\displaystyle H_{n}={\begin{cases}1,n=0\\H_{n-1}+2P_{n-1},n>0\end{cases}}}$

${\displaystyle P_{n}={\begin{cases}0,n=0;\\H_{n-1}+P_{n-1},n>0\end{cases}}}$

или, в матричном виде:

${\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}}.}$

Таким образом

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

Разность ${\displaystyle H_{n}}$ и ${\displaystyle P_{n}{\sqrt {2}}}$ равна ${\displaystyle (1-{\sqrt {2}})^{n}\approx (-0.41421)^{n}}$, что быстро стремится к нулю. Таким образом ${\displaystyle (1+{\sqrt {2}})^{n}=H_{n}+P_{n}{\sqrt {2}}}$ очень близко к ${\displaystyle 2H_{n}}$.

Из этого наблюдения следует, что отношение целых ${\displaystyle {\frac {H_{n}}{P_{n}}}}$ быстро приближается к ${\displaystyle {\sqrt {2}}}$ в то время как ${\displaystyle {\frac {H_{n}}{H_{n-1}}}}$ и ${\displaystyle {\frac {P_{n}}{P_{n-1}}}}$ быстро приближается к ${\displaystyle 1+{\sqrt {2}}}$.

Поскольку ${\displaystyle {\sqrt {2}}}$ является иррациональным, мы не можем получить ${\displaystyle {\frac {H}{P}}=2}$, то есть ${\displaystyle {\frac {H^{2}}{P^{2}}}={\frac {2P^{2}}{P^{2}}}}$. Лучшее, что мы можем получить, это либо ${\displaystyle {\frac {H^{2}}{P^{2}}}={\frac {2P^{2}-1}{P^{2}}}}$ либо ${\displaystyle {\frac {H^{2}}{P^{2}}}={\frac {2P^{2}+1}{P^{2}}}}$.

Неотрицательными решениями ${\displaystyle H^{2}-2P^{2}=1}$ являются пары ${\displaystyle H_{n},P_{n}}$ с четным n, и решениями ${\displaystyle H^{2}-2P^{2}=-1}$ являются пары ${\displaystyle H_{n},P_{n}}$ с n нечетным.

Чтобы понять это, заметим

${\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})}$

так что, начиная с ${\displaystyle H_{0}^{2}-2P_{0}^{2}=1}$ знак чередуется (${\displaystyle 1,-1}$). Заметим теперь, что каждое положительное решение можно получить из решения с меньшим индексом благодаря равенству ${\displaystyle (2P-H)^{2}-2(H-P)^{2}=-(H^{2}-2P^{2})}$.

Требуемое равенство ${\displaystyle {\frac {t(t+1)}{2}}=s^{2}}$ эквивалентно ${\displaystyle 4t^{2}+4t+1=8s^{2}+1}$, что превращается в ${\displaystyle H^{2}=2P^{2}+1}$ при подстановке ${\displaystyle H=2t+1}$ и ${\displaystyle P=2s}$. Отсюда n-м решением будет ${\displaystyle t_{n}={\frac {H_{2n}-1}{2}}}$ и ${\displaystyle s_{n}={\frac {P_{2n}}{2}}.}$

Заметим, что ${\displaystyle t}$ и ${\displaystyle t+1}$ взаимно просты, так что ${\displaystyle {\frac {t(t+1)}{2}}=s^{2}}$ возможно только тогда, когда они являются соседними целыми, одно — квадрат ${\displaystyle H^{2}}$ и другое — удвоенный квадрат ${\displaystyle 2P^{2}}$. Поскольку мы знаем все решения уравнения, мы получаем

${\displaystyle t_{n}={\begin{cases}2P_{n}^{2}&n\equiv 0{\pmod {2}}\\H_{n}^{2}&n\equiv 1{\pmod {2}}\end{cases}}}$

и ${\displaystyle s_{n}=H_{n}P_{n}}$

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

Равенство ${\displaystyle c^{2}=a^{2}+(a+1)^{2}=2a^{2}+2a+1}$ верно только при ${\displaystyle 2c^{2}=4a^{2}+4a+2}$, что превращается в ${\displaystyle 2P^{2}=H^{2}+1}$ при подстановке ${\displaystyle H=2a+1{\mbox{ and }}P=c}$. Тогда n-м решением является ${\displaystyle a_{n}={\frac {H_{2n+1}-1}{2}}}$ и ${\displaystyle c_{n}={P_{2n+1}}.}$

Таблица выше показывает, что с точностью до порядка ${\displaystyle a_{n}}$ и ${\displaystyle b_{n}=a_{n}+1}$ равны ${\displaystyle H_{n}H_{n+1}}$ и ${\displaystyle 2P_{n}P_{n+1}}$ , в то время как ${\displaystyle c_{n}=H_{n+1}P_{n}+P_{n+1}H_{n}.}$