Теория чисел Фибоначчи (стр. 12 из 14)
Равенство (36) можно доказать и иначе. Положим:
G (n) =
+ C1n + +... + ,где р = E [(n+1)/2]. Из равенства
= + легко следует, что:G(n) = G(n – 1) + G(n – 2). (37)
Кроме того, ясно, что G(1)=2 = F(1) и G(2) =3 = F(2).
Так как обе последовательности F(n) и G(n) удовлетворяют рекуррентному соотношению Х(n) =Х(n – 1) + X (n – 2), то имеем:
G(3) = G(2) + G(1) = F(2) + F(l) = F(3),
и, вообще, G(n)=F(n).
Приведем и другой метод доказательства.
Мы непосредственно установили связь между задачей Фибоначчи и комбинаторной задачей. Эту связь можно было установить и иначе, непосредственно доказав, что число Т(n) решений комбинаторной задачи удовлетворяет тому же рекуррентному соотношению:
T(n+1) = T(n) + T(n – 1), (38)
что и числа Фибоначчи.
В самом деле, возьмем любую (n-1)-последовательность нулей и единиц, удовлетворяющую условию, что никакие две единицы не идут подряд. Она может оканчиваться или на 0, или на 1. Если она оканчивается на 0, то, отбросив его, получим n-последовательность, удовлетворяющую нашему условию. Обратно, если взять любую n-последовательность нулей и единиц, в которой подряд не идут две единицы, и приписать к ней нуль, то получим (n+1)-последовательность с тем же свойством. Мы доказали, что число "хороших" последовательностей, оканчивающихся на нуль, равно Т(n).
Пусть теперь последовательность оканчивается на 1. Так как двух единиц подряд быть не может, то перед этой единицей стоит нуль. Иными словами, последовательность оканчивается на 01. Остающаяся же после отбрасывания 0 и 1 (n – 1)-последовательность может быть любой, лишь бы в ней не шли подряд две единицы.
Поэтому число "хороших" последовательностей, оканчивающихся единицей, равно Т(n – 1). Но каждая последовательность оканчивается или на 0, или на 1. В силу правила суммы получаем, что Т(n + 1) = Т(n) + Т(n – 1).
Мы получили, таким образом, то же самое рекуррентное соотношение. Отсюда еще не вытекает, что числа Т(n) и F(n) совпадают.
Чтобы доказать совпадение чисел Т(n) и F(n), надо еще показать, что T(n)=F(n) и T(2) – F(2) – тогда уже в силу рекуррентного соотношения имеем и T(3)=F(3), T(4)=T(4) и т. д. Существуют две 1-последовательности, удовлетворяющие поставленному условию: 0 и 1, и три 2-последовательности; 00, 01 и 10.
Поэтому T(1) = 2 = F(1) и T(2) =3 =. F(2). Тем самым утверждение доказано.
Для решения комбинаторных задач часто применяют метод, использованный выше. Устанавливают для данной задачи рекуррентное соотношение и показывают, что оно совпадает с рекуррентным соотношением для другой задачи, решение которой нам уже известно. Если при этом совпадают и начальные члены последовательностей в достаточном числе (позже мы остановимся подробнее на том, сколько членов должны совпадать), то обе задачи имеют одинаковые решения.
Применим описанный прием для решения следующей задачи.
Задача. Пусть дано некоторое множество из № предметов, стоящих в определенном порядке. Разобьем это множество на две непустые части так, чтобы одна из этих частей лежала левее второй (то есть, скажем, одна часть состоит из элементов от первого до m-го, а вторая – из элементов от (m + 1)-го до n-го). После этого каждую из частей таким же образом разобьем на две непустые части (если одна из частей состоит уже из одного предмета, она не подвергается дальнейшим разбиениям). Этот процесс продолжается до тех пор, пока не получим части, состоящие из одного предмета каждая. Сколько существует таких процессов разбиения (два процесса считаются различными, если хотя бы на одном шагу они приводят к разным результатам)?
Решение: Обозначим число способов разбиения для множества из n+1 предметов через Вn. На первом шагу это множество может быть разбито № способами (первая часть может содержать один предмет, два предмета,..., и предметов). В соответствии с этим множество всех процессов разбиений распадается на № классов – в s-й класс входят процессы, при которых первая часть состоит из s предметов.
Подсчитаем число процессов в s-м классе. В первой части содержится s элементов. Поэтому ее можно разбивать далее Bs-1 различными процессами. Вторая же часть содержит № – s+1 элементов, и ее можно разбивать далее Bn-s процессами. По правилу произведения получаем, что s-й класс состоит из Bs-1Bn-s различных процессов. По правилу суммы отсюда вытекает, что:
Bn = B0 Bn-1 + B1 Bn-2 + … + Bn-1 B0 (39)
Мы получили рекуррентное соотношение для Bn. Этому соотношению удовлетворяют числа:
Тn =
Чтобы доказать равенство
Вn = Тn =
. (40)нам осталось показать, что начальные члены Т0 и В0 последовательностей T0, T1,..., Tn, … и В0, В1,..., Вn,... совпадают.
Мы имеем T0 =
=1. С другой стороны, В0 = 1, так как множество из одного элемента можно разделить единственным образом. Итак, В0 = T0.Но по рекуррентной формуле имеем В1 = =1.Так как T0 удовлетворяет той же рекуррентной формуле, то T1 = = 1.Далее устанавливаем, что:B2 = B0 B1 + B1 B0 = 2 и T2 = T0 T1 + T1 T0 = 2 и т. д.
Итак, все члены обеих последовательностей совпадают. Таким образом, доказан следующий результат:
Число процессов последовательного деления множества из № + 1 элементов, расположенных в некотором порядке, равно:
Тn =
.5.3. Решение рекуррентных соотношений
Для школьника важно выработать умение за частной задачей видеть общую теорию, и наоборот – общую теорию необходимо уметь применять к частному случаю.
Умение решать рекуррентные соотношения как раз и приводят нас доказательству многих интересных фактов, касающихся чисел Фибоначчи.
Мы будем говорить, что рекуррентное соотношение имеет порядок k, если оно позволяет выразить f(n+k) через f(n), f(n + l),.., f(n + k – l).
Например, f(n+2) = f(n) f(n+1) – 3 f 2(n+1) + 1 – рекуррентное соотношение второго порядка, а f(n+3) = 6f(n) f(n+2) – f(n+1) – рекуррентное соотношение третьего порядка.
Если задано рекуррентное соотношение k-гo порядка, то ему удовлетворяет бесконечно много последовательностей. Дело в том, что первые k элементов последовательности можно задать совершенно произвольно – между ними нет никаких соотношений. Но если первые k элементов заданы, то все остальные элементы определяются совершенно однозначно – элемент f(k+1) выражается в силу рекуррентного соотношения через f(1), …, f(k), элемент f(k+2) – через f(2),..., f(k+l) и т. д.
Пользуясь рекуррентным соотношением и начальными членами, можно один за другим выписывать члены последовательности, причем рано или поздно мы получим любой ее член. Однако, при этом нам придется выписать и все предыдущие члены – ведь не узнав их, мы не узнаем и последующих членов. Но во многих случаях мы хотим узнать только один определенный член последовательности, а остальные члены нам не нужны В этих случаях удобнее иметь явную формулу для n-го члена последовательности. Мы будем говорить, что некоторая последовательность является решением данного рекуррентного соотношения, если при подстановке этой последовательности соотношение тождественно выполняется. Например, последовательность 2, 4, 8,..., 2n,...
является одним из решений рекуррентного соотношения:
f(n+2) = 3 f(n+1) – 2 f(n).
В самом деле, общий член этой последовательности имеет вид f(n) = 2n. Значит, f(n+2) = 2n+2, f(n+1) = 2n+1.Но при любом № имеет место тождество 2n+2 =3x2n+1 – 2x2n. Поэтому 2n является решением указанного соотношения.
Решение рекуррентного соотношения k-гo порядка называется общим, если оно зависит от k произвольных постоянных С1,..., Сk, и путем подбора этих постоянных можно получить любое решение данного соотношения.
Например, для соотношения
f(n+2) = 5 f(n+1) – 6 f(n) (41)
общим решением будет:
f(n) = С1 2n + С2 3n. (42)
В самом деле, легко проверить, что последовательность (42) обращает соотношение (41) в тождество. Поэтому нам надо только показать, что любое решение нашего соотношения можно представить в виде (42). Но любое решение соотношения (41) однозначно определяется значениями f(1) и f(2). Поэтому нам надо доказать, что для любых чисел a и b найдутся такие значения С1 и С2, что
2 С1 + 3 С2 = a и 22 С1 + 32 С2 = b
Но легко видеть, что при любых значениях а и b система уравнений:
имеет решение. Поэтому (42) является общим решением соотношения (41).
Для решения рекуррентных соотношений общих правил, вообще говоря, нет Однако существует весьма часто встречающийся класс соотношений, решаемый единообразным методом. Это – рекуррентные соотношения вида:
f(n+k) = a1 f(n+k – 1) – a2 f(n+k – 2) + … + an f(n), (43)
где a1, a2, …, an – некоторые числа Такие соотношения называют линейными рекуррентными соотношениями с постоянными коэффициентами.