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

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

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

[tex]T_0 = 2^0 -1 = 0 \\ \\ T_1 = 2^1 - 1 = 1 \\ \\ \\ T_1 = 2* T_0 + 1 = 2*0 + 1 = 1[/tex]

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

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

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

[tex]T_{n+1} = 2T_n + 1 = 2* (2^n -1) + 1 =2*2^n - 2 + 1 = 2^{n+1} - 1[/tex]

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