מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/נוסחאות נסיגה/תרגילים/נוסחת נסיגה שאיננה מתאימה למשפט המאסטר/שאלה

$\displaystyle T(n)$ מתארת את זמן הריצה של אלגוריתם כלשהו, והיא פתרונה של נוסחת הנסיגה $\displaystyle T(n)=a\cdot T\left({\frac {n}{b}}\right)+f(n)$.‏ בנוסחה זו, $\displaystyle a$ מספר שלם גדול ממש מ1, $\displaystyle b$ מספר גדול ממש מ1, ו$\displaystyle f(n)$ היא פונקציה המקיימת $\displaystyle f(n)=\Theta \left(n^{\log _{b}(a)}\log ^{k}(n)\right)$, עבור $\displaystyle k$ שלם גדול ממש מ1. אנא הוכח $\displaystyle T(n)=\Theta \left(n^{\log _{b}(a)}\log ^{k+1}(n)\right)$.