Курсовая работа: Возвратные последовательности

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

Т_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 прямыми?

1

????? ?????? ? ???????????? ??????? ???????.

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

Таким образом, 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 (верно);