Теория чисел Фибоначчи (стр. 3 из 14)
ЛЕММА МАТИЯСЕВИЧА. Если № > 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.