Find closed form of $T(n)=5T(n/5)+3n$, $T(1)=7$

197 Views Asked by At

As mentioned in the title, I have to find the closed form of a recursive set: $T(n)=5T(n/5)+3n$ $\forall n \geq 2$, $T(1)=7$.

So far I have:

$k=1$, $T(n)=5T(n/5)+3n$

$k=2$, $T(n)=5(5T(n/25)+3(n/5))+3n = 5^2T(n/25)+3n+3n$

$k=3$, $T(n)=5^2(5T(n/125)+3(n/25))+3n+3n = 5^3T(n/125)+3n+3n+3n$

$k=4$, $T(n)=5^3(5T(n/625)+3(n/125))+3n+3n+3n = 5^4T(n/625)+3n+3n+3n+3n$

EDIT: I wrote $5(5^2T(n/125)$ instead of $5^2(5T(n/125)$... Now I definitely can do the question.