# solving recurrence by substitution, calculations doesnt add up

I have this recurrence $p(n) = 2p(n-2) + n$, and I have guessed that the solution is $O(n^2)$, however, when I do the following calculations, I cannot get the inequality to hold

$p(n-2) \leq c(n-2)^2$ (induction hypothesis)

$2c(n-2)^2 + n \leq cn^2$ (substitution)

$cn^2-8c + n \leq cn^2$

Can anyone see where I go wrong? I also tried for even larger $O(n^x)$ but it still doesn't work.

• Still cant get it to work, could you perhaps show some of the steps? – sfsd May 4 '14 at 15:15
• @Guildenstern You should make that an answer. – Raphael May 4 '14 at 19:23
• Our reference question seems to have everything needed to solve this recurrence: cs.stackexchange.com/q/2789/755 – D.W. May 5 '14 at 3:44

Using the so-called substitution method, we get (for even $n$) \begin{align*} p(n) &= 2p(n-2) + n \\ &= 4p(n-4) + 2(n-2) + n \\ &= 8p(n-6) + 4(n-4) + 2(n-2) +n \\ &= \cdots \\ &= 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.)
It isn't $O(n^2)$.
Hint: $p(1)=1,p(2)=2, p(n)=p(n−2)+n$ is $O(n^2)$, but notice in what way your recurrence relation is different from this one. Try expanding it (yours). And it isn't $O(n^c)$ for some constant $c$.