A question related to linear recurrence.

Question

I have seen examples such as Towers of Hanoi and Merge Sort, which I understand but when it comes to solving this kind of problems I just don't understand where to start. If given a solution to the following problem I might be able to figure out something for the rest.

Solve Linear recurrence: $$f(0) = 1, f(1) = -1$$

$$\forall n \in \mathbb{Z},f(n) = f(n-2)$$

Answer 1

The characteristic equation of the given linear recurrence is $$ \lambda^2 - 1=0, $$ thus $f(n)= c 1^n + d (-1)^n$. Substituting $f(0)=1$ and $f(1)=-1$, $$ c+d=1\\ c-d=-1 $$ Solving the linear system, we get $c=0$ and $d=1$. $$ \therefore f(n)=(-1)^n $$

Answer 2

The solution is $f(n)=(-1)^n$. To see this, note that

$$f(0)=1 \implies f(2)=f(0)=1 \implies f(4)=f(2)=1 \implies \cdots$$

and similarly

$$f(-1)=-1 \implies f(1)=f(-1)=-1 \implies f(3)=f(1)=-1 \implies \cdots$$