Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/2003/02/33.pdf Дата изменения: Fri Dec 23 19:27:20 2005 Дата индексирования: Tue Oct 2 00:31:07 2012 Кодировка: Windows-1251 Поисковые слова: п п п п п п п п п п п п

Рис. 7

ношения: 1 + 2 + 3 + K + n = n

+2

- 1,

1 + 3 + 5 + K + 2n n + 1n

-1

= 2n ,
n +1

2 + 4 + 6 + K + 2n = 2
-1

- 1,

n 2 - n = ( -1) ,

которые можно доказать методом математической индукции. Последнее соотношение открыл в 1680 году французский астроном Жан Доминик Кассини. При n = 6 оно превращается в числовое равенство
13 5 - 82 = 1 ,

на рисунке 9 сложен прямоугольник размером 5 Ч 13 . (Аналогичная конструкция при любом n разбивает квадрат со стороной n на четыре части, из которых получается прямоугольник размером n -1 Ч n + 1 . Одна клетка либо теряется, либо возникает лишняя в зависимости от четности n.) Разгадка парадокса проста: на рисунке 9 линии, соединяющие левый верхний угол с нижним правым углом, на самом деле образуют не отрезок, а незаметный для глаза параллелограмм. Соотношение Кассини можно использовать и для других целей. Если заменить в нем n -1 на n + 1 - n , то оно примет вид
2 n +1 n 2 - n + 1n - n = ( -1) .

НО Д (12 ,

= НОД (144, 2584 ) = 8 = 6 ).

18

)

=

Для доказательства последнего факта полезно тождество

m

+n

= m n

-1

+ m + 1n ,

Можно доказать, что никаких других решений в натуральных числах уравнение

которое лежит в основе геометрического парадокса: на рисун-

x 2 - xy - y 2 = +1
не имеет. В 1970 году это (и более сложные свойства) было использовано Ю.В.Матиясевичем при решении десятой проблемы Гильберта о несуществовании алгоритма, который решает задачу, имеет или нет уравнение вида P (x 1 , x 2 , K , x n ) = 0 , где P многочлен с целыми коэффициентами, решения в целых числах. Много интересного в арифметике чисел Фибоначчи. Каждое третье число Фибоначчи четно; каждое четвертое кратно 3; каждое пятнадцатое оканчивается нулем; два соседних числа Фибоначчи взаимно просты; n кратно m в том и только том случае, когда n кратно m; наибольший общий делитель чисел n и m число Фибоначчи с номером НОД (m , n ) (например,

Рис. 8

ке 8 шахматная доска разрезана на четыре части, из которых

которое можно доказать по индукции. Но мы разберем более интересное доказательство выясним комбинаторный смысл этого тождества. Рассмотрим для этого полоску из k клеток и задумаемся, сколько существует способов пройти из левой клетки полоски в правую клетку этой полоски, если каждым ходом разрешается переходить в соседнюю справа клетку или перепрыгивать через одну клетку. Очевидно, при k = 1 идти некуда, да и не нужно; при k = 2 нужно сделать ровно один шаг. Значит, при k = 1 или 2 число способов равно 1. Для рассматриваемого числа способов выполнена в точности такая же рекуррентная формула, что и для чисел Фибоначчи. В самом деле, если первый шаг сдвиг на 1 клетку, то остается полоска из k 1 клетки, если же первый шаг сдвиг на 2 клетки, то остается полоска из k 2 клеток. Итак, число способов пройти полоску это число Фибоначчи. Осталось заметить, что все m +n способов можно разбить на два типа: можно остановиться на (m + 1) -й клетке (таких способов m + 1n ), а можно ее перепрыгнуть (таких способов m n -1 ). В 1728 году Даниэль Бернулли опубликовал формулу n = n n 1 1+ 5 1 1- 5 = - , 5 2 5 2 но о ней позабыли до 1843 года, когда она была вновь открыта французом Жаком Бине. Из этой формулы следует, в частности, что n растет примерно как геометрическая прогрессия со з наменателем = 1 + 5 2 , точнее, n равно ближайшему к n 5 целому числу. А.Спивак

(

)

Рис. 9