Каким способом решить рекуррентное уравнение?

Question

[Евгений Крамор]

Как решить рекуррентное уравнение вида:
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

но так и не могу въехать, что и откуда берётся.

Какими источниками для ознакомления можно воспользоваться?
Что-то искал в книге Вилинкина (Комбинаторика), но успех обошёл меня стороной.

Comments

[Lynn «Кофеман»]

Напишите формулы нормально. Невозможно читать когда 2 в степени к обозначается 2к, а не 2^к

[Lynn «Кофеман»]

А вообще гугл выдаёт кучу учебников и способов решения.

[devalone]

int t(int n) {
  if (n == 1) {
    return 3;
  }
  return 4 * t(2 * n / 3) + 1;
}

?

[Andy_U]

devalone, Очевидно, нет. Запустите ваш код, например, с n=2....

[devalone]

Andy_U, https://ideone.com/7DdQjH

[Andy_U]

devalone, Вы там случайно не нацело поделили? Типа 2*2/3 = 1? Так то 4/3 должно быть и рекурсивные вызовы до бесконечности.

[devalone]

Andy_U, int же, можно сделать float и условие <=

[Andy_U]

devalone, Я в очередной раз намекаю, что рекурсия тут не очень работает, потому что исходно функция определена лишь на множестве n=(3/2)^k , k=0, 1, 2, ....

[devalone]

Andy_U, откуда взялась степень и почему вдруг не работает?

[Andy_U]

devalone, Ну посмотрите внимательно на постановку задачи в первой строчке вопроса... Мы изначально знаем лишь значение T при n=1. Для какого нового n мы можем теперь узнать значение функции? Лишь для 3/2, ибо лишь тогда в правой части будет стоять T(1) которое мы уже знаем (и больше ничего). И так далее.

Answer 1

[Александр Скуснов]

Метод производящих функций