I have to prove the following excercise:
"Determine whether each of these proposed definitions is a valid recursive definition of a function f from the set of nonnegative integersto the set of integers. If f is well defined, find a formula for $f(n)$ when $n$ is a nonnegative integer and prove that your formula is valid."
The proposition is $f(0)=2, f(n)=f(n-1)$ if $n$ is odd and $n >= 1$ and $f(n)=2f(n-2)$ if $n>=2$
The formula I found is:
$$f(n) = 2^{\left\lceil\frac{n}{2}\right\rceil}$$
I already did the basis step where $f(1)=2, f(2)=2, f(3)=4$ and $f(4)=4$ so $f(n)$ is true for $n <= 4$.
Now comes the Inductive Step where I want to prove that $P(k+1)$ is true given that $P(k-3)$ is also true. Is this a correct assumption for the inductive step? If so, how should I proceed with the proof?
Hint:
For $n=0$, we have $f(0) = 2 \not= 2^{\left\lceil\frac{0}{2}\right\rceil} = 1$, so your formula cannot be correct. Looking at the first few terms: $$f(0) = 2$$ $$f(1) = f(1-1) = 2$$ $$f(2) = 2f(0) = 4$$ $$f(3) = f(3-1) = 4$$ $$\vdots$$
Personally, I'd try to find a formula for even $n$ (that is, $n=2k$), use induction to prove it, and then use the relation $f(2k+1) = f(2k)$.