Why is my induction solution to T(n) = T(7n/10)+n wrong?

Question

I want to solve the recurrence $T(n) = T(7n/10)+n$ I know I can use the master theorem but I want to do it using the substitution method. The first thing I did to find a good guess was to use the recursive tree method. I know that $7n/10 = n/(10/7)$ so I wrote that the tree will have $log10/7(n)+1$ levels ( because multiplying the size of n by 7n/10 at each iteration is like to divide it by 10/7 ). The $log10/7(n)$ first levels each have a total cost of (i being the number of the level) $(7/10)^{(i)}*n$, the last level contain only 1 node and it cost $Θ(1)$ so the total is $ (\sum_{i=0}^{\log(10/7)(n)-1} n*(7/10)^i) + Θ(1) = (n*\sum_{i=0}^{\log10/7(n)-1}(7/10)^i )+ Θ(1) = (n*((7/10)^{log(10/7)(n)}-1)/(7/10-1))+Θ(1) = (n*(n^{log10/7(7/10)}-1)/(7/10-1))+Θ(1) $ Which is clear not $Θ(n)$ But the master theorem gives Θ(n} ( as well as wolframalpha ) I know I did an error somewhere but I don't find it when I read my reasoning, can you help me please ? Thank you

Answer 1

Unraveling the tree gives a term depending on the initial data plus something like $n \sum_{i=c}^{\log_{10/7}(n)} (7/10)^i$. Where exactly the sum starts and ends depends on how exactly you initialize the recursion, which is not important to the asymptotics.

That sum converges to a finite nonzero number as $n \to \infty$, so it is just $\Theta(1)$. So overall you get $T(n)=\Theta(n)$. (It may be helpful in similar problems to recall that $\sum_{i=a}^b r^i = \frac{r^a-r^{b+1}}{1-r}$.)