До этого рекуррентного соотношения можно было, видимо, догадаться по нескольким первым решениям, а потом проверить, что
Добавив начальное условие x1 = 1, y1 = 1, отсюда (по индукции) можно было бы заключить, что |xn2 – 2yn2| = 1 для любого n. Далее, выразив обратно (xn;yn): через (xn+1;yn+1), «методом спуска» ([8 ]) можно доказать, что найденной серией исчерпываются все решения уравнения (5) в натуральных числах (x;y). Подобным же образом решается любое «уравнение Пелля» x2 – dy2 = c (а к уравнениям такого типа сводится любое квадратное уравнение в целых числах x, y), но у исходного уравнения может быть несколько серий решений ([7 ]). Рекуррентные соотношения типа (6) возникают не только в теории чисел, но и в разных задачах анализа, теории вероятностей. Вот характерный пример комбинаторной задачи такого типа (она предлагалась на последней международной олимпиаде в Лондоне): 7. В вершине A правильного восьмиугольника сидит лягушка. Из любой вершины восьмиугольника, кроме вершины E, противоположной A, она может прыгнуть в любую из двух соседних вершин. Попав в E, лягушка останавливается и остаётся там. Найти количество em различных способов, которыми лягушка может попасть из вершины A в E ровно за m прыжков. Если раскрасить вершины восьмиугольника через одну в чёрный и белый цвет (рис.2), сразу станет ясно, что e2k–1 = 0 при любом k: цвет вершин при каждом прыжке меняется. Обозначим через an и cn количество способов, которым лягушка может за 2n прыжков, попасть из вершины A, соответственно, в вершину A и в одну из вершин C (из соображений симметрии ясно, что в каждую из вершин, обозначенных на рисунке буквой C, можно попасть одним и тем же числом способов). Как легко проверить (см. рис.2а,б,в,г), a1 = 2, c1 = 1;
|
Главная