Числа Фибоначчи (или последовательность Фибоначчи Fn) обладают целым рядом интересных и важных свойств. К их изучению мы сейчас и приступаем. Итак,
ОПРЕДЕЛЕНИЕ. Последовательность Фибоначчи Fn определяется рекуррентным соотношением:
F0 =0,
F1 =1,
Fn = Fn-1 + Fn-2,……для № > 1.(1)
Несколько первых значений представлены в таблице 1.
Таблица 1
| n | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
| Fn | 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 |
В отличие от многих знаменитых в математике чисел (например, гармонических чисел, чисел Бернулли и т. д.), числа Фибоначчи являют собой подкупающие своей бесхитростностью целые числа. Бесхитростность правила образования этих чисел – возможно, самого бесхитростного из всевозможных рекуррентных соотношений, в котором каждое число зависит от двух предыдущих – служит объяснением того, почему числа Фибоначчи встречаются в самых разнообразных ситуациях.
Простоту и естественность возникновения можно считать первым свойством чисел Фибоначчи. И по мере накопления информации о числах Фибоначчи эта простота становится только таинственней и привлекательней.
Одним из самых первых фактов о числах Фибоначчи, обнаруженным в 1680 г. французским астрономом Жан-Домиником Кассини, является соотношение:
Fn+1 Fn-1 – Fn2 = (-1)n при № > 0.(2)
Так, при № = 6 соотношение Кассини справедливо утверждает, что 13x5 – 82 = 1.(Этот закон был известен Иоганну Кеплеру еще в 1608 г.)
Многочленная формула, которая включает в себя числа Фибоначчи вида Fn±k при малых k, может быть преобразована в формулу, которая включает в себя только Fn и Fn+1, если воспользоваться правилом
Fm = Fm+2 – Fm+1 (3)
для выражения Fm через большие числа Фибоначчи при m < n, и если воспользоваться формулой
Fm = Fm-2 + Fm-1 (4)
для замены Fm меньшими числами Фибоначчи при m > n+1.Так, например, можно заменить Fn-i на Fn+1 – Fn в (2), получая соотношение Кассини вида:
Fn+12 – Fn+1Fn – Fn2 = (-1)n. (5)
Кроме того, если заменить № на № + 1, то соотношение Кассини принимает вид:
Fn+2Fn – Fn+12 = (-1)n+1;
это то же самое, что и (Fn+1 +Fn)Fn – Fn+12 = (– 1)n+1, а последнее совпадает с (5). Таким образом "Кассини(n)" справедливо тогда и только тогда, когда справедливо "Кассини (n + 1)" так что по индукции равенство (2) справедливо при любом n.
Соотношение Кассини лежит в основе геометрического парадокса, который был одной из излюбленных головоломок Льюиса Кэррола. Суть его в том, чтобы взять шахматную доску и разрезать ее на четыре части, как показано ниже на рис. 1, а затем составить из этих частей прямоугольник:
Рис. 1.
Первоначальные 8 х 8 = 64 клетки переставлены так, что получилось 5 х 13 = 65 клеток. Аналогичная конструкция расчленяет любой Fn х Fn-квадрат на четыре части с размерами сторон Fn+1, Fn, Fn-1 и Fn-2 клеток вместо соответственно 13, 8, 5, и 3 клеток в нашем примере. В результате получается Fn-1 х Fn+2-прямоугольник, и в соответствии с (2) одна клетка либо прибавляется, либо утрачивается – в зависимости от того, четно или нечетно n.
Строго говоря, мы не можем применять правило (4) кроме как при та m ≥ 2, ибо нами не определены Fn при отрицательном n. Мы обретем большую свободу действий, если избавимся от этого ограничительного условия и воспользуемся правилами (3) и (4) для доопределения чисел Фибоначчи при отрицательных индексах. Так, F-1 оказывается равным F1 – F0 = 1, a F-2 – равным F0 – F-1 = – 1. Действуя таким образом, выписываем величины:
| n | 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 |
| Fn | 0 1 -1 2 -3 5 -8 13 -21 34 -55 89 |
и вскоре становится ясно (по индукции), что
F-n = (-l)n-1Fn, № – целое. (6)
Если обобщить последовательность Фибоначчи подобным образом, то соотношение Кассини (2) будет справедливым при любых целых n, а не только при № > 0.
Процесс сведения Тn±k к комбинации Fn и Fn+1 по правилам (4) и (3) приводит к последовательности формул:
Fn+2 = Fn+1 + Fn, Fn-1 = Fn+1 – Fn,
Fn+3 = 2Fn+1 + Fn, Fn-2 = – Fn+1 + 2Fn,
Fn+4 = 3Fn+1 + 2Fn, Fn-3 = 2Fn+1 – 3Fn,
Fn+5 = 5Fn+1 +3Fn, Fn-4 = – 3Fn+1 +5F,V,
в которой просматривается закономерность другого рода:
Fn+k = FkFn+1 + Fk-1Fn (7)
Это соотношение, которое легко доказывается по индукции, справедливо при любых целых k и № (положительных, отрицательных или равных нулю).
Если в (7) положить k = n, то выясняется, что:
F2n = FnFn+1 + Fn-1Fn; (8)
следовательно, F2n кратно Fn. Аналогично,
F3n = F2n Fn+1 + F2n-1 Fn,
и можно заключить, что F3n также кратно Fn. И, вообще, по индукции:
Fkn кратно Fn (9)
при любых целых k и n. Это объясняет, в частности, почему F15 (которое равно 610) кратно как F3, так и F5 (которые равны 2 и 5). Фактически справедливо даже большее: можно доказать, что:
НОД(Fm, Fn) = FНод(m,n) (10)
К примеру, НОД(F12, F18) = НОД(144,2584) = 8 = F6.
Теперь можно доказать обращение свойства (9): если № > 2 и если Fm кратно Fn, то m кратно n. Действительно, если Fn\Fm, то Fn \ НОД(Fm, Fn) = FНод(m,n) ≤ Fn. А это возможно только тогда, когда FНод(m,n) = Fn и наше допущение о том, что № > 2 приводит к необходимости того, что НОД(m, n) = n. Следовательно, n\m.
Обобщение подобных понятий делимости было использовано Юрием Матиясевичем в его знаменитом доказательстве того, что не существует алгоритма, позволяющего выяснить, разрешимо ли в целых числах заданное полиномиальное уравнение относительно многих неизвестных с целыми коэффициентами. Одна из лемм Матиясевича утверждает следующее.
ЛЕММА МАТИЯСЕВИЧА. Если № > 2, то число Фибоначчи Fm кратно Fn2 тогда и только тогда, когда m кратно nFn.
ДОКАЗАТЕЛЬСТВО. Докажем это, рассмотрев последовательность (Fkn mod Fn2) при k = 1, 2, 3,... № выяснив, когда же Fkn mod Fn2 = 0.(Мы знаем, что m должно иметь вид kn, если Fm mod Fn = 0.) Вначале имеем Fn mod Fn2 = Fn, что не равно нулю. Затем, согласно (6.108), получаем:
F3n = FnFn+1 +Fn-1Fn ≡ 2FnFn+1 (mod Fn2), поскольку Fn+1 ≡ Fn-1 (mod Pn). Аналогично F2n+1 = Fn+12 + Fn2 ≡ Fn+12 (mod Fn2).
Это сравнение позволяет вычислить:
F3n = F2n+1Fn + F2nFn-1
≡ Fn+12Fn + (2FnFn+1)Fn+1 = 3 Fn+12Fn (mod Fn2),
F3n+1 = F2n+1Fn+i + F2nFn
≡ Fn+13 (2FnFn+1) Fn ≡ F3n+1 (mod Fn2)
И вообще индукцией по k устанавливается, что:
Fkn ≡ kFn+1k-1 и Fkn+1 = Fn+1k (mod Fn2).
А поскольку Fn+1 взаимно просто с Fn, то
Fkn ≡ 0 (mod Fn2) kFn ≡ 0 (mod Fn2) k ≡ 0 (mod Fn2)
и лемма Матиясевича доказана.
Одно из наиболее важных качеств чисел Фибоначчи – это особый способ представления целых чисел с их использованием. Будем писать:
j >> k j ≥ k + 2.(11)
Тогда верна следующая
ТЕОРЕМА Цеккендорфа. Каждое целое положительное число имеет единственное представление вида:
n = Fk1, + Fk2+ … + Fkr, k1 > k2 > … > kr > 0.(12)
К примеру, представление одного миллиона оказывается таким:
1 000 000 = 832040 + 121393+46368 + 144+55 = F30 + F26 + F24 + F12 + F10.
Подобное представление всегда может быть найдено с помощью „жадного" подхода: в качестве Fk1, выбирается наибольшее число Фибоначчи ≤ n, затем в качестве Fk2 выбирается наибольшее число ≤ № – Fk1, и т. д. (Более точно, предположим, что Fk ≤ № < Fk+1; тогда 0 ≤ № – Fk < Fk+1 – Fk = Fk-1,. Если № – одно из чисел Фибоначчи, то представление (12) справедливо при r = 1 и k1 = k. В противном случае индукция по № показывает, что № – Fk имеет фибоначчиево представление Fk2 + … + Fkr, и представление (12) справедливо, если положить k1 = k, ибо неравенства Fk2 ≤ № – Fk < Fk-1 означают, что k >> k2.) И обратно, всякое представление вида (12) означает, что:
Fk1 ≤ № < Fk1+1,
поскольку наибольшим возможным значением выражения Fk2 + …+Fkr, когда k >> k2 >> … >> kr >> 0, является:
Fk-2 + Fk-4 +---+ Fk mod2+2 = Fk-1 – 1, если k ≥ 2.(13)
(Эта формула легко доказывается индукцией по k – ее левая часть обращается в нуль при k равном 2 или 3.) Поэтому k1 – это как раз описанная выше, „жадно" выбранная величина, и данное представление должно быть единственным.
Любая система однозначного представления чисел является системой счисления – следовательно, теорема Цеккендорфа приводит к фибоначчиевой системе счисления. Всякое целое неотрицательное число можно представить в виде последовательности нулей и единиц, записав:
n = (bmbm-1... b2)F № = . (14)
Эта система счисления отчасти напоминает двоичное (с основанием 2) представление, за исключением того, что в ней никогда не встречаются две 1 подряд. Вот, к примеру, числа от 1 до 20, представленные по Фибоначчи:
1 = (000001)F 6 = (001001)F 11=(010100)F 16 = (100100)F
2 = (000010)F 7 = (001010)F 12=(010101)F 17 = (100101)F
3 = (000100)F 8 = (010000)F 13 = (100000)F 18 = (101000)F
4 = (000101)F 9 = (010001)F 14 = (100001)F 19 = (101001)F
5 = (001000)F 10 = (010010)F 15 = (100010)F 20 = (101010)F
Фибоначчиево представление одного миллиона, указанное минутой ранее, может быть сопоставлено с его двоичным представлением: 219 + 218 + 217 + 2'6 + 214 + 29 + 26:
(1000000)10=(10001010000000000010100000000)F=(11110100001001000000)2.
Фибоначчиево представление требует несколько больше битов, поскольку не допускаются две 1 подряд – но в остальном оба представления аналогичны. При прибавлении 1 в фибоначчиевой системе счисления возникают два случая. В случае, если „разряд единиц" есть 0, он заменяется на 1 – тем самым прибавляется F2 = 1, ибо разряд единиц связан с F2.В противном случае двумя наименее значащими цифрами будут 01, и они заменяются на 10 (тем самым прибавляя F3 – F2 = 1). Наконец, мы должны „перенести" 1 столько раз, сколько это необходимо, заменяя набор цифр ‘011’ на ‘100’ до тех пор, пока в строке цифр имеются две рядом стоящие 1.(Подобное правило переноса эквивалентно замене Fm+1 + Fm на Fm+2). Так, для того чтобы перейти от 5 = (1000)F к 6 = (1001)F или от 6 = (1001)F к 7 = (1010)F, переносов не требуется, но для того чтобы перейти от 7 = (1010)F к 8 = (10000)F необходимо выполнить перенос дважды.
Несмотря на обилие рассмотренных нами свойств чисел Фибоначчи, мы пока не сталкивались с какой-либо замкнутой формулой для них. Так, нет ли какой-нибудь связи между Fn и другими известными нам величинами? Можно ли "разрешить" рекуррентность, посредством которой определяются числа Fn?
Ответ утвердительный: действительно, существует простой способ решения этой рекуррентности, если воспользоваться понятием производящей функции. Образуем бесконечный ряд:
F(z) =F0+F1z + F2z2 +... = Fnzn. (15)
Если мы сможем найти простую формулу для F(z), то появятся шансы установить простую формулу и для его коэффициентов Fn.
Степенной ряд F(z) обнаруживает одно замечательное свойство, если посмотреть, что происходит при его умножении на z и на z2:
F(z) = F0 + F1z + F2z2 + F3z3 + F4z4 + F5z5 + …,
zF(z) = F0z + F1z2 + F2z3 + F3z4 + F4z5 + …,
z2F(z) = F0z2 + F1z3 + F2z4 + F3z5 + ….
Если теперь вычесть два последних равенства из первого, то члены, включающие z2, z3 и большие степени z, пропадут – в силу фибоначчиевой рекуррентности. К тому же постоянный член F0 на самом деле никогда не оказывается первым, поскольку F0 = 0. Следовательно, все, что остается после вычитания – это (F1 – F0)z, т. е. просто z. Другими словами,
F(z) – z F(z) – z2F(z) =z,
и решение F(z) получается в виде компактной формулы:
F(z) = z / (1 – z – z2). (16)
Итак, вся информация, содержащаяся в последовательности Фибоначчи, свернута в несложное (хотя и непонятное) выражение z/(1 – z – z2). Теперь знаменатель можно разложить на множители, а затем воспользоваться элементарными дробями для получения формулы, которую легко разложить в степенной ряд. А коэффициенты этого степенного ряда дадут выражение для чисел Фибоначчи в замкнутой форме.
Выть может, план действия, который мы только набросали, будет понятнее, если подойти к нему с другого конца. Если имеется какая-нибудь более простая производящая функция – скажем, 1/(1 – α z), где α – некоторая константа, то нам известны коэффициенты при всех степенях z, поскольку:
1/(1 – α z) = 1 + α z + α2 z2 + α3 z3 + ….
Аналогично, если имеется некоторая производящая функция вида:
А/(1 – α z) + В/(1 – β z),
то коэффициенты также легко вычисляются, ибо:
А/(1 – α z) + В/(1 – β z) = A (α z)n + (β zn) = (A αn + B βn)zn. (17)
Следовательно, все, что от нас требуется – это найти константы А, В, α и β, такие, что:
1/(1 – α z) + В/(1 – β z) = z / (1 – z – z2),
и тогда будет получено выражение в замкнутой форме A αn + B βn для коэффициента Fn при zn в разложении F(z). Левая часть может быть переписана как:
1/(1 – α z) + В/(1 – β z) = (A – A β z – B – B α z) +) / [(1 – α z) (1 – β z)],
так что интересующие нас четыре константы являются решениями двух полиномиальных уравнений:
(1 – α z) (1 – β z) = 1 – z – z2; (18)
(A + B) – (A β – B α) z = z. (19)
Мы хотим представить знаменатель F(z) в форме произведения (1 – α z) (1 – β z) – тогда появится возможность выразить F(z) в виде суммы двух дробей, в которых сомножители (1 – α z) и (1 – β z) удачно отделены друг от друга.
Обратим внимание на то, что сомножители в знаменателе уравнения (18) записаны в виде (1 – α z) (1 – β z), а не в более привычной форме c(z – ρ1)(z – ρ2), где ρ1 и ρ2 – некоторые корни. Дело в том, что запись (1 – α z) (1 – β z) приводит к более привлекательным разложениям в степенные ряды.
Величины α и β могут быть найдены несколькими способами, в одном из которых используется тонкая уловка. Введем новую переменную w и попробуем найти разложение вида:
w2 – w z – z2 = (w – α z) (w – β z).
Тогда мы сможем просто положить w = 1 и получить разложение 1 – z – z2.Корни уравнения w2 – w z – z2 = 0 могут быть найдены по формуле решения квадратного уравнения – они равны:
(z ± )/2 = z.
Следовательно,
w2 – w z – z2 = (w – z) (w – z)
и искомые константы α и β получены.
Число (1 + )/2 ≈ 1.61803 играет важную роль во многих разделах математики. Оно имеет специальное название – отношение золотого сечения и обозначается греческой буквой Ф. Другой корень, (1 – )/2 = – 1/Ф ≈ – . 61803, обладает многими свойствами числа Ф, поэтому и он имеет специальное обозначение Ф – "фи с крышкой" А оба эти числа являются корнями уравнения w2 – w – 1 =0, так что:
Ф2 = Ф + 1, Ф2 = Ф + 1.(20)
Итак, найдены константы α = Ф и β = Ф, необходимые в (6.119); теперь нужно лишь установить А и B в (19). Подстановка z = 0 в это уравнение показывает, что В = – А, так что (19) сводится к уравнению:
– ФА + ФА = 1,
решением которого является А = 1/(Ф – Ф) = 1/ . Следовательно, разложение (6.117) на элементарные дроби имеет вид:
F(z) = ( – ) / (21)
Итак: F(z) получено в той форме, что и хотелось. А разложение дробей в степенные ряды, как в (17), доставляет выражение в замкнутой форме для коэффициента при zn:
Fn = (Фn – Фn) / . (22)
(Эта формула впервые опубликована Даниэлем Бернулли в 1728 г., но о ней позабыли до 1843 г., пока она не была вновь открыта Жаком Бине.)
Следует еще проверить правильность вывода. При № = 0 данная формула правильно дает F0 = 0, а при № = 1 она дает F1 = (Ф – Ф)/ , что, действительно, равно 1. При больших № уравнения (20) показывают, что числа, определенные формулой (22), удовлетворяют фибоначчиевой рекуррентности, так что по индукции они должны быть числами Фибоначчи. (Мы могли бы также разложить Фn и Фn в соответствии с биномиальной теоремой и избавиться от различных степеней , но это приводит к изрядной путанице. Смысл выражения в замкнутой форме не обязательно состоит в том, чтобы обеспечить нас методом быстрого вычисления, а скорее в том, чтобы указать, как Fn связано с другими математическими величинами.)
Проявив некоторую смекалку, можно было бы просто угадать формулу (22) и доказать ее по индукции. Однако, так называемый, метод производящих функций является действенным способом именно ее нахождения. Между прочим, мы нисколько не беспокоились, сходятся ли бесконечные суммы в нашем выводе формулы (22) – оказывается, что большинство операций с коэффициентами степенного ряда может быть строго обосновано независимо от того, сходятся или нет данные суммы в действительности, но это другая тема. Тем не менее, после того, как уравнение (22) найдено с использованием бесконечного ряда, оно может быть проверено путем надежного доказательства по индукции.
Одним из интересных следствий формулы (22) является то, что целое число Fn чрезвычайно близко к иррациональному числу Фn / при большом n. (Поскольку Ф по абсолютной величине меньше 1, то величина Фn убывает экспоненциально и ее влияние почти несущественно.) К примеру, числа F10 = 55 и F11 = 89 очень близки к числам:
= ≈ 55.00364 и ≈ 88.99775.
Этим наблюдением можно воспользоваться для вывода другого выражения в замкнутой форме,
Fn = [ + ] = , округленное до ближайшего целого, (23)
ибо |Фn/ | < при любом № ≥ 0. Если № четно, то Fn немного меньше, чем Фn/ ; в противном случае оно немного больше. Соотношение Кассини (2) может быть переписано как:
.
При большом № величина 1/(Fn-1Fn) весьма мала, так что отношение Fn+1/Fn должно быть почти тем же самым, что и отношение Fn/Fn-1, a (23) указывает на то, что это отношение приближает Ф. И в самом деле,
Fn+1 = Ф Fn + Фn. (24)
(Это соотношение непосредственно проверяется при № = 0 и № = 1, а при № > 1 доказывается по индукции; оно может быть также доказано непосредственно подстановкой в формулу (22).) Отношение Fn+1/Fn весьма близко к числу Ф, которое оно приближает попеременно то с избытком, то с недостатком.
Кроме того, в силу простого совпадения, число Ф довольно близко к числу километров в одной миле. (Точное число равно 1.609344, поскольку один дюйм равен в точности 2.54 сантиметрам.) Это дает нам удобный способ перевода в уме километров в мили и обратно, ибо расстояние в Fn+1 километров равно (довольно близко) расстоянию в Fn миль.
Предположим, что мы хотим перевести некоторое число (не являющееся числом Фибоначчи) километров в мили – сколько будет 30 км по-американски? Это делается легко: мы просто прибегаем к фибоначчиевой системе счисления и переводим в уме число 30 в его фибоначчиево представление 21 +8 + 1 с помощью объясненного выше "жадного" подхода. Теперь можно сдвинуть каждое число на одну позицию вправо, получая 13+5 + 1.(Первоначальная "1" была числом F2, поскольку kr >> 0 в (12); новая же "1" – это F1). Сдвиг вправо практически равносилен делению на Ф. Следовательно, наша оценка – 19 миль. (Это довольно точная оценка: правильный ответ – около 18.64 миль.) Аналогично, для перехода от миль к километрам можно осуществить сдвиг на одну позицию влево: 30 миль – это примерно 34 + 13 + 2 = 49 километров. (Это уже не столь точная оценка: правильное число – около 48.28.)
Оказывается, что подобное правило „сдвига вправо" дает правильно округленное число миль в № километрах при всех № ≤ 100, за исключением случаев № = 4, 12, 54, 62, 75, 83, 91, 96 и 99, когда оно отличается меньше чем на 2/3 мили. А правило "сдвига влево" дает либо правильно округленное число километров в и милях, либо на 1 км больше, при всех № ≤ 113.(Единственный, действительно нарушающий данное правило случай – это № = 4, когда отдельные ошибки округления для № = 3 +1 накладываются друг на друга, вместо того, чтобы компенсировать друг друга).
Приведем еще несколько свойств чисел Фибоначчи.
1.Вычислим сумму первых № чисел Фибоначчи. Именно, докажем, что:
U1+U2+…+Un=Un+2-1 (24)
В самом деле, мы имеем:
U1=U3-U2,
U2=U4-U3,
U3=U5-U4,
…………..
Un-1=Un+1-Un,
Un=Un+2-Un+1.
Сложив все эти равенства почленно, мы получим: U1+U2+…+Un=Un+2-U2,
И нам остается вспомнить, что U2=1.
2. Сумма чисел Фибоначчи с нечетными номерами:
U1+U3+U5+…+U2n-1=U2n. (25)
Для доказательства этого равенства напишем:
U1=U2,
U3=U4-U2,
U5=U6-U4,
…………..
U2n-1=U2n-U2n-2.
Сложив эти равенства почленно, мы и получим требуемое свойство.
3. Сумма чисел Фибоначчи с четными номерами:
U2+U4+…+U2n=U2n+1-1 (26)
На основании п. 1 мы имеем:
U1+U2+U3+…+U2n=U2n+2-1;
вычитая почленно из этого равенства, равенство (25) мы получим:
U2+U4+…+U2n=U2n+2-1-U2n=U2n+1-1,
а это нам и требовалось.
Вычитая, далее, почленно (26) из (25), получаем:
U1-U2+U3-U4+…+U2n-1-U2n=-U2n-1+1 (27)
Прибавим теперь к обеим частям (27) по U2n+1:
U1-U2+U3-U4+…+(-U2n)+U2n+1=U2n+1 (28)
Объединяя (27) и (28), получаем выражение для знакопеременной суммы чисел Фибоначчи.
U1-U2+U3-U4+…+(-1)n+1Un=(-1)n+1Un-1+1 (29)
4. Формулы (24) и (25) были выведены при помощи почленного сложения целой серии очевидных равенств. Еще одним примером применения этого приема может служить вывод формулы для суммы квадратов первых № чисел Фибоначчи:
U12+U22+…+Un2= UnUn+1 (30)
Сложив равенства
U12=U1U2,
U22=U2U3-U1U2,
U32=U3U4-U2U3,
…………………
Un2=UnUn+1-Un-1Un,
почленно мы получаем формулу (30).
5. Многие соотношения между числами Фибоначчи удобно доказывать при помощи метода полной индукции. Сущность метода полной индукции (называемого часто методом математической индукции) состоит в следующем: для доказательства, что некоторое утверждение справедливо для всякого натурального числа, достаточно установить, что:
а) оно имеет место для числа 1;
б) из справедливости доказываемого утверждения, для какого-либо произвольно – выбранного натурального числа № следует его справедливость для числа n+1.
Всякое индуктивное доказательство утверждения, справедливого для любого натурального числа, состоит, поэтому из двух частей.
В первой части устанавливается справедливость доказываемого утверждения для единицы, ее называют иногда основанием индукции. Во второй части доказательства делается предположение о справедливости доказываемого утверждения для некоторого произвольного (но фиксированного) числа № и из этого предположения, которое часто называют индуктивным предположением, выводится, что и для числа n+1 доказываемого утверждение имеет место.
Вторая часть доказательства называется индуктивным переходом. Иногда применяется индуктивное рассуждение, которое можно назвать переходом "от всех чисел, меньших n, к n". При этом необходимость в специальном доказательстве основания индукции отпадают, так как, говоря формально, доказательство для случая n+1 и есть переход от "всех" целых положительных чисел, меньших единицы (которых просто нет), к единице. Именно таким является доказательство возможности разложения любого натурального числа на простые множители.
Предположим, что каждое из чисел, меньших некоторого n, разложимо в произведение простых множителей.
Если число № оказывается простым, то оно само и является своим разложением.
Если же число № составное, то его по определению, можно представить в виде произведения хотя бы двух сомножителей: n=n1n2, где n1 ≠ 1 и n2 ≠ 1.
Но тогда n1>n и n2<n,а по индуктивному предположению как n1, так и n2 разлагаются на простые множители. Тем самым и № разложимо на простые множители.
6. Простейшей реализацией идеи индукции в применении к числам Фибоначчи является само определение чисел Фибоначчи. Оно состоит в указании двух первых чисел Фибоначчи: U1=1 и U2=1 и в индуктивном переходе от Un и Un+1 к Un+2, даваемым рекуррентным соотношением : Un+Un+1=Un+2.В частности, отсюда автоматически следует, что если некоторая последовательность чисел начинается с двух единиц, а каждое из следующих получается сложением двух предыдущих, то эта последовательность является последовательностью чисел Фибоначчи.
В качестве примера рассмотрим так называемую "задачу о прыгуне". Она состоит в следующем.
"Задача о прыгуне". Прыгун может прыгать в одном направлении вдоль разделенной на клетки полосы, перемещаясь при каждом прыжке либо в соседнюю клетку, либо через клетку. Сколькими способами может он сдвинуться на n-1 клетку и, в частности, переместиться из первой клетки в n-ю? (Способы прыганья считаются одинаковыми, если в ходе каждого из них прыгун побывает в одних и тех же клетках). Обозначим искомое число через хn. Очевидно х1=1(ибо переход из первой клетки в первую же осуществляется только одним способом-отсутствием прыжков) и х2=1 (переход из первой клетки во вторую также единствен: он состоит в одном непосредственном прыжке на соседнюю клетку). Пусть целью прыгуна является достижение n+2-й клетки. Общее число способов осуществление этой цели в наших обозначениях равно хn+2.Но с самого начала эти способы разбиваются на два класса: начинающиеся с прыжка во вторую клетку и начинающиеся с прыжка в третью клетку. Из второй клетки прыгун может переместиться в n+2-ю хn+1 способами, а из третьей хn способами.
Таким образом, последовательность чисел х1, х2,…, хn,…удовлетворяет рекуррентному соотношению:
xn+хn+1=хn+2 и поэтому совпадает с последовательностью чисел Фибоначчи хn=Un.
7. Докажем по индукции следующую важную формулу:
Un+m=Un-1Um+UnUm+1.(31)
Доказательство этой формулы будем вести индукцией по m.
При m=1 эта формула принимает вид:
Un+1=Un-1U1+UnU2, что очевидно.
При m=2 формула (31) также верна, потому что
Un+2=Un-1U2+UnU3=Un-1+2Un=Un-1+Un +Un=Un+1+Un.
Основание индукции, таким образом, доказано.
8.Полагая в формуле (31) m = n, мы получаем
U2n=Un-1Un+UnUn+1,
или
U2n=Un(Un-1+Un+1) (32)
Из написанного равенства видно, что U2n делится на Un.
Так как Un=Un+1-Un-1, формулу (32) можно переписать так:
U2n=(Un+1-Un-1) =(Un+1+Un-1), или
U2n= U2n+1-U 2n-1, т. е. разность квадратов двух чисел Фибоначчи, номера которых отличаются на два, есть снова число Фибоначчи (и причем с четным номером).
Аналогично(полагая m=2n) можно показать, что
U3n=U3n+1+U3n-U3n-1.
9.В дальнейшем нам пригодиться следующая формула:
U2n = Un-1Un+1+(-1)n+1 (33)
Докажем ее индукцией по n.
Для n=2, формула (33) принимает вид:
U22=U1U3-1,
что очевидно.
Предположим теперь в формулу (33) доказанной для некоторого n, прибавим к обеим частям ее по UnUn+1. Получим
U2n+UnUn+1= Un-1Un+1+ UnUn+1+(-1)n+1,
Или
Un (Un+Un+1)= Un+1(Un-1+Un)+(-1)n+1,
Или
Un Un+2= U2n+1+(-1)n+1,
Или
U2n+1= Un Un+2+(-1)n+2,
Этим индуктивный переход обоснован и формула (33) доказана для любого n.
10. Аналогичным способом можно установить такие свойства чисел Фибоначчи:
U1U2+U2U3+U3U4+…+U2n-1U2n=U22n.
U1U2+U2U3+U3U4+…+U2nU2n+1=U22n+1-1.
nU1+(n-1)U2+(n-2)U3+…+2Un-1+Un=Un+4-(n+3)
U1+2U2+3U3+…+nUm=nUn+2-Un+3+2
11. До сих пор мы определяли числа Фибоначчи рекуррентно, т. е. индуктивно, по их номеру. Оказывается, что любое число Фибоначчи можно определить и непосредственно, как некоторую функцию его номера.
Исследуем для этого различные последовательности U1, U2, U3, …., Un,…, удовлетворяющие соотношению
Un=Un-2+Un-1 (34)
Все такие последовательности мы будем называть решениями уравнения (34)
Будем обозначать буквами V,V`, V`` соответственно последовательности:
w1,w2,w3,…
w1`,w2`,w3`,…
w1``,w2``,w3``,…
Сначала докажем две леммы.
ЛЕММА 1.
Если V – есть решение уравнения (34), а c – произвольное число, то последовательность cV (т. е. последовательность cw1,cw2,cw3,…) есть так же решение уравнения (11)
ДОКАЗАТЕЛЬСТВО: Умножив соотношение wn=wn-2+wn-1 почленно на c, получаем cwn=cwn-2+cwn-1, а это и требовалось доказать.
ЛЕММА 2.
Если последовательности V`и V`` являются решениями уравнения (34), то и их сумма V`+ V`` (т. е. последовательность w`1+w``1, w2`+w2``, w3` +w3``) является решением уравнения (11)
ДОКАЗАТЕЛЬСТВО: Из условия леммы мы имеем:
w`n=w`n-2+w`n-1
и
w``n=w``n-2+w``n-1
Сложив эти два равенства почленно, получим:
w`n +w``n= (w`n-2+w``n-2)+(w`n-1+w``n-1).
Этим лемма доказана.
Из этих лемм также выводится знаменитая формула Бине:
Рассмотрим теперь некоторые свойства чисел Фибоначчи, касающиеся их делимости. Докажем следующую теорему.
ТЕОРЕМА. Если № делиться на m, то и Un делиться на Um.
ДОКАЗАТЕЛЬСТВО:
Пусть № делиться на m, т. е. № = mk. Будем вести доказательство индукцией по k.
Для k=1, № = m, так что в этом случае Un делиться на Um очевидным образом. Предположим теперь что Umk делиться на Um и рассмотрим Um(k+1). Тогда имеем: Um(k+1) = Umk+m и на основании формулы (31) получим:
Um(k+1) = Umk+m= Umk-1Um+ UmkUm+1
Первое слагаемое правой части написанного равенства, очевидно, делиться на Um. Второе же его слагаемое кратно Umk т. е. по индуктивному предположению тоже делиться на Um. Значит, на Um делиться и их сумма, т. е. Um(k+1). Теорема доказана.
Большой интерес представляет вопрос об арифметической природе чисел Фибоначчи, об их делителях.
Докажем, что при № составном и отличном от 4 Un есть составное число. Действительно, для такого № можно написать n=n1n2, где 1<n1<n,
1<n2<n, либо n1>2, либо n2>2. Пусть для определенности n1>2. Тогда ввиду только что доказанный теоремы Un делиться на Un1 причем 1<Un1<Un, а это и означает, что Un – составное число.
Существует огромное количество различных обобщений чисел Фибоначчи. Одним из наиболее интересных является гипотенузный ряд Шишкова.
Существует связь между теоремой Пифагора и числами Фибоначчи.
С2+B2=A2 – теорема Пифагора.
Поместим для наглядности рядом числа Фибоначчи:
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4161 6765...
Полагая, что числа Фибоначчи непосредственно связаны с прямоугольными треугольниками, берем попарно суммы, состоящие из квадратов чисел Фибоначчи, и находим в этом же ряду соответствующее число, равное квадрату гипотенузы, или сумме двух возведенных в квадрат чисел Фибоначчи. Эти числа, равные квадрату гипотенузы, сумме двух возведенных в квадрат катетов, подчеркнуты в ряду Фибоначчи чертой. Эти подчеркнутые числа Ф являются и квадратом гипотенузы ранее расположенных катетов, и, одновременно, катетами, квадрат гипотенузы которых расположен дальше в ряду Фибоначчи.
Примеры: 12+12 =2; 12 +22=5; 22 +32=13 и т. д.
Таким образом числа Фибоначчи характеризуют не только золотое сечение, но и прямоугольные треугольники.
Золотое сечение
Иоганн Кеплер говорил, что геометрия владеет двумя сокровищами – теоремой Пифагора и золотым сечением. И если первое из этих двух сокровищ можно сравнить с мерой золота, то второе с драгоценным камнем.
Теорему Пифагора знает каждый школьник, а что такое золотое сечение – далеко не все. Так что же такое золотое сечение, и какая существует связь между ним и числами Фибоначчи?
Как уже упоминалось в разделе 2, число (1 + )/2 ≈ 1.61803 играет важную роль во многих разделах математики, равно как и в мире искусств, где с античных времен оно рассматривалось как эстетически самое благоприятное отношение. Поэтому оно имеет специальное название – отношение золотого сечения и обозначается греческой буквой Ф в честь Фидия, который, как утверждается, сознательно использовал его в своих скульптурах. Связь этого числа с числами Фибоначчи устанавливается посредством Формулы Бине (или точнее, формулы Бернулли-Бине):
F(z) = ( – ) / .
Однако, есть и другой – геометрический – подход к определению золотого сечения. Через золотое сечение числа Фибоначчи проявляют свои свойства в самых различных сферах. Многие наблюдаемые закономерности в этой области до сих пор не объяснены наукой. Но знать о них должен каждый исследователь.
Человек различает окружающие его предметы по форме. Интерес к форме какого-либо предмета может быть продиктован жизненной необходимостью, а может быть вызван красотой формы. Форма, в основе построения которой лежат сочетание симметрии и золотого сечения, способствует наилучшему зрительному восприятию и появлению ощущения красоты и гармонии. Целое всегда состоит из частей, части разной величины находятся в определенном отношении друг к другу и к целому. Принцип золотого сечения – высшее проявление структурного и функционального совершенства целого и его частей в искусстве, науке, технике и природе.
Золотое сечение – гармоническая пропорция. В математике пропорцией называют равенство двух отношений: a : b = c : d.
Отрезок АВ можно разделить точкой C на две части следующими способами:
1) на две равные части АВ: АC = АВ: ВC;
2) на две неравные части в любом отношении (такие части пропорции не образуют);
3) таким образом, когда АВ: АC = АC: ВC.
Последнее и есть золотое сечение или деление отрезка в крайнем и среднем отношении.
Золотое сечение – это такое пропорциональное деление отрезка на неравные части, при котором весь отрезок так относится к большей части, как сама большая часть относится к меньшей; или другими словами, меньший отрезок так относится к большему, как больший ко всему.
a : b = b: c или с: b = b: а.
Pис. 2. Геометрическое изображение золотой пропорции
Если c принять за единицу, то отрезки золотой пропорции выражаются бесконечными иррациональными дробями b = 0,618..., a = 0,382... Как мы уже знаем, числа 0.618 и 0.382 являются коэффициентами последовательности Фибоначчи. На этой пропорции базируются основные геометрические фигуры.
Прямоугольник с таким отношением сторон стали называть золотым прямоугольником. Он также обладает интересными свойствами. Если от него отрезать квадрат, то останется вновь золотой прямоугольник. Этот процесс можно продолжать до бесконечности. А если провести диагональ первого и второго прямоугольника, то точка их пересечения будет принадлежать всем получаемым золотым прямоугольникам.
Разумеется, есть и золотой треугольник. Это равнобедренный треугольник, у которого отношение длины боковой стороны к длине основания равняется 1.618.
Pис. 3. Золотой треугольник
Есть и золотой кубоид – это прямоугольный параллелепипед с ребрами, имеющими длины 1.618, 1 и 0.618.
В звездчатом пятиугольнике каждая из пяти линий, составляющих эту фигуру, делит другую в отношении золотого сечения, а концы звезды являются золотыми треугольниками.
Pис. 4. Построение правильного пятиугольника и пентаграммы
Принято считать, что понятие о золотом делении ввел в научный обиход Пифагор, древнегреческий философ и математик (VI в. до н. э.). Есть предположение, что Пифагор свое знание золотого деления позаимствовал у египтян и вавилонян. И действительно, пропорции пирамиды Хеопса, храмов, барельефов, предметов быта и украшений из гробницы Тутанхамона свидетельствуют, что египетские мастера пользовались соотношениями золотого деления при их создании.
Французский архитектор Ле Корбюзье нашел, что в рельефе из храма фараона Cети I в Абидосе и в рельефе, изображающем фараона Pамзеса, пропорции фигур соответствуют величинам золотого деления. Зодчий Хесира, изображенный на рельефе деревянной доски из гробницы его имени, держит в руках измерительные инструменты, в которых зафиксированы пропорции золотого деления.
Греки были искусными геометрами. Даже арифметике обучали своих детей при помощи геометрических фигур. Kвадрат Пифагора и диагональ этого квадрата были основанием для построения динамических прямоугольников.
Pис. 5. Динамические прямоугольники
Платон (427-347 гг. до н. э.) также знал о золотом делении. Его диалог "Тимей" посвящен математическим и эстетическим воззрениям школы Пифагора и, в частности, вопросам золотого деления.
В фасаде древнегреческого храма Парфенона присутствуют золотые пропорции. При его раскопках обнаружены циркули, которыми пользовались архитекторы и скульпторы античного мира. В Помпейском циркуле (музей в Неаполе) также заложены пропорции золотого деления.
Pис. 6. Античный циркуль золотого сечения
В дошедшей до нас античной литературе золотое деление впервые упоминается в "Началах" Евклида. Во 2-й книге "Начал" дается геометрическое построение золотого деления. После Евклида исследованием золотого деления занимались Гипсикл (II в. до н. э.), Папп (III в. н. э.) и др. В средневековой Европе с золотым делением познакомились по арабским переводам "Начал" Евклида. Переводчик Дж. Kампано из Наварры (III в.) сделал к переводу комментарии. Секреты золотого деления ревностно оберегались, хранились в строгой тайне, они были известны только посвященным.
В эпоху Возрождения усиливается интерес к золотому делению среди ученых и художников в связи с его применением, как в геометрии, так и в искусстве, особенно в архитектуре. Леонардо да Винчи, художник и ученый, видел, что у итальянских художников эмпирический опыт большой, а знаний мало. Он задумал и начал писать книгу по геометрии, но в это время появилась книга монаха Луки Пачоли, и Леонардо оставил свою затею. По мнению современников и историков науки, Лука Пачоли был настоящим светилом, величайшим математиком Италии в период между Фибоначчи и Галилеем. Лука Пачоли был учеником художника Пьеро Дела Франчески, написавшего две книги, одна из которых называлась "О перспективе в живописи". Его считают творцом начертательной геометрии.
Лука Пачоли прекрасно понимал значение науки для искусства. В 1496 г по приглашению герцога Моро он приезжает в Милан, где читает лекции по математике. В Милане при дворе Моро в то время работал и Леонардо да Винчи. В 1509 г. в Венеции была издана книга Луки Пачоли "Божественная пропорция" с блестяще выполненными иллюстрациями, ввиду чего полагают, что их сделал Леонардо да Винчи. Книга была восторженным гимном золотой пропорции. Среди многих достоинств золотой пропорции монах Лука Пачоли не преминул назвать и ее "божественную суть" как выражение божественного триединства бог сын, бог отец и бог дух святой (подразумевалось, что малый отрезок есть олицетворение бога сына, больший отрезок – бога отца, а весь отрезок – бога духа святого).
Леонардо да Винчи также много внимания уделял изучению золотого деления. Он производил сечения стереометрического тела, образованного правильными пятиугольниками, и каждый раз получал прямоугольники с отношениями сторон в золотом делении. Поэтому он дал этому делению название золотое сечение. Так оно и держится до сих пор как самое популярное.
В то же время на севере Европы, в Германии, над теми же проблемами трудился Аль Брехт Дюрер. Он делает наброски введения к первому варианту трактата о пропорциях. Дюрер пишет. "Необходимо, чтобы тот, кто что-либо умеет, обучил этому других, которые в этом нуждаются. Это я и вознамерился сделать".
Судя по одному из писем Дюрера, он встречался с Лукой Пачоли во время пребывания в Италии. Аль Брехт Дюрер подробно разрабатывает теорию пропорций человеческого тела. Важное место в своей системе соотношений Дюрер отводил золотому сечению. Рост человека делится в золотых пропорциях линией пояса, а также линией, проведенной через кончики средних пальцев опущенных рук, нижняя часть лица – ртом и т. д. Известен пропорциональный циркуль Дюрера.
Великий астроном XVI в. Коган Кеплер назвал золотое сечение одним из сокровищ геометрии. Он первый обращает внимание на значение золотой пропорции для ботаники (рост растений и их строение).
В последующие века правило золотой пропорции превратилось в академический канон и, когда со временем в искусстве началась борьба с академической рутиной, в пылу борьбы "вместе с водой выплеснули и ребенка". Вновь "открыто" золотое сечение было в середине XIX в. В 1855 г. немецкий исследователь золотого сечения профессор Цейзинг опубликовал свой труд "Эстетические исследования". Он абсолютизировал пропорцию золотого сечения, объявив ее универсальной для всех явлений природы и искусства.
Цейзинг проделал колоссальную работу. Он измерил около двух тысяч человеческих тел и пришел к выводу, что золотое сечение выражает средний статистический закон. Деление тела точкой пупа – важнейший показатель золотого сечения. Пропорции мужского тела колеблются в пределах среднего отношения 13: 8 = 1,625 и несколько ближе подходят к золотому сечению, чем пропорции женского тела, в отношении которого среднее значение пропорции выражается в соотношении 8: 5 = 1,6. У новорожденного пропорция составляет отношение 1: 1, к 13 годам она равна 1,6, а к 21 году равняется мужской. Пропорции золотого сечения проявляются и в отношении других частей тела – длина плеча, предплечья и кисти, кисти и пальцев и т. д.
Справедливость своей теории Цейзинг проверял на греческих статуях. Наиболее подробно он разработал пропорции Аполлона Бельведерского. Подверглись исследованию греческие вазы, архитектурные сооружения различных эпох, растения, животные, птичьи яйца, музыкальные тона, стихотворные размеры. Цейзинг дал определение золотому сечению, показал, как оно выражается в отрезках прямой и в цифрах. Когда цифры, выражающие длины отрезков, были получены, Цейзинг увидел, что они составляют ряд Фибоначчи, который можно продолжать до бесконечности в одну и в другую сторону. Следующая его книга имела название "Золотое деление как основной морфологический закон в природе и искусстве". В 1876 г. в России была издана небольшая книжка, почти брошюра, с изложением этого труда Цейзинга.
В конце XIX – начале XX вв. появилось немало чисто формалистических теории о применении золотого сечения в произведениях искусства и архитектуры. С развитием дизайна и технической эстетики применение закона золотого сечения распространилось на конструирование машин, мебели и пр.
Пропорция, выражаемая числом Ф, по мнению многих исследований, является наиболее приятной для человеческого глаза.
Леонардо де Винчи считал, что идеальные пропорции человеческого тела должны быть связаны с числом Ф. Деление отрезка в отношении Ф он назвал "золотым сечением". В эпоху возрождения "золотое сечение" было очень популярно среди художников, скульпторов и архитекторов. Размеры картины было принято брать такими, чтобы отношение ширины к высоте равнялось Ф. Этот термин сохранился до наших дней, и само "золотое сечение" по прежнему играет важную роль в искусстве. Им руководствовался, например, великий архитектор Ле Корбюзье.
Прямоугольник с таким отношением сторон стали называть "золотым прямоугольником".
Форму "золотого сечения" придавали книгам, столам почтовым открыткам. В дальнейшем книгам и другим бумажным изделиям стали чаще придавать форму прямоугольника с отношением сторон корень из двух. Это связано с тем, что при перегибании такого прямоугольника по средней линии образуются два прямоугольника с тем же соотношением сторон.
Число золотого сечения Ф обладает какой-то странной неуловимостью. Оно появляется в различных проекциях, так и не давая ответа на вопрос, как это число связано с тем или иным явлением. Интерес к мистическому числу Ф достаточно периодичен. Он возникает с обнаружением нового проявления этого числа в каком-либо явлении природы.
Проходит время, и интерес к нему спадает. Но ненадолго. Числу Ф находят всё новое и новое применение, но оно так и остается недоступным для ясного и полного понимания его свойств и степени его влияния на окружающий мир.
Дата: 2019-12-22, просмотров: 256.
