I have the recurrence which I need to solve via telescoping and finally find the big theta time complexity:
$ T(n) = kT(\frac{n}{k}) + k(k − 1) $
Where $ K = 9 $
I have taken $ K = 9 $, $ n=9^m$ and substituted it in the function, resulting in.
$ T(n) = 9T(\frac{9^m}{9}) + 9(9 − 1) $
$ T(n) = 9T(\frac{9^m}{9}) + 72 $
$ T(n) = 9T(\frac{{9^m}^{-1}}{9}) + 72 $
I then proceeded to take $ T(n) $ to be $T(2^m)$
Finally I am left with:
$ F(m) = 9F(m-1) + 72 $
Provided I haven't made a major error I am not sure how to procede from here, any assitance would be greatly appreciated.
Let us consider that $n = k^p$ is an integer power of $k$. Thus, the recurrence relation rewrites as $$ \underbrace{T(k^p)}_{u_p} = k\, \underbrace{T(k^{p-1})}_{u_{p-1}} + k(k-1) \, . $$ The sequence $(u_p)_{p\in\mathbb{N}}$ is an affine recursion. Therefore, the sequence defined by $v_p = u_{p+1} - u_p$ is a geometric sequence with common ratio $k$, $$ v_{p+1} = k u_{p+1} + k(k-1) - \left( k u_p + k(k-1)\right) = k v_p \, , $$ and first term $v_0 = (k-1)\left(u_0 + k\right)$. Recognizing a telescoping series, one writes $$ u_p = u_0 + \sum_{k=0}^{p-1} v_k = u_0 + v_0\frac{1-k^p}{1-k} \, , $$ i.e. $$ u_p = k^p \left(u_0 + k \right) - k \, . $$ Finally, $u_p=\Theta(k^{p})$, and $T(n) = \Theta(n)$.