How do you solve the recurrence relation $T(n) = cn(dn + T(n-k))$?

Question

How do I come up with a big-O approximation to $T(n) = cn(dn + T(n-k))$ where $c, d \in \Bbb{R}$ are fixed. $T(n)$ is the running time of a recursive algorithm. This seems difficult as usual. :)

Answer 1

Assuming both $n$ and $k$ as variables and $T(0)=1$ :

$$T(n)=cn(dn+T(n-k)) =cdn^2+cnT(n-k) =cdn^2+cn[cn(T(n-2k)+dn)] =cdn^2+c^2dn^3+c^2n^2T(n-2k) $$ now on generalizing T(n) as $$T(n)=d(cn^2+c^2n^3+........+c^an^{a+1}+......)+c^{n/k}n^{n/k}T(n-bk) $$ [because if $n=bk$ then $n/k=b$] Taking n as common $$T(n)=dn(cn+c^2n^2+.....+(cn)^{(n/k)})+(cn)^{n/k} =T(n)=dn \frac{cn((cn)^{n/k}-1)}{cn-1}+(cn)^{n/k}=O(n^{(n/k)+1}) $$ if $n/k=b$ then $$ T(n)=O(n^{(b+1)})$$