Solving divide and conquer recurrence

Question

I have a recurrence $T(n)$ with only powers of two being valid as values for $n$.

$$T(1) = 1$$ $$T(n) = n^2 + \frac{n}{2} - 1 + T(\frac{n}{2})$$

I tried to substitute $n=2^m$, which yields the following recurrence:

$$S(m) := T(2^m)$$ $$S(0) = 1$$ $$S(m) = 4^m + 2^{m-1} - 1 + S(m-1)$$

This new $S(m)$ is now somewhat of a linear recurrence which I learned how to solve, but the $4^m$ and $2^{m-1}$ are still a problem for me. WolframAlpha gives me a solution to this recurrence, which I managed to prove as right through induction.
However, I would like to know how I can actually determine this solution without Wolfram.

Answer 1

You can just apply the formuala recursively to get:

$$ S(m) = 4^m + 2^{m-1} - 1 + S(m-1) \\ S(m-1) = 4^{m-1} + 2^{m-2} - 1 + S(m-2) \\ S(m-2) = 4^{m-2} + 2^{m-3} - 1 + S(m-3) \\ S(m-3) = 4^{m-3} + 2^{m-4} - 1 + S(m-4) \\ \dots\\ S(1) = 4 + 2^0 - 1 + S(0) \\ $$

By summing the "columns" you get

$$ S(m) = \sum_{k=1}^m4^k +\sum_{k=0}^{m-1}2^k - m + S(0) $$

Answer 2

By expanding the recurrence, the solution is $S(0)$ plus the sum of $4^k+2^{k-1}-1$ for $k=1...m$.

Computing the sums of the geometric sequences shouldn't be a problem to you.