Есть рекуррентное соотношение и Объясните, как эти две формулы могут быть тождественными. Почему а не ? Друг подсказал, что это

Question

4 года назад

6

Есть рекуррентное соотношение и Объясните, как эти две формулы могут быть тождественными. Почему а не ? Друг подсказал, что это

Есть рекуррентное соотношение
$T_{n} =2T_{n-1}+1$
и
$T_{n} =2^{n} -1$
Объясните, как эти две формулы могут быть тождественными. Почему $2^{n}$ а не $2*n$ ? Друг подсказал, что это соответствует показательной функции, но мне все равно непонятно.

Знания

Математика

1 ответ:

otto555 · Answer 1 · 2020-04-22T21:03:13+03:00

Доказывается методом математической индукции.

1. Проверяем при n = 1:

$T_0 = 2^0 -1 = 0 \\ \\ T_1 = 2^1 - 1 = 1 \\ \\ \\ T_1 = 2* T_0 + 1 = 2*0 + 1 = 1$

Всё верно. Можно продолжить проверку и убедиться, что всё верно.

2. Пусть $T_n = 2^n - 1 = 2T_{n-1} - 1$ верно для n.

3. Докажем, что верно при (n+1)

$T_{n+1} = 2T_n + 1 = 2* (2^n -1) + 1 =2*2^n - 2 + 1 = 2^{n+1} - 1$

Как видим, так оно и есть.