Артур Бенджамин - Магия математики: Как найти x и зачем это нужно

Посмотрим, что произойдет при перемножении двух соседних чисел последовательности Фибоначчи. «Соседями» 5, например, являются 3 и 8. Их произведение равно 3 × 8 = 24, что лишь на единицу меньше 5². «Соседи» 8 – 5 и 13, которые при умножении друг на друга дают 65 – число, которое на единицу больше 82. Таблица, показанная ниже, подтверждает эту закономерность: в последовательности Фибоначчи произведение двух соседних с искомым чисел будет всегда отличаться на 1 от квадрата этого искомого. Другими словами,

С помощью метода доказательства (называемого также индукцией), о котором мы подробно поговорим в следующей главе, приходим к тому, что при n ≥ 1

А почему бы нам не пойти дальше, к дальним соседям? Возьмем число F5 = 5. Мы уже знаем, что его ближайшие «соседи» дают 3 × 8 = 24, что в шаге от 5². Но то же произойдет, если мы сделаем еще шаг влево и вправо по последовательности: 2 × 13 = 26, что так же в шаге от 5². А что насчет более отдаленных – на три, четыре шага – «соседей»? На пять, наконец? Получим 1 × 21 = 21, 1 × 34 = 34 и 0 × 55 = 0 соответственно. Насколько далеки эти результаты от 25? На 4, на 9 и на 25. Но это же квадраты натуральных чисел! Причем не всяких, а тех, что входят в последовательность Фибоначчи! Еще больше свидетельств этой закономерности – в таблице ниже, общая же формула выглядит так:

Еще несколько закономерностей чисел Фибоначчи

Говоря о треугольнике Паскаля, мы видели, насколько красивые в своей сложности закономерности демонстрируют его четные и нечетные числа. С последовательностью Фибоначчи все проще. Посмотрите на нее еще раз. Какие из этих чисел четные?

F3 = 2, F6 = 8, F9 = 34, F12 = 144 и т. д. (в этом разделе мы снова переключимся на заглавную F, чтобы подчеркнуть красоту и значительность описанных здесь закономерностей). Позиции четных чисел – 3, 6, 9 и 12. Похоже, что интервал между ними всегда равен 3. Доказать это очень легко, достаточно просто проследить закономерность с самого начала последовательности:

И дальше такой порядок повторяется вновь и вновь:

Происходит это потому, что после каждого блока «нечетное, нечетное, четное» следующий цикл сложения выглядит как «нечетное + четное = нечетное», потом «четное + нечетное = нечетное» и, наконец, «нечетное + нечетное = четное», так что закономерность бесконечно повторяется.

Говоря языком соотносимости, выученным нами в главе 3, каждое четное число соотносится с 0 (по модулю 2), а каждое нечетное – с 1 (также по модулю 2), а 1 + 1 ≡ 0 (mod 2). Вот как выглядит последовательность Фибоначчи в двоичной системе (или по модулю 2 – выбирайте любой термин):

А что насчет чисел, кратных 3? Первые из них – F4 = 3, F8 = 21, F12 = 144, что волей-неволей наталкивает нас на мысль, что кратные 3 числа занимают в последовательности каждое четвертое место. Чтобы эту догадку подтвердить, заменим все числа Фибоначчи на 0, 1 или 2 и будем считать по модулю 3, где

В троичной системе последовательность выглядит как

После каждого восьмого числа мы замыкаем круг и начинаем опять с двух следующих друг за другом единиц, то есть в этом случае цикл состоит из 8 чисел, четвертое и восьмое из которых – 0. Так и получается, что каждое четвертое место последовательности Фибоначчи занято числом, кратным 3. Считая по модулю 5, 8 или 13, обнаруживаем, что

и закономерность продолжается.

А что насчет чисел, следующих друг за другом? Есть ли между ними что-то общее? Что интересно – в каком-то смысле ничего общего между ними нет. И мы можем это продемонстрировать. Пары чисел, находящихся рядом в последовательности

