На этом шаге мы дадим краткую характеристику этому методу.

Метод расширения (итерации или обратной подстановки) применяется прежде всего для решения рекуррентных соотношений, рекурсивное условие которых содержит одну ссылку на рекурсивную функцию (в отдельных случаях он может быть применён к рекуррентным соотношениям с несколькими ссылками на рекурсивную функцию). Его идея заключается в последовательном упрощении рекуррентного соотношения вплоть до выявления на некотором шаге i общей закономерности. После чего в функцию подставляются конкретные значения в предположении, что начальное условие достигнуто на этом шаге i. Приводимые в следующих шагах примеры иллюстрируют эту процедуру, а в дальнейшем будет рассмотрен соответствующий визуальный подход, называемый "методом дерева".

На следующем шаге мы рассмотрим общие рекуррентные соотношения.