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

Причем все значения fn дублируют числа последовательности Фибоначчи и будут и дальше их дублировать с увеличением значения n. Причина в том, что это и есть последовательность Фибоначчи, только в несколько измененном виде – с небольшим смещением. Обратите внимание, что f1 = 1 = F2, f2 = 2 = F3, f3 = 3 = F4 и т. д. (для удобства договоримся, что f0 = F1 = 1, а f–1 = F0 = 0). Обобщая, мы можем утверждать, что при n ≥ 1

А так как мы с вами уже знаем, что означают числа последовательности, мы с их помощью можем доказать состоятельность многих и многих других удивительных закономерностей. Возьмем, к примеру, ту из них, о которой мы говорили в конце главы 4, когда просчитывали диагонали Паскалева треугольника:

Так, восьмая диагональ дает нам

С точки зрения «подсчета комбинаций» это значит, что

Чтобы понять суть этой закономерности, попробуем ответить на один вопрос двумя различными способами.

Вопрос: Сколько существует возможных комбинаций единиц и двоек, дающих в сумме 8?

Ответ номер один: Судя по тому, о чем мы говорили чуть выше, – f8 = F9.

Ответ номер два: Представим себе эту проблему как 5 частных задач, в основе каждой из которых лежит количество двоек в комбинации. Сколько комбинаций обойдется вообще без двоек? Разумеется, только одна – 11111111. И поэтому совсем не случайно, что

С одной двойкой? Уже семь: 2111111, 1211111, 1121111, 1112111, 1111211, 1111121, 1111112. Каждая из них состоит из семи цифр, и, смещая двойку шаг за шагом, получаем

С двумя двойками (скажем, 221111)? Не будем перечислять их все, просто отметим, что любая из них будет состоять из двух двоек и четырех единиц, то есть всего из шести цифр, что дает нам возможных местоположений двоек. По той же логике комбинации с тремя двойками будут включать в себя две единицы и состоять из 5 цифр, а общее их количество будет равняться И наконец, из четырех двоек у нас получится всего одна комбинация (а именно 2222), потому что

Оба ответа отлично проясняют всю ситуацию. И заодно объясняют, почему сумма чисел n-ной диагонали треугольника Паскаля равна одному из чисел последовательности Фибоначчи. То есть при n ≥ 0 сложение чисел диагонали n (вплоть до того момента, пока через n/2 шагов мы не выйдем за границы треугольника) дает нам

К тому же можно прийти, представив последовательность Фибоначчи в виде плиток черепицы. Тогда f4 = 5 означает 5 способов выложить один ряд (условно состоящий из 4 квадратов) одинарными (в виде квадратов) и двойными (в виде прямоугольников) плитками. То есть 1 + 1 + 2 будет выглядеть как «квадрат – квадрат – прямоугольник».

Такую визуализацию можно использовать, чтобы понять другие закономерности, основанные на числах Фибоначчи. Давайте посмотрим, что произойдет, если возвести числа Фибоначчи в квадрат.

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

Попробуем объяснить эту закономерность с точки зрения счета. Последнее уравнение утверждает, что

Почему? Ответим на простой вопрос.

Вопрос: Сколькими способами можно выложить из квадратов и прямоугольников ряд длиной в 10 квадратов?

Ответ 1: Естественно, f10. Вот один из вариантов – визуализация суммы 2 + 1 + 1 + 2 + 1 + 2 + 1.

То есть разрывы между плитками у нас будут после 2, 3, 4, 6, 7, 9 и 10 квадратов (попросту – везде, кроме центральной оси прямоугольников, в нашем примере – это после 1, 5 и 8 квадратов).

Ответ 2: Решим две задачи: сначала посчитаем варианты кладки, в которых будет разрыв после 5 квадрата (то есть ряд можно разделить пополам), потом те, где разрыва в этом месте не будет (и ряд будет разделяться на две неравные части). Начнем с первого. Левую часть можно выложить f5 = 8 способами. Обе части равны, значит, и правую можно выложить f5 = 8 способами. Согласно закону произведения (см. главу 4), мы можем представить общую сумму способов как f5² = 8², как показано ниже:

