Есть рекуррентное соотношение

и

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

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

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



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

2. Пусть верно для n.

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



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