Сопряжённые числа (стр. 2 из 3)

|x

2n

– 2y

2n

| = |x

2n+1

– 2y

2n+1

|.

Добавив начальное условие x₁ = 1, y₁ = 1, отсюда (по индукции) можно было бы заключить, что |x_n² – 2y_n²| = 1 для любого n. Далее, выразив обратно (x_n;y_n): через (x_n+1;y_n+1), «методом спуска» ([8]) можно доказать, что найденной серией исчерпываются все решения уравнения (5) в натуральных числах (x;y). Подобным же образом решается любое «уравнение Пелля» x² – dy² = c (а к уравнениям такого типа сводится любое квадратное уравнение в целых числах x, y), но у исходного уравнения может быть несколько серий решений ([7]).

Рекуррентные соотношения типа (6) возникают не только в теории чисел, но и в разных задачах анализа, теории вероятностей. Вот характерный пример комбинаторной задачи такого типа (она предлагалась на последней международной олимпиаде в Лондоне):

7. В вершине A правильного восьмиугольника сидит лягушка. Из любой вершины восьмиугольника, кроме вершины E, противоположной A, она может прыгнуть в любую из двух соседних вершин. Попав в E, лягушка останавливается и остаётся там. Найти количество e_m различных способов, которыми лягушка может попасть из вершины A в E ровно за m прыжков.

Если раскрасить вершины восьмиугольника через одну в чёрный и белый цвет (рис.2), сразу станет ясно, что e_2k–1 = 0 при любом k: цвет вершин при каждом прыжке меняется. Обозначим через a_n и c_n количество способов, которым лягушка может за 2n прыжков, попасть из вершины A, соответственно, в вершину A и в одну из вершин C (из соображений симметрии ясно, что в каждую из вершин, обозначенных на рисунке буквой C, можно попасть одним и тем же числом способов). Как легко проверить (см. рис.2а,б,в,г),

a₁ = 2, c₁ = 1;

(7)

А интересующее нас число e_2n равно, очевидно, 2c_n–1 (рис. 2д).

а) c1 = 1

б) a1 = 2

в) an+1 = 2an + 2cn