Solve the reccurence relation for $T(n) = 2T(n/2) + n − 1, n > 1, T(1) = 0, n = 2^k$ Even though it's pretty similar to other questions, I'm confusing myself with the answer because I always end up with:
$$
T(2^k)=\log_2⁡n-\log_2⁡n
$$
which doesn't seem right at all. Plus, I'm not sure whether the final big theta notation would be $\Theta(\log_2⁡n)$ or $\Theta(1)$.
I don't know what else to do. Any help would be appreciated.
EDIT: Here's the obvious extremely wrong attempt:
\begin{align*}
A(2^k )&=2A(2^{k-1} )+2^k-1\\
&=(2A(2^{k-2} )+2^k-1)+2^k-1
&&=2A(2^{k-2} )+2(2^k)-2\\
&=(2A(2^{k-3} )+2^k-1)+2(2^k)-2
&&=2A(2^{k-3} )+3(2^k)-3
\end{align*}
$$
A(2^k)=2A(2^{k-i} )+i(2^k)-i
$$
sub in $i = k$:
\begin{align*}
A(2^k)&=2A(2^{k-k} )+k(2^k)-k  \\
&=2A(2^0 )+k(2^k)-k &&  \\
&=\log_2⁡n-\log_2⁡n\\
\end{align*}

You wrote
$$\color{red}{2A(2^{k-1} )}+2^k-1=\color{red}{(2A(2^{k-2} )+2^k-1)}+2^k-1.$$
But you seem to assume $2A(2^{k-1}) = 2A(2^{k-2}) + 2^k - 1$, which is incorrect.
It should be
\begin{align*}
2 \cdot A(2^{k-1}) &= 2 \cdot (2A(2^{k-2}) + 2^{k-1} - 1) \\
&= 4A(2^{k-2}) + 2^k - 2.
\end{align*}