называются взаимно простыми, что означает, что нет числа, большего чем 1, на которое они оба делятся. Если мы возьмем для примера последнюю из перечисленных выше пар, мы увидим, что 21 делится на 1, 3, 7 и 21, а 34 – на 1, 2, 17 и 34. То есть у 21 и 34 только один общий делитель – 1. Как убедиться, что эта закономерность повторяется? Откуда нам знать, что числа следующей пары (34, 55) – непременно взаимно простые? Для этого необязательно искать все делители для 55. Пойдем от обратного: предположим, что есть некое число d > 1, на которое и 34, и 55 делятся без остатка. Но тогда на него должна делиться без остатка и их разность: 55 – 34 = 21 (если два числа кратны третьему, их разность тоже будет ему кратна), что невозможно: ведь мы уже знаем, что нет такого d > 1, на которое можно было бы разделить и 21, и 34. Раз за разом применяя это доказательство, мы придем к выводу, что все числа последовательности Фибоначчи, образующие пары по принципу ближайшего соседства, являются взаимно простыми.

А теперь – мой самый любимый факт о числах Фибоначчи. Он касается наибольшего общего делителя (НОД). Наибольший общий делитель двух чисел есть наибольшее число, на которое делятся оба эти числа. Например, для 20 и 90 НОД равен 10. Обозначается это как

Как вы думаете, каким будет наибольший общий делитель двадцатого и девяностого чисел последовательности Фибоначчи? Ответ звучит как поэзия: 55 – десятое число последовательности Фибоначчи! А вот уравнение:

Или в общем виде, для значений m и n:

Другими словами, «НОД значений F есть значение F НОДа»! Подробно останавливаться на этом мы здесь не будем, но и пройти мимо я не мог.

Иногда закономерность может оказаться обманчивой. Какие, например, из чисел Фибоначчи являются простыми? (Простые – это числа больше 1, которые при этом делятся без остатка только на 1 и на самих себя, мы поговорим о них подробнее в следующей главе.) Числа больше единицы, не являющиеся простыми, называются составными, потому что их можно разложить на неделимые простые составляющие. Вот несколько первых простых чисел последовательности Фибоначчи:

А теперь взгляните на числа, стоящие на «простых» позициях:

Числа 2, 5, 13, 89, 233 и 1597 – простые. Закономерность вроде бы говорит нам о том, что, если значение p > 2 является простым, простым будет и Fp. Однако следующий же элемент последовательности эту закономерность нарушает: F19 = 4181 – уже составное число, потому что 4181 = 37 × 113. Но верно и то, что каждое простое число больше 3 стоит в последовательности Фибоначчи на «простой» позиции. Это следует из одной из уже рассмотренных закономерностей. F14 должно быть составным, поскольку каждое седьмое число последовательности кратно F7 = 13 (и правда: F14 = 377 = 13 × 29).

На самом деле простые числа Фибоначчи встречаются редко – пока что официально подтверждено лишь 33, наибольшее из них занимает F81839 позицию. И это притом, что вопрос, является ли количество простых чисел в последовательности бесконечным, еще не решен.

Но отвлечемся немного от серьезных научных изысканий и займемся небольшим, но забавным фокусом, основанным на магии чисел Фибоначчи.

В 1 и 2 рядах таблицы напишите два любых числа от 1 до 10. Сложите их, а сумму запишите в 3 ряду. Затем сложите числа из 2 и 3 рядов. Результат запишите в 4 ряд. Продолжайте так делать (ряд 3 + ряд 4 = ряд 5 и т. п.), пока не дойдете до конца таблицы. У вас получится свой вариант последовательности Фибоначчи. А теперь разделите число из 10 ряда на число из 9 ряда. Из результата вам нужны первые три цифры, включая те, которые идут после запятой. В нашем примере из них оставляем 1,61. Хотите – верьте, хотите – нет, но, с каких бы двух положительных (необязательно целых и даже необязательно из промежутка от 1 до 10) чисел в 1 и 2 рядах вы ни начали, частным при делении числа 10 ряда на число 9 ряда всегда будет 1,61. Попробуйте сами разок-другой и легко в этом убедитесь.