# finding the closed form of $T(n) = 4T(n/4) + 5n$

I am trying to use "telescoping" demonstrated in this tutorial https://www.youtube.com/watch?v=lPCS2FFyqNA to solve this recurrence relation.

I started it off below, but quickly lost my way. Might anyone show the process for breaking down this recurrence relation, $$T(n) = 4T(n/4) + 5n$$ into a closed form?

$$T(n) = 4T(n/4) + 5n$$

$$T(n-1) = 4T((n-1)/4) + 5n - 5$$

$$T(n-2) = 4T((n-2)/4) + 5n - 10$$

$$....$$ $$T(n) = ???$$

I know we would cancel out the terms on the left and the right side of the $$=$$ but because it's divided by 4, I'm getting a bit lost...

Thank you

• Is N any integer, or is it any integer div. by 4?
– user721016
Feb 12 '20 at 7:23

Hint.

Taking $$m = 4n$$

$$T(4m)=4T(m)+20m$$

and now

$$T\left(4^{\log_4(4m)}\right)=4T\left(4^{\log_4(m)}\right)+20m$$

calling $$\mathcal{T}(\cdot)=T(4^{(\cdot)})$$ and $$z = \log_4 m$$

$$\mathcal{T}(z+1)=4\mathcal{T}(z)+20\times 4^z$$

with solution

$$\mathcal{T}(z) = \left(5z+C_0\right)4^z$$

now from $$z$$ to $$m$$.

• Thank you @Cesareo... I'm a bit confused in how you found $4{^/log(4m)}$ can you explain that part. Thanks! Feb 12 '20 at 14:13
• With positive $m$ we have $4m=4^{\log_4(4m)}$ Feb 12 '20 at 14:16