Русская Википедия:Число Пелля

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

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

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

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

Числа Пелля

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

<math>P_n=\begin{cases}0, n=0;\\1, n=1 \\2P_{n-1}+P_{n-2}, n>1 \end{cases}</math>

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

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

Шаблон:Num, 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, … (Шаблон:OEIS).

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

<math>P_n=\frac{(1+\sqrt2)^n-(1-\sqrt2)^n}{2\sqrt2}.</math>

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

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

<math>\begin{pmatrix} P_{n+1} & P_n \\ P_n & P_{n-1} \end{pmatrix} = \begin{pmatrix} 2 & 1 \\ 1 & 0 \end{pmatrix}^{N-1}.</math>

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

<math>P_{n+1}P_{n-1}-P_n^2 = (-1)^{N-1},</math>

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

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

Файл:Pell octagons.svg
Рациональное приближение к правильным восьмиугольникам, с координатами из чисел Пелля

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

<math>\displaystyle x^2-2y^2=\pm 1,</math>

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

<math>1, \frac32, \frac75, \frac{17}{12}, \frac{41}{29}, \frac{99}{70}, \dots</math>

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

Приближение

<math>\sqrt 2\approx\frac{577}{408}</math>

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

Эти приближения могут быть получены из цепной дроби <math>\scriptstyle\sqrt 2</math>:

<math>\sqrt 2 = 1 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2 + \ddots\,}}}}}.</math>

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

<math>\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}}}}}}}.</math>

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

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

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

2, 5, 29, 5741, … (Шаблон:OEIS)

Как и в случае с числами Фибоначчи, число Пелля <math>P_n</math> может быть простым только если n само просто.

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

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

<math>\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}.</math>

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

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

<math>\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.</math>

Например, сумма чисел Пелля до <math>P_5</math>, <math>0+1+2+5+12+29=49</math>, является квадратом числа <math>P_2+P_3=2+5=7</math>.

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

1, 7, 41, 239, 1393, 8119, 47 321, … (Шаблон:OEIS),

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

Пифагоровы тройки

Файл:Pell right triangles.svg
Прямоугольные треугольники с почти равными катетами и целочисленными координатами, порождённые числами Пелля.

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

<math>(2P_{n}P_{n+1}, P_{n+1}^2 - P_{n}^2, P_{n+1}^2 + P_{n}^2=P_{2n+1}).</math>

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

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

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

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

<math>Q_n=\begin{cases}2, n=0\\2, n=1\\2Q_{n-1}+Q_{n-2}, n>1\end{cases}</math>

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

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

2, 2, 6, 14, 34, 82, 198, 478, … (Шаблон:OEIS)

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

<math>Q_n=(1+\sqrt 2)^n+(1-\sqrt 2)^n.</math>

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

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

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

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

Коэффициенты представляют собой половины сопутствующих чисел Пелля <math>H_n</math> и числа Пелля <math>P_n</math>, являющиеся неотрицательными решениями уравнения <math>H^2-2P^2=\pm1</math>.

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

Следующая таблица показывает разложение нечетных <math>H_n</math> на две почти одинаковые половинки, дающее квадратное треугольное число когда n четно и почти равнобедренную пифагорову тройку, когда n нечетно.

<math> n </math> <math> H_n </math> <math> P_n </math> 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

Определения

Половины сопутствующих чисел Пелля <math>H_n</math> и числа Пелля <math>P_n</math> могут быть получены несколькими эквивалентными путями:

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

<math>(1+\sqrt2)^n=H_n+P_n\sqrt{2}</math>
<math>(1-\sqrt2)^n=H_n-P_n\sqrt{2}.</math>

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

<math>H_n=\frac{(1+\sqrt2)^n+(1-\sqrt2)^n}{2}.</math>

и

<math>P_n\sqrt2=\frac{(1+\sqrt2)^n-(1-\sqrt2)^n}{2}.</math>

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

<math>H_n=\begin{cases}1, n=0\\H_{n-1}+2P_{n-1}, n>0\end{cases}</math>
<math>P_n=\begin{cases}0, n=0;\\H_{n-1}+P_{n-1}, n>0\end{cases}</math>

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

<math>\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}.</math>

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

<math> \begin{pmatrix} H_n & 2P_n \\ P_n & H_n \end{pmatrix}= \begin{pmatrix} 1 & 2 \\ 1 & 1 \end{pmatrix}^n .</math>

Приближения

Разность <math>H_n</math> и <math>P_n\sqrt2</math> равна <math>(1-\sqrt2)^n \approx (-0.41421)^n</math>, что быстро стремится к нулю. Таким образом <math>(1+\sqrt2)^n=H_n+P_n\sqrt2 </math> очень близко к <math>2H_n</math>.

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

H2 − 2P2 = ±1

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

Неотрицательными решениями <math>H^2-2P^2=1</math> являются пары <math>H_n,P_n</math> с четным n, и решениями <math>H^2-2P^2=-1</math> являются пары <math>H_n,P_n</math> с n нечетным.

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

<math>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)</math>

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

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

Шаблон:Main

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

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

<math>t_n=\begin{cases}2P_n^2&n \equiv 0\pmod 2 \\H_{n}^2&n\equiv 1 \pmod 2 \end{cases}</math>

и <math>s_n=H_nP_n</math>

<math> n </math> <math> H_n </math> <math> P_n </math> 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

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

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

Таблица выше показывает, что с точностью до порядка <math>a_n</math> и <math>b_n=a_n+1</math> равны <math>H_nH_{n+1}</math> и <math>2P_nP_{n+1}</math> , в то время как <math>c_n=H_{n+1}P_n+P_{n+1}H_n.</math>

Примечания

Шаблон:Примечания

Литература

Шаблон:Колонки

Шаблон:Колонки/конец

Ссылки

Шаблон:Rq

  1. Например, Селлерс (Sellers) в 2002 году показал, что количество совершенных паросочетаний в декартовом произведении путей и графа K4-e может быть вычислено как произведение числа Пелля на соответствующие число Фибоначчи
  2. О матричной формуле и её следствиях смотрите Эрколано (Ercolano) (1979), Килик (Kilic) и Таски (Tasci) (2005). Другие тождества для чисел Пелля приведены Хорадамом (Horadam) (1971) и Бикнеллем (Bicknell) (1975).
  3. Это записано в Shulba Sutras. Смотрите, например, Дутка (Dutka) (1986), который цитировал Тибаута (Thibaut) (1875)
  4. Смотри Кнорра (Knorr) (1976) со ссылкой на пятое столетие, что соответствует утверждению Прокла, что числа были открыты пифагорейцами. Для более полного исследования о более поздних знаниях греков об этих числах смотри Томпсона (Thompson) (1929), Ведова (Vedova) (1951), Риденхоура (Ridenhour) (1986), Кнорра (Knorr) (1998), и Филепа (Filep) (1999).
  5. Например, в Государстве Платона имеется ссылка на «рациональный диаметр пяти», под которым Платон подразумевал 7, числитель приближения 7/5.
  6. Шаблон:Cite web
  7. Pethő (1992); Cohn (1996). Хотя числа Фибоначчи определяются рекуррентными формулами, очень похожими на формулы для чисел Пелля, Кон (Cohn) пишет, что аналогичные результаты для чисел Фибоначчи куда сложнее доказать (однако, они доказаны в 2006 году Бугеадом [Bugeaud]).
  8. Sesskin (1962).