How to solve this homogeneous recurrence relation

Question

I have the homogeneous recurrence relation $x_n = x_{n-2}$ for $n \geq 2$ with $x_1 = 2$ and $x_0 = 1$. So for the characteristic polynomial I got $r^2 - r = 0$, then I factored out r: $r(r - 1)$ for which the roots then are: $r = 0, 1$. I then pluck the values into the function $x_n = \alpha (0^n) + \beta (1^n)$. Now solve for the first 2 values: $x_0 = 1 = \alpha (0^0) + \beta (1^0) = \beta (1^0)$ $\Rightarrow \beta = 1$ . And $x_1 = 2 = \alpha (0^1) + \beta (1^1)$ $\Rightarrow \beta = 2$. So I'm obviously making a mistake here since $\beta$ can't be $1$ and $2$ but I'm kind of lost, what am I missing here? Can somebody help me to get to the right solution?

Answer 1

Hint: Characterisitc polynomial corresponding to $x_n=x_{n-2}$ is $r^2-1=0$ solving which yields $r=1, r=-1$ and general solution will be as given by Yves Daoust after using base cases.

Answer 2

You can solve without the standard machinery just by observing

$$\begin{cases}x_0=x_2=x_4\cdots=1,\\x_1=x_3=x_5\cdots=2.\end{cases}$$

Then $$\begin{cases}x_{even}=1,\\x_{odd}=2.\end{cases}$$

As the values are alternating, you can rewrite this as a single line formula

$$x_n=\frac{3-(-1)^n}2.$$

Answer 3

$x_n=x_n-2$ divide everything by $g^{n-2}$, this will be: $$g^n=g^{n-2}$$ $$g^2=1$$ I guess you can solve the rest by yourself