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
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$.