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

Question

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?

Answer 1

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.