Из пунктов 1 и 2 следует: для n ≥ 1 f(n) = A(n)∙α + B(n)∙β + C(n)∙γ.
Теперь докажем (12) в предположении, что (11) выполняется.
Если n - четное, тогда по соотношению (10) f(2n) = 2f(n) + β. Подставляя в данное равенство соотношение (11) получим:
A(2n)∙α + B(2n)∙β + C(2n)∙γ = 2(A(n)∙α + B(n)∙β + C(n)∙γ) + β
(A(2n) − 2A(n))∙α + (B(2n) − 2B(n)−1)∙β + (C(2n) − 2C(n))∙γ = 0
Теперь подставим соотношение (12) в данное равенство и посмотрим, будет ли оно выполнятся: т.к. n = 2m+ k=> 2n = 2m+1+2k, тогда A(2n) = 2m+1, B(2n)=2m+1−1−2k, С(n)=2k. Подставляем: (2m+1 −2∙2m)∙α + +(2m+1−1−2k−2(2m−1−k)−1)∙β + (2k −2k)∙γ = 0
0∙α + 0∙β + 0∙γ = 0, получили 0=0 (верно);Если n - нечетное, тогда по соотношению (10) f(2n+1) = 2f(n) + γ. Снова подставляя в данное равенство соотношение (11) получим:
A(2n+1)∙α + B(2n+1)∙β + C(2n+1)∙γ = 2(A(n)∙α + B(n)∙β + C(n)∙γ) + γ
(A(2n+1) − 2A(n))∙α + (B(2n+1) − 2B(n))∙β + (C(2n+1) − 2C(n)−1)∙γ = 0
Теперь подставим соотношение (12) в данное равенство и посмотрим, будет ли оно выполнятся: n = 2m+ k=> 2n+1 = 2m+1+2k+1, тогда A(2n+1) = 2m+1, B(2n+1) = 2m+1 −1−(2k+1), С(n+1) = 2k+1. Подставляем : (2m+1 −2∙2m)∙α + +(2m+1−2−2k−2(2m−1−k))∙β + (2k+1 −2k−1)∙γ=0
0∙α + 0∙β + 0∙γ = 0, получили 0=0 (верно).Таким образом, мы показали, что соотношения (11) и (12) верные.
Выше было показано, что J – рекуррентность имеет решение в двоичной записи: J((bmbm-1 … b1b0)2) = (bm-1 … b1b0bm)2, где bm = 1. Можно показать, что и обобщенная рекуррентность (10) имеет похожее решение.
Запишем соотношение (10) следующим образом:
Пусть Fn - минимальное число перекладываний, необходимых для перемещения n дисков с одного колышка на другой через колышек С.
Рассмотрим крайние случаи: F0=0, F1=2, F2=8, F3=26. Эксперимент с тремя дисками дает ключ к общему правилу перемещения n дисков: сначала мы перемещаем (n−1) меньших дисков на колышек B (что требует Fn-1 перекладываний), затем перекладываем самый большой диск на колышек С (одно перекладывание), потом помещаем (n−1) меньших дисков на колышек А (еще Fn-1 перекладываний), затем перекладываем самый большой диск на колышек B (одно перекладывание), и, наконец, помещаем (n−1) меньших дисков на колышек B (еще Fn-1 перекладываний). Таким образом, n дисков (при n>0) можно переместить самое большое за 3Fn-1+2 перекладываний (т.е. достаточно перекладываний): Fn≤ 3Fn-1+2.
Сейчас покажем, что необходимо 3Fn-1+2 перекладываний. На двух этапах мы обязаны переместить самый большой диск. Когда мы это делаем, (n−1) меньших дисков должны находиться на одном колышке (А или B), а для того чтобы собрать их вместе, потребуется, по меньшей мере, Fn-1 перекладываний. Самый большой диск можно перекладывать и более одного раза. Следовательно, Fn≥ 3Fn-1+2.
Эти два неравенства вместе с тривиальным решением при n=0 дают рекуррентное соотношение:
F0=0
Fn= 3Fn-1+2 при n>0
Решим данное соотношение.
Первый способ решения (угадывание правильного решения с последующим доказательством, что наша догадка верна). Вычислим: F1=2=31 −1, F2=32 −1, F3=33 −1. Из этого можно сделать предположение, что
Fn= 3n−1 при n≥0.
Докажем методом математической индукции по числу n:
1) База: n=0, F0=30–1=1–1=0 (верно);
2) Индуктивный переход: пусть доказано для всех чисел t≤ (n–1). Докажем для t=n: Fn= 3Fn-1+2
3(3n-1−1)+2 = 3n − 1.Из пунктов 1 и 2 следует: при n≥0 Fn= 3n − 1.
Второй способ решения.
К обеим частям соотношения (1) прибавим 1:
F0+1 = 1,
Fn+1 = 3Fn-1+3 при n>0.
Обозначим Un= Fn+1, тогда получим: U0 = 1, Un= 3Un-1 при n>0.
Решением этой рекурсии есть Un=
; следовательно, Fn= −1.В дальнейшем мы не будем показывать достаточное и необходимое условие в решении подобных задач, а сразу будем описывать получение нужного равенства. Это связано, во-первых, с тем, что достаточное и необходимое условие показывается аналогично тому, как это сделано в данной задаче, а во-вторых, в виду ограниченности объема дипломной работы.