Каким способом решить рекуррентное уравнение? Как решить рекуррентное уравнение вида:T( n) =4T(2n/3) + 1, T(1) = 3?
Рассматривал один пример:T(n) = 2T(n/2) + 5n2
T(1) = 7Решение:Для простоты мы предположим, что n является степенью 2 , т.е. n = 2к
T(n) = 2T(n/2) + 5n2 =
= 2(2T (n/4) + 5 (n/2)2 ) + 5n2 =
= 2(2(2T (n/8) + 5 (n/4)2 ) + 5 (n/2)2 ) + 5n2 =…=
=2к T(1) + 2к-1 · 5 (n/2k-1 ) 2 + … + 2 · 5 (n/2)2 + 5n2
но так и не могу въехать, что и откуда берётся.
Какими источниками для ознакомления можно воспользоваться?
Что-то искал в книге Вилинкина (Комбинаторика), но успех обошёл меня стороной.

Предыдущий
вопрос Следующий
вопрос

Для решения рекуррентных уравнений можно использовать метод разделяй и властвуй (divide and conquer).

В данном случае, уравнение T(n) = 4T(2n/3) + 1 может быть решено следующим образом:

Предположим, что n является степенью 3, т.е. n = 3^k. Тогда уравнение примет вид:
T(3^k) = 4T(2 3^(k-1)) + 1 = 4T(3^(k-1) 2/3) + 1 = 4T(3^(k-1)) + 1

Заменим T(3^k) на T(3^(k-1)) в уравнении:
T(3^k) = 4T(3^(k-1)) + 1

Продолжим подстановку, пока не получим базовый случай, T(1):
T(3^k) = 4(4T(3^(k-2)) + 1) + 1 = 16T(3^(k-2)) + 4 + 1

После k итераций мы получим:
T(3^k) = 4^k T(1) + 4^(k-1) + ... + 4 + 1

Подставим T(1) = 3 и найдем T(n):
T(3^k) = 4^k * 3 + 4^(k-1) + ... + 4 + 1

Таким образом, решив каждое слагаемое, мы найдем значение T(n).

Для ознакомления с методами решения рекуррентных уравнений и алгоритмическими подходами к решению задач можно воспользоваться учебниками по алгоритмам и структурам данных, онлайн-курсами по алгоритмике и математике, а также материалами по теории вычислительных алгоритмов.