$T(n) = 2T(n-2) + 1$ recursion tree

Question

Can someone help me build what the recursion tree would look like for this problem? Would the next level be $n-3$, and then $n-4$?

Answer 1

I like moving the extra term to the front when solving these kinds of problems. $$\begin{align} T(n)&=1+2T(n-2)\\ &=1+2(1+2T(n-4))=1+2+4T(n-4)\\ &=1+2+4(1+2T(n-6))=1+2+4+8T(n-6)=\dots\\ &=(2^{n/2}-1)+2^{n/2}T(0)\\ &=\Theta(2^{n/2}) \end{align}$$

Answer 2

Let $T(n)=2^{\frac{n}{2}}. A(n)$ $$. $$ Hence $T(n-2)=2^{\frac{n-2}{2}}.A(n-2)$ put in given equation we get $$2^{\frac{n}{2}}A(n)=2^{\frac{n}{2}}A(n-2)+1$$ $$\therefore A(n)-A(n-2)=2^{-\frac{n}{2}}$$ $$\sum_{n=2}^{n} (A(n)-A(n-2))=\frac{2^{\frac{n-1}{2}}-1}{2^{\frac{n}{2}}}=y \,(say)$$ Hence $ A(n)+A(n-1)-A(0)-A(1)=y$ $$T(n).2^{-\frac{n}{2}}+T(n-1).2^{-\frac{n-1}{2}}=y+T(0)+\frac{T(1)}{\sqrt{2}}$$