Основная теорема для рекуррентных соотношений(Кормен)

[Righost]

Доброго времени суток!
Помогите разобраться с задачей из Кормена(Алгоритмы: построение и анализ).
Дано соотношение вида: $T(n) = a \cdot T(n/b) + f(n)$

Теорема:
Если $f(n)=\Omega \left(n^\log_ba+\varepsilon \right)$ для некоторой константы $\varepsilon > 0$, и если $af(n/b) \leqslant cf(n)$ для некоторой константы $0<c<1$ и всех достаточно больших n, то $T(n) = \Theta (f(n))$

Задача( номер 4.3-5 во втором издании):
Рассмотрим условие регулярности $af(n/b) \leqslant cf(n)$ для некоторой константы $0<c<1$. Приведите примеры констант $a \geqslant 1$ и $b>1$ и функции $f(n)$ которые удовлетворяют всем условиям теоремы, кроме условия регулярности.

В итоге получается система:

$$ \begin{cases} af(n/b) > cf(n),&\text{для любого c в интерале $0<c<1$, где $a \geqslant 1$, $b > 1$, $n \in \mathbb N$;}\\ f(n)=\Omega \left(n^\log_ba+\varepsilon \right), &\text{где $\varepsilon >0$;}\\ \end{cases} $$

Пока что у меня получилось только прийти к выводу, что искомая функция $f(n) \ne n^x $:
Пусть $f(n) = n^x$:
$a \cdot n^x/b^x > c \cdot n^x \Rightarrow n^x \cdot (a-cb^x) > 0$
$a-cb^x > 0 \Rightarrow x < \log_b a/c$
из второго уравнения системы так-же следует, что $x > \log_b a$

В итоге получаем:
$\log_b a< x < \log_b a - \log_b c$, откуда видно, что $\forall x > \log_b a \exists c<1 : x > \log_b a - \log_c b$

Подскажите куда двигаться дальше.

[Righost]

Забыл сделать важное замечание: функция $f(n)$ асимптотически положительна.

[4iFF]

Righost
Добрый день! Тоже стараюсь решить это задание. Пока пришел только к выводу который Вы тоже сделали и что наверное функция для того что бы выполнялось первое условие в системе должна быть достаточно медленно растущей (к сожалению нельзя брать функции с горизонтальной асимптотой в силу второго уравнения). Предлагаю Up темы. ^_^
P.S.
Хотелось бы узнать названия книг в которых хорошо освещаются вопросы решения рекуррентных соотношений.

[Утундрий]

Там же, в Кормене и др. Начиная с раздела 4.4. (Метод деревьев рекурсии) и далее.