title: Solve Recurrence for T(n) = 7T(n/7) + n
body: <p>I'm trying to solve the recurrence for <code>T(n) = 7T(n/7) + n</code>.
  I know using Master Theorem it's <code>O(nlog7n)</code>, but I want to solve it by substitution.</p>
  <p>At level i, I get: <code>7^i T(n/7^i) + (n+7n+7^2n+ .... + 7^i n)</code>
  By setting <code>i = log7n</code>, the above becomes: <code> 7^(log7n)*T(1) + (n + 7n + 7^2n ..... + 7^(log7n) n</code></p>
  <p>Since <code>7^log7n = n</code>, the above finally becomes <code>n+ (n+7n+(7^2)n+ ....n*n)</code>
  This solves to <code>O(n^2)</code> to me not <code>O(nlog7n)</code>, any idea what's wrong?</p>