Теперь посчитаем те варианты, в которых разрыва в центре нет, зато мы точно знаем, что 5 и 6 квадраты закрыты прямоугольником (как нарисовано ниже). В таком случае части ряда как слева, так и справа от центрального прямоугольника можно выложить f4 = 5 способами, значит, всего получается f4² = 5². Сводим вместе оба варианта и получаем, что f10 = f5² + f4², что и требовалось.

На уровне обобщений же трюк с разделением панелей длиной 2n квадратов на два типа в зависимости от того, есть ли у них по центру разрыв или нет, приводит нас к очень красивой закономерности –

Возьмем только что рассмотренную закономерность и попробуем использовать ее в похожих примерах. Скажем, сколько будет способов выложить плиткой ряд протяженностью m + n? Сначала – те варианты кладки, в которых будет разрыв после квадрата m. Левую часть можно выложить fm способами, правую – fn способами, то есть всего их fm fn. Теперь – варианты кладки без разрыва после квадрата m. Прямоугольник тогда покрывает квадраты m и m + 1, остальные же можно выложить fm–1 fn–1 способами. В итоге у нас получается весьма полезная формула при m, n ≥ 0.

А теперь рассмотрим другой пример. Что получится, если суммировать квадраты всех чисел Фибоначчи?

Ух ты! Здо́рово, правда? Сумма квадратов есть произведение двух последних чисел! Но зачем прибавлять сумму квадратов 1, 1, 2, 3, 5 и 8 к произведению 8 × 13? Лучший способ визуализировать это – взять шесть квадратов со сторонами 1, 1, 2, 3, 5 и 8 и расположить их так, как показано на схеме.

Берем один квадрат 1 на 1. Рядом с ним помещаем второй такой же. Получается прямоугольник 1 на 2. Под ним располагаем квадрат 2 на 2, и наш прямоугольник вырастает до 3 на 2. К его более длинной грани прибавляем квадрат 3 на 3 (получается прямоугольник 3 на 5); квадрат 5 на 5 отправляется вниз (получая прямоугольник 8 на 5), и, наконец, чертим самый большой квадрат, 8 на 8, тем самым заканчивая и прямоугольник 8 на 13. А теперь – простой вопрос.

Вопрос: Какова площадь большого прямоугольника?

Ответ 1: С одной стороны, это будет сумма площадей всех входящих в него квадратов, то есть 1² + 1² + 2² + 3² + 5² + 8².

Ответ 2: С другой стороны, высота большого прямоугольника равняется 8, длина же – 5 + 8 = 13, а значит, площадь – 8 × 13.

Так как оба эти ответа логически верны, они должны приводить нас к одному и тому же результату, который объяснит наше тождество. По большому счету, то, как мы строили этот прямоугольник, уже его объясняет – вместе со всеми отношениями между входящими в нее числами (я имею в виду 1² + 1² + 2² + 3² + 5² = 5 × 8). И если следовать этой логике и дальше, мы расширим наш прямоугольник сначала до 13 × 21, потом до 21 × 34 и т. д. до бесконечности. Общая формула выглядит так:

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

Ответ 2: С другой стороны, высота большого прямоугольника равняется 8, длина же – 5 + 8 = 13, а значит, площадь – 8 × 13.

Так как оба эти ответа логически верны, они должны приводить нас к одному и тому же результату, который объяснит наше тождество. По большому счету, то, как мы строили этот прямоугольник, уже его объясняет – вместе со всеми отношениями между входящими в нее числами (я имею в виду 1² + 1² + 2² + 3² + 5² = 5 × 8). И если следовать этой логике и дальше, мы расширим наш прямоугольник сначала до 13 × 21, потом до 21 × 34 и т. д. до бесконечности. Общая формула выглядит так:

Посмотрим, что произойдет при перемножении двух соседних чисел последовательности Фибоначчи. «Соседями» 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).