Последовательно производим подстановки и пытаемся уловить общий принцип.
Пример 1.
Имеем рекуррентное соотношение
Подставим в первое равенство эквивалентное выражение для
Теперь необходимо исключить значение
Выполняем последовательность подстановок
Будем подставлять результаты в исходное уравнение
Необходимо уловить общую схему
Слагаемые с конца представляют собой число -15, умноженное на очередную степень двойки.
Коэффициент при рекурсивном вызове функции T является степенью двойки.
Аргумент функции T всякий раз уменьшается на 2.
Процесс завершится, когда мы доберемся до значения или
Сколько нужно сделать подстановок?
При четном нужно сделать подстановок.
Это даст слагаемых с множителем -15 и степень двойки перед .
Например, при нужно сделать пять подстановок; получим шесть слагаемых с множителем -15, и коэффициент при будет равен .
Для четных значений имеем
Для нечетных значений имеем
Применяя равенство
получаем для четного
Действуя аналогично получаем для нечетного
Пример 2
Имеем рекуррентное соотношение
, если ;
в противном случае
Будем действовать так же как в предыдущем случае
Сначала будет подставлять значения для . В результате приходим к равенствам
Последовательно производим подстановку этих равенств в исходное уравнение.
,
;
,
,
,
,
Выявляем закономерности:
коэффициент при -1 увеличивается в некоторую степень четверки раз;
степень двойки, на которую мы делим аргумент, всякий раз на 1 больше наибольшей степени четверки при -1;
степень четверки в коэффициенте при такая же, что и степень двойки, на которую мы делим аргумент.
При этот коэффициент равен
При каком значении подстановки должны прекратиться?
Поскольку значения заданы явно при можно остановиться, добравшись до
В результате получаем
Упростим выражение используя соотношение