I am working on a recurrence equation and I am wondering why this equivalence? What's the general rule to do this for other sums?
$$T(\frac{5^k}{5^k})+4·5^k\left(\sum_{i=0}^{k-1} \frac {1}{5^i}\right)+k = T(1)+4·5\sum_{i=0}^{k-1} 5^i+k $$
I am working on a recurrence equation and I am wondering why this equivalence? What's the general rule to do this for other sums?
$$T(\frac{5^k}{5^k})+4·5^k\left(\sum_{i=0}^{k-1} \frac {1}{5^i}\right)+k = T(1)+4·5\sum_{i=0}^{k-1} 5^i+k $$
Copyright © 2021 JogjaFile Inc.
$$5^k\left(\sum_{i=0}^{k-1} \frac {1}{5^i}\right) = 5^k\sum_{i=0}^{k-1} \frac1{5^{ (k-1)-i}}=5^k\sum_{i=0}^{k-1}{5^{-k+1+i}}=5\sum_{i=0}^{k-1} 5^i$$