I was given a whole bunch of recurrence equations to solve but there's one in particular that i can't seem to solve...
T(n) = T(9n/10) + n
Assume that..
T(1) = 0
n = $a^k$ (for some appropriate value of a)
Down below is my attempt at solving this...
1) T(n) = T(9n/10) + n
2) T(9n/10) = T(81n/100) + 9n/10
3) T(n) = T(81n/100) + 9n/10 + n
4) T(81n/100) = T(729n/1000) + 81n/100
5) T(n) = T(729n/1000) + 81n/100 + 9n/10 + n
.
.
.
k) T(n) = T($9^k$n/$10^k$) + n($(9/10)^0$ + $(9/10)^1$ + $(9/10)^2$ + ... + $(9/10)^{k-1}$)
T(n) = T($9^k$n/$10^k$) + n$\sum_{i=0}^{k-1} (9/10)^i$
Ok this is where im stuck, i know how to solve the summation above, but the T($9^k$n/$10^k$) is throwing me off a little. In the other recurrence equations that i have solved, the extra T(n) in the equation usually ends up being zero, but even if i applied the rule $n = a^k$ i will get the following...
T(n) = T(n) + n$\sum_{i=0}^{k-1} (9/10)^i$
what am i supposed to do with the extra T(n)?
Any help will be appreciated
Why not try $a=\frac{10}{9}$? Then your recurrence relation $$T(n)=T\left(\frac{9}{10}n\right)+n$$
with the substitution $n=a^k$ becomes $$T(a^k)=T(a^{k-1})+a^k$$
Now, make the substitution $t_k=T(a^k)$ and our recurrence relation becomes
$$t_k=t_{k-1}+a^k$$
Do you know how to solve this last recurrence relation? Then you can trace back the substitutions to get a form for $T(n)$.