solving recurrence by substitution, calculations doesnt add up
Using the so-called substitution method, we get (for even $n$)
$$
\begin{align*}
p(n) &amp;= 2p(n-2) + n \\ &amp;= 4p(n-4) + 2(n-2) + n \\ &amp;= 8p(n-6) + 4(n-4) + 2(n-2) +n \\ &amp;= \cdots \\ &amp;= 2^{n/2} p(0) + 2^{n/2-1} 2 + 2^{n/2-2} 4 + \cdots + 2^0 n.
\end{align*}
$$
Let's assume for simplicity that $p(0) = 0$. We can write
$$
p(n) = \sum_{k=0}^{n/2-1} 2^k (n-2k) = 2^{n/2+2} - n - 4 = \Theta(2^{n/2}).
$$
(Solution courtesy of Wolfram alpha.)