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

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

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$

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