Could anyone show how to solve the recurrence $T(n) = 2T(n-1)+n-1$ with the initial condition $T(1) = 0$ by iteration? I've written out a couple levels of the recurrence in an attempt to see some sort of useful pattern, but I'm lost on this one. Here is what I have so far:
$\begin{array} \ T(1) &= 0 \\ T(2) &=2T(1)+n-1 &=2 \ (0) &+2-1&=2^1-1 \\ T(3) &=2T(2)+n-1 &=2\left(2^1-1\right) &+3-1&=2^2+0 \\ T(4) &=2T(3)+n-1 &=2\left( 2^2+0\right) &+4-1&=2^3+3 \\ T(5) &=2T(4)+n-1 &=2\left( 2^3+3 \right) &+5-1&=2^4 +10\\ T(6) &=2T(5)+n-1 &=2\left( 2^4+10\right) &+6-1&=2^5 +25\\ T(7) &=2T(6)+n-1 &=2\left(2^5+25 \right) &+7-1&=2^6+56 \\ \end{array}$
Hint Multiply each row by an extra power of 2.
$$\begin{array}{ccc} T(n) &= 2T(n - 1) &+ n - 1 \\ 2T(n-1) &= 4T(n - 2) &+ 2(n - 2) \\ 4T(n-2) &= 8T(n - 3) &+ 4(n - 3) \\ ...&...&...\\ 2^{n-1}T(1)&=2^nT(0)&+2^{n-1} \cdot 0 \end{array}$$
Now add everything together.