Число Пелля

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

Числа Пелля[править | править вики-текст]

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

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+\sqrt2)^n-(1-\sqrt2)^n}{2\sqrt2}.

Для больших значений 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.

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

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

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

Приближение к квадратному корню из двух[править | править вики-текст]

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

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

\displaystyle x^2-2y^2=\pm 1,

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

1, \frac32, \frac75, \frac{17}{12}, \frac{41}{29}, \frac{99}{70}, \dots

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

Приближение

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

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

Эти приближения могут быть получены из цепной дроби \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 = 132.[7]

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

\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, 47321, … (последовательность A002315 в OEIS),

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

Пифагоровы тройки[править | править вики-текст]

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

Если прямоугольный треугольник имеет стороны a, b, c (по теореме Пифагора a2+b2=c2), то (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+\sqrt2 и связанного с ним \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=\pm1.

Квадратное треугольное число — это число 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+\sqrt2)^n=H_n+P_n\sqrt{2}
(1-\sqrt2)^n=H_n-P_n\sqrt{2}.

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

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

и

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

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

H2 − 2P2 = ±1[править | править вики-текст]

Поскольку \sqrt2 является иррациональным, мы не можем получить \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_nP_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_nH_{n+1} и 2P_nP_{n+1} , в то время как c_n=H_{n+1}P_n+P_{n+1}H_n.

Примечания[править | править вики-текст]

  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. Например, в Государстве Платона tимеется ссылка на «рациональный диаметр пчти», под которым Платон подразумевал 7, числитель приближения 7/5.
  6. A History of Greek Mathematics: From Thales to Euclid - Sir Thomas Little Heath - Google Books. Проверено 28 января 2013.
  7. Pethő (1992); Cohn (1996). Хотя числа Фибоначчи определяются рекуррентыми формулами, очень похожими на формулы для чисел Пелля, Кон (Cohn) пишет, что аналогичные результаты для чисел Фибоначчи куда сложнее доказать. (Однако, они были доказаны в 2006 году Бугеадом (Bugeaud).)
  8. Sesskin (1962).

Ссылки[править | править вики-текст]

Ссылки[править | править вики-текст]