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

Алгоритм применения метода: 3

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

Роль базы индукции в методе рекуррентных соотношений играет начальное значение вычисляемой величины, а роль шага индукции — рекуррентное соотношение. 4

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