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