# Recurrence Relation Proof check

A question I was given

$$T(0) = 1,$$ $$T(1)=0,$$ $$T(n)= 2T(n-2)$$

I think the possible solution is $$T(n)=2^n$$

Proof: by induction. Base Case:

$$n=0$$ $$T(0)=2^0=1$$

Inductive Hypothesis: Assume for some $$n$$. $$T(n)=2^n$$ Show for $$n+1$$

$$T(n+1)= 2(T(n-1))$$ $$=2(2^{n-1})$$ $$=2^n$$

which is what I proposed. Is this correct? I'm a little confused because it says that $$T(1)=0$$, so it wouldn't make sense for $$t(n)=2^n$$. But I don't know how else I could prove the recurrence relation given as stated above.

The recurrence relation can be written as $$T(n)=2T(n-2)+O(1)$$.
Comparing with the general recurrence here $$a=2$$, $$b=2, k=0$$
Using Case 2 of the theorem we get $$T(n)= O(2^{\frac{n}{2}}*n^0) = O(2^{\frac{n}{2}})$$