Warum braucht Akra-Bazzi, dass die Mautfunktion g begrenzt ist?

Im Anschluss an vonbrands Antwort möchte ich ein kleines Dokument über stärkere Master-Theoreme für unsere Schüler schreiben, von denen eines das Akra-Bazzi-Theorem ist. Ich habe den Satz aus ihrer Arbeit [1] kopiert und - neben einer kleinen Notationsverwirrung² - das folgende Problem festgestellt.

Die Autoren verlangen (Hervorhebung von mir):

$g(x)$ ist für reelle Werte definiert und ist eine begrenzte , positive und nicht abnehmende Funktion $x$$\forall x \geq 0$

Hier ist die Mautfunktion, dh die Wiederholung hat die Form$g$

$\qquad\displaystyle T(n) = g(n) + \sum_{i=1}^k a_i T\bigl(\lfloor n b_i^{-1} \rfloor\bigr)$ .

Am Ende ihrer Arbeit (S. 209) geben sie mehrere Beispiele für die Anwendung ihres Ergebnisses und verwenden Funktionen in die eindeutig nicht begrenzt sind.$\Omega(n)$

Vom Überfliegen des Beweises scheinen sie hauptsächlich Integrale der Form zu erfordern

$\qquad\displaystyle \int_a^b \frac{g(x)}{x^{p+1}} dx$

endliche Werte haben. Es kann also ausreichend sein , auf jedes kompakte Intervall zu beschränken . Ich habe den Beweis nicht im Detail durchgearbeitet. Ist es möglich, dass sie das meinen?$g$

Meine Frage ist: Wie sollte der Satz von Akra-Bazzi so formuliert werden, dass er mit Beweisen und Beispielen übereinstimmt ?

1. Zur Lösung linearer Wiederholungsgleichungen von M. Akra und L. Bazzi (1998)
2. Sie benötigen . Ist das eine Notation, die ich nicht kenne, oder ein Tippfehler? Ich gehe davon aus, dass die beabsichtigte Bedeutung .$a_i \in R^{*+}$$(0,\infty) \subseteq \mathbb{R}$

Schauen Sie sich die Notizen von Tom Leighton an , auf die im Wikipedia-Artikel verwiesen wird. Seine Notizen haben anscheinend weniger Tippfehler als das Originalpapier. Die Bedingung, die er von verlangt, ist ein Polynomwachstum. Wenn Sie das Argument mit einer Konstanten skalieren, wird der Betrag, den die Funktion skaliert, auch durch eine Konstante begrenzt.$g$

Die schönste Version des Akra-Bazzi-Theorems, die ich gesehen habe, ist die in Lehman, Leighton, Meyer "Mathematik für Informatik" . Die Diskussion beginnt auf Seite 1019. Eine (ältere) Druckversion ist verfügbar. Kein Beweis. Müsste Leightons Notiz durchgehen , um zu überprüfen, ob die Vorlesungsnotizen / Buchversion richtig sind (es gibt etwas andere Bedingungen, die viel einfacher zu überprüfen sind).