Solving recurrence equations with repeated substitution?

Question

Say we have a recurrence equation as

$$ T(n) = \begin{cases} T\left(\frac n2\right) +n & \text{if }n\ge2 \\ 1 & \text{if }n=1 \end{cases} $$

Would the first substitution be like this?

$$\left(T\left(\frac n4\right) + \frac n2\right) + n$$

A little confused with these. If you could show the first 3 or so steps, or any other help would be greatly appreciated :)

Answer 1

Let $n = 2^k$.

$$\begin{align}T\left(n\right) & = T\left(\frac n2\right) + n \\ &= \left[T\left(\frac n4\right) + \frac n2\right] + n\\ & = \left[T\left(\frac n8\right) + \frac n4\right] + \frac n2 + n\\ & = \dots\\ & = T\left(\frac n{2^k}\right) + \left[n + \frac n2 + \frac n4 + \cdots + \frac{n}{2^{k-1}}\right]\\ & = 2n - 1\end{align}$$