Substituční metoda

Mějme rekurentní rovnici

Pomocí iterační metody po krocích dostaneme

Iterování skončí po propracování se k , tedy dosažení rovnosti

Výpočtem zjistíme

Pak dostáváme

Pomocí matematické indukce dokažte vztah pro

Máme dokázat:
Splňuje-li rekurentní rovnici , pak existují tak, že pro každé

Indukční krok:
Předpokládejme, že pro platí .

Potom s využitím rekurentního vztahu dostáváme

Poslední výraz (ten v závorce) je záporný pro , tedy když jí škrtnu, celý výraz zvětším. A proto platí
Omezení na jsme žádná neměli.

To jsme chtěli dokázati a máme hotovo, už jen zbývá zvolit nějaký základní krok, odkud indukci nastartujeme.

Základní krok:
Hledáme takové, aby nerovnost platila pro nějaké
Můžeme vzít libovolné , pro které má smysl a pak nerovnost splnit volbou dostatečně velkého