# Solve Recurrence for $T(n) = 7T(n/7) + n$

I'm trying to solve the recurrence for $$T(n) = 7T(n/7) + n$$. I know using Master Theorem it's $$O(n\log_7n)$$, but I want to solve it by substitution method.

At level $$i$$, I get: $$7^i T(n/7^i) + (n+7n+7^2n+ \cdots + 7^i n)$$ By setting $$i = \log_7n$$, the above becomes: $$7^{\log_7n}\cdot T(1) + (n + 7n + 7^2n + \cdots + 7^{\log_7n}n$$

Since $$7^{\log_7n} = n$$, the above finally becomes $$n+ (n+7n+(7^2)n+ \cdots + n\cdot n)$$ This solves to $$O(n^2)$$ to me since $$n\cdot n$$ dominates, not $$O(n\log_7n)$$, any idea what's wrong?

Here is what I get: \begin{align} T(n) &= n + 7T(n/7) \\ &= n + 7(n/7) + 7^2 T(n/7^2) \\ &= n + 7(n/7) + 7^2(n/7^2) + 7^3 T(n/7^3) \end{align} and so on. Each of the summands equals $$n$$, and there are $$O(\log n)$$ of them.