Question

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

Answer 1

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

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$

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

Answer 2

Спасибо за ответ, но меня скорее волнует сама запись второго выражения.

Answer 3

А почему она волнует? Запись, как запись.