Recurrence doesn't add up
The hints you've been given almost work. The important idea is that your guess, $T(n)≤c2^{n/2}$, while correct, doesn't behave nicely in your induction proof, as you noted. What's the problem? Clearly, it's that "$+n$" term in the recurrence, so let's try to make it work by choosing a better guess:
$$
T(n)≤c2^{n/2}−kn \quad\text{for some suitable } k
$$

With this guess, we'll have
$$\begin{align}
T(n)&amp;=2T(n−2)+n\\
&amp;\le 2(c2^{(n−2)/2}−k(n−2))+n\\
&amp;=c2^{n/2}−2k(n−2)+n\\
&amp;=c2^{n/2}−2kn+4k+n
\end{align}$$
and if we can find a suitable $k$ to make this less than or equal to $c2^{n/2}−kn$ we'll be done. In other words, we need to find $k$ such that
$$
−2kn+4k+n≤kn
$$
It's not hard to see that this will happen if
$$
k\ge\frac{n}{n−4}
$$
and this will be satisfied when $k=5$ for any integer $n&gt;4$. Now go back to the inductive proof and recast it for the guess $T(n)\le c2^{n/2}−5n$. You'll find that everything works nicely. Finally, observe that $c2^{n/2}−5n=O(2^{n/2})$ and you'll be done.

This is explained in a bit more detail in this answer to a similar question.