Число Пелля

Число Пелля — целое число, входящее в качестве знаменателя в бесконечную последовательность подходящих дробей для квадратного корня из 2. Эта последовательность приближений начинается следующим образом: ${\frac {1}{1}},{\frac {3}{2}},{\frac {7}{5}},{\frac {17}{12}},{\frac {41}{29}},\dots$, то есть первые числа Пелля — 1, 2, 5, 12 и 29. Числители той же последовательности приближений являются половинами сопутствующих чисел Пелля или числами Пелля — Люка — бесконечной последовательностью, начинающейся с 2, 6, 14, 34 и 82.

Обе последовательности, числа Пелля и сопутствующие числа Пелля, могут быть вычислены с помощью рекуррентного соотношения, похожего на формулы для чисел Фибоначчи, и обе последовательности чисел растут экспоненциально, пропорционально степени серебряного сечения $1+{\sqrt {2}}$.

Кроме использования в цепной дроби приближений к квадратному корню из двух, числа Пелля могут быть использованы для поиска квадратных треугольных чисел и для решения некоторых комбинаторных задач перечисления.

Последовательность чисел Пелля известна с древних времен. Как и уравнение Пелля, числа Пелля ошибочно приписаны Леонардом Эйлером Джону Пеллю. Числа Пелля — Люка названы в честь Эдуарда Люка, который изучал эти последовательности. И числа Пелля, и сопутствующие числа Пелля, являются частными случаями последовательностей Люка.

Числа Пелля

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

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

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

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

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

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

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

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

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

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

Приближение к квадратному корню из двух

Рациональное приближение к правильным восьмиугольникам, с координатами из чисел Пелля

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

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

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

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

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

Приближение

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

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

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

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

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

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

Простые и квадраты

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

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

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

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

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

${\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) доказали другое тождество, связывающее числа Пелля с квадратами, показав, что сумма чисел Пелля до $P_{4n+1}$ всегда квадрат:

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

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

Числа $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 отличаются на единицу, что соответствует почти равнобедренному прямоугольному треугольнику. Каждая такая тройка имеет вид

$(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), ….

Числа Пелля — Люка

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

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

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

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

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

Вычисления и связи

Следующая таблица даёт несколько первых степеней серебряного сечения $\delta =\delta _{S}=1+{\sqrt {2}}$ и связанного с ним ${\bar {\delta }}=1-{\sqrt {2}}$.

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

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

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

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

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

Определения

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

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

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

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

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

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

и

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

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

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

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

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

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

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

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

Приближения

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

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

H² − 2P² = ±1

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

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

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

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

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

Квадратные треугольные числа

Основная статья: Квадратное треугольное число

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

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

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

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

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

Триплеты Пифагора

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

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

Литература

• Bicknell, Marjorie. A primer on the Pell sequence and related sequences // Fibonacci Quarterly. — 1975. — Т. 13, вып. 4. — С. 345—349.
• Cohn, J. H. E. Perfect Pell powers // Glasgow Mathematical Journal. — 1996. — Т. 38, вып. 1. — С. 19—20. — doi:10.1017/S0017089500031207.
• Dutka, Jacques. On square roots and their representations // Archive for History of Exact Sciences. — 1986. — Т. 36, вып. 1. — С. 21—39. — doi:10.1007/BF00357439.
• Ercolano, Joseph. Matrix generators of Pell sequences // Fibonacci Quarterly. — 1979. — Т. 17, вып. 1. — С. 71—77.
• Filep, László. Pythagorean side and diagonal numbers // Acta Mathematica Academiae Paedagogiace Nyíregyháziensis. — 1999. — Т. 15. — С. 1–7.
• Horadam, A. F. Pell identities // Fibonacci Quarterly. — 1971. — Т. 9, вып. 3. — С. 245—252, 263.
• Kilic, Emrah; Tasci, Dursun. The linear algebra of the Pell matrix // Boletín de la Sociedad Matemática Mexicana, Tercera Serie. — 2005. — Т. 11, вып. 2. — С. 163—174.
• Knorr, Wilbur. Archimedes and the measurement of the circle: A new interpretation // Archive for History of Exact Sciences. — 1976. — Т. 15, вып. 2. — С. 115—140. — doi:10.1007/BF00348496.
• Knorr, Wilbur. "Rational diameters" and the discovery of incommensurability // American Mathematical Monthly. — 1998. — Т. 105, вып. 5. — С. 421—429. — doi:10.2307/3109803.
• Knuth, Donald E. Leaper graphs // The Mathematical Gazette. — 1994. — Т. 78, вып. 483. — С. 274—297. — doi:10.2307/3620202. — arXiv:math.CO/9411240.
• Martin, Artemas. Rational right angled triangles nearly isosceles // The Analyst. — 1875. — Т. 3, вып. 2. — С. 47—50. — doi:10.2307/2635906. — .
• Pethő, A. Sets, graphs, and numbers (Budapest, 1991). — Colloq. Math. Soc. János Bolyai, 60, North-Holland, 1992. — С. 561—568.
• Ridenhour, J. R. Ladder approximations of irrational numbers // Mathematics Magazine. — Т. 59, вып. 2. — С. 95—105. — doi:10.2307/2690427. — .
• Santana, S. F.; Diaz-Barrero, J. L. Some properties of sums involving Pell numbers // Missouri Journal of Mathematical Sciences. — 2006. — Т. 18, вып. 1. Архивировано 8 мая 2007 года.
• Sellers, James A. Domino tilings and products of Fibonacci and Pell numbers // Journal of Integer Sequences. — 2002. — Т. 5.
• Sesskin, Sam. A «converse» to Fermat's last theorem? // Mathematics Magazine. — 1962. — Т. 35, вып. 4. — С. 215—217. — doi:10.2307/2688551. — .
• Thibaut, George. On the Súlvasútras // Journal of the Royal Asiatic Society of Bengal. — 1875. — Т. 44. — С. 227—275.
• Thompson, D'Arcy Wentworth. III.—Excess and defect: or the little more and the little less // Mind: New Series. — 1929. — Т. 38, вып. 149. — С. 43—55. — .
• Vedova, G. C. Notes on Theon of Smyrna // American Mathematical Monthly. — 1951. — Т. 58, вып. 10. — С. 675—683. — doi:10.2307/2307978. — .

Ссылки

• Weisstein, Eric W. Pell Number (англ.) на сайте Wolfram MathWorld.