Рекуррентные соотношения

a) Давайте попробуем доказать это по индукции.
1. База. При имеем: где в качестве c берётся а в качестве берётся

2. Шаг индукции. Итак, пусть при всех от до мы уже доказали формулу, что
Докажем её для :

Однако мы бы хотели, чтобы наше имело вид
Таким образом, у нас с одной стороны свободный член получился равным а с другой стороны он должен быть просто
Из этого условия и находим : значит, откуда Вот здесь-то нам и пригодилось условие, что

b) Независимо от предыдущего пункта попробуем угадать формулу, посчитав первые несколько членов:

И вот, например, для если преобразовать выражение, то становится видно, что:

Таким образом, очевидно (но лучше доказать по индукции), что для формула имеет вид:

В скобках у нас появляется формула суммы геометрической прогрессии с первым членом и знаменателем

В итоге имеем