Возвратные последовательности (стр. 4 из 5)

Первый способ решения (угадывание правильного решения с последующим доказательством, что наша догадка верна). Вычислим:

Т₃ = 2∙3 + 1 = 7; Т₄ = 2∙7 + 1; Т₅ = 2∙15 + 1; Т₆ = 2∙31 + 1 = 63.

Теперь можно сделать предположение, что

Т_n=2ⁿ − 1 при n≥ 0. (42)

Докажем методом математической индукции по числу n:

1) База: n=0, Т₀=2⁰ – 1 = 1 – 1 = 0 (верно);

2) Индуктивный переход: пусть доказано для всех чисел t ≤ (n– 1). Докажем для

t= n: Т_n= 2T_{n – 1} +1

2(2^{n – 1} − 1) + 1 = 2∙2^{n – 1} − 2 + 1 = 2ⁿ − 1

Из пунктов 1 и 2 следует: при n≥ 0 Т_n= 2ⁿ − 1

Второй способ решения.

К обеим частям соотношения (41) прибавим 1:

Т₀+1 = 1,

Т_n+1 = 2T_{n – 1} + 2 при n> 0.

Обозначим U_n= T_n+ 1, тогда получим

U₀ = 1

U_n= 2U_{n- 1} при n> 0.

Решением этой рекурсии есть U_n= 2ⁿ; следовательно Т_n = 2ⁿ−1.

2. Задача о разрезании пиццы

Формулировка задачи: сколько кусков пиццы можно получить, делая n прямолинейных разрезов ножом? Или, каково максимальное число L_n областей, на которые плоскость делится n прямыми?

Снова начнем с рассмотрения крайних случаев.

Эксперимент с тремя прямыми показывает, что добавленная третья прямая может рассекать самое большое три старых области вне зависимости от того, как расположены первые две прямые:

Таким образом, L₃ = 4 + 3 = 7 – самое большое, что можно сделать.

Обобщая, приходим к следующему выводу: новая n-я прямая (при n> 0) увеличивает число областей на k- когда рассекает k старых областей - когда пересекает прежние прямые в (k− 1) различных местах. Две прямые могут пересекаться не более чем в одной точке. Поэтому новая прямая может пересекать (n− 1) старых прямых не более чем в (n− 1) различных точках, и мы должны иметь k≤ n. Установлена верхняя граница:

L_n≤ L_{n – 1} + nпри n> 0

В этой формуле можно достичь равенства следующим образом: проводим n-ю прямую так, чтобы она не была параллельна никакой другой прямой (следовательно, она пересекает каждую из них) и так, чтобы она не проходила ни через одну из имеющихся точек пересечения (следовательно, она пересекает каждую из прямых в различных местах). Поэтому рекуррентное соотношение имеет вид:

L₀ = 1

L_n= L_{n- 1}+ nпри n > 0

Теперь получим решение в замкнутой форме.

L_n= L_{n – 1} + n = L_{n – 2} + (n−1) + n = L_{n- 3}+ (n−2) + (n−1) + n = … = L₀+ 1 + 2+ +… + (n−2) + (n−1) + n = 1 +

L_n =

+ 1при n ≥ 0 (43)

Докажем полученное равенство методом математической индукции.

1) База: n=0, L₀=

= 1 (верно);

2) Индуктивный переход: пусть доказано для всех чисел t ≤ (n–1). Докажем для t=n:

L_n= L_n-1+ n

= =

Из пунктов 1 и 2 следует: при n ≥ 0

L_n =

+ 1