Interested Article - Число Пелля

Число Пелля — целое число , входящее в качестве знаменателя в бесконечную последовательность подходящих дробей для квадратного корня из 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, … (последовательность в 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, … (последовательность в 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, … (последовательность в 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 , , , … (последовательность в 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 ² − 2 P ² = ±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}.$

Примечания

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

Литература

Bicknell, Marjorie. // . — 1975. — Т. 13 , вып. 4 . — С. 345—349 .
Cohn, J. H. E. Perfect Pell powers // . — 1996. — Т. 38 , вып. 1 . — С. 19—20 . — doi : .
Dutka, Jacques. // Archive for History of Exact Sciences . — 1986. — Т. 36 , вып. 1 . — С. 21—39 . — doi : .
Ercolano, Joseph. // . — 1979. — Т. 17 , вып. 1 . — С. 71—77 .
Filep, László. Pythagorean side and diagonal numbers // . — 1999. — Т. 15 . — С. 1–7 .
Horadam, A. F. // . — 1971. — Т. 9 , вып. 3 . — С. 245—252, 263 .
Kilic, Emrah; Tasci, Dursun. The linear algebra of the Pell matrix // , 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 : .
Knorr, Wilbur. // American Mathematical Monthly . — 1998. — Т. 105 , вып. 5 . — С. 421—429 . — doi : .
Knuth, Donald E. // . — 1994. — Т. 78 , вып. 483 . — С. 274—297 . — doi : . — arXiv : .
. Rational right angled triangles nearly isosceles // The Analyst . — 1875. — Т. 3 , вып. 2 . — С. 47—50 . — doi : . — JSTOR .
Pethő, A. Sets, graphs, and numbers (Budapest, 1991). — Colloq. Math. Soc. János Bolyai, 60, North-Holland, 1992. — С. 561—568.
Ridenhour, J. R. // Mathematics Magazine . — Т. 59 , вып. 2 . — С. 95—105 . — doi : . — JSTOR .
Santana, S. F.; Diaz-Barrero, J. L. Some properties of sums involving Pell numbers // . — 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. // Mathematics Magazine . — 1962. — Т. 35 , вып. 4 . — С. 215—217 . — doi : . — JSTOR .
Thibaut, George. On the Súlvasútras // . — 1875. — Т. 44 . — С. 227—275 .
Thompson, D'Arcy Wentworth. // . — 1929. — Т. 38 , вып. 149 . — С. 43—55 . — JSTOR .
Vedova, G. C. // American Mathematical Monthly . — 1951. — Т. 58 , вып. 10 . — С. 675—683 . — doi : . — JSTOR .

Ссылки

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

[1] Например, Селлерс ( Sellers ) в 2002 году показал, что количество совершенных паросочетаний в декартовом произведении путей и графа K ₄ - e может быть вычислено как произведение числа Пелля на соответствующие число Фибоначчи

[2] О матричной формуле и её следствиях смотрите Эрколано (Ercolano) (1979), Килик (Kilic) и Таски (Tasci) (2005). Другие тождества для чисел Пелля приведены Хорадамом (Horadam) (1971) и Бикнеллем (Bicknell) (1975).

[3] Это записано в . Смотрите, например, Дутка (Dutka) (1986), который цитировал Тибаута (Thibaut) (1875)

[4] Смотри Кнорра (Knorr) (1976) со ссылкой на пятое столетие, что соответствует утверждению Прокла , что числа были открыты пифагорейцами . Для более полного исследования о более поздних знаниях греков об этих числах смотри Томпсона (Thompson) (1929), Ведова (Vedova) (1951), Риденхоура (Ridenhour) (1986), Кнорра (Knorr) (1998), и Филепа (Filep) (1999).

[5] Например, в Государстве Платона имеется ссылка на «рациональный диаметр пяти», под которым Платон подразумевал 7, числитель приближения 7/5.

[6] . Дата обращения: 28 января 2013.

[7] Pethő (1992); Cohn (1996). Хотя числа Фибоначчи определяются рекуррентными формулами, очень похожими на формулы для чисел Пелля, Кон (Cohn) пишет, что аналогичные результаты для чисел Фибоначчи куда сложнее доказать (однако, они доказаны в 2006 году Бугеадом [Bugeaud]).

[8] Sesskin (1962).