How to retrieve closed form of a recursion

Question

I am looking for a closed form of this recursion:

$$T(0)=1$$

$$T(n) = \begin{cases} T(n-1) & \text{for odd } n \\ 2^n+T(n-2) & \text{otherwise} \end{cases}$$

Obviously this recursion leads to something like this: $$T(6) = 2^0+2^2+2^4+2^6$$ Which would be the same like this: $$T(n)=\sum_{i=0}^{\left \lfloor \frac{n}{2} \right \rfloor} 2^{2i}$$

How do I elemninate the sum now? Is there any other way to retrieve the closed form?

Btw, the solution is: $\frac{4^{\left \lfloor \frac{n}{2} \right \rfloor + 1}-1}{3}$

But looking for the way to get there.

Thanks for your help.

Answer 1

1. Let : $$x_n = T(2n)$$ Show that : $$z_n = \dfrac{x_n}{4^n} - \dfrac{4}{3}$$ is geometric.
   
2. Deduce a closed form of $T(2n)$.
   
3. For the closed form of $T(n)$ notice that : $$\left\lfloor \dfrac{2 p}{2} \right\rfloor = \left\lfloor \dfrac{2 p + 1}{2} \right\rfloor$$