Теория чисел Фибоначчи (стр. 4 из 14)
Следовательно,
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. Многие соотношения между числами Фибоначчи удобно доказывать при помощи метода полной индукции. Сущность метода полной индукции (называемого часто методом математической индукции) состоит в следующем: для доказательства, что некоторое утверждение справедливо для всякого натурального числа, достаточно установить, что: