Метод математической индукции при решении рекуррентных уравнений работает следующим образом: 2

1. База индукции. 1 Проверяется истинность утверждения при n = 1 (первый индукционный шаг). 2
2. Индукционное предположение. 1 Допускается, что утверждение справедливо при n = k, где k — произвольное натуральное число (второй индукционный шаг). 2
3. Индукционный переход. 1 Доказывается, что тогда утверждение верно и при n = k + 1 (второй индукционный шаг). 2

Если обе части доказательства проведены, то на основании принципа математической индукции утверждение истинно для всех натуральных n (вывод). 2

Метод математической индукции применим для доказательства формул n-ых членов числовых последовательностей, заданных рекуррентным способом, то есть выражением n-го члена через один или несколько предыдущих. 2