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?
Asked
Active
Viewed 110 times
0
-
Be careful with $0^0$! – guestDiego Jun 09 '16 at 10:16
-
1Your characteristic polynomial is wrong. – Jun 09 '16 at 10:17
-
Ok! There is also the fact that characteristic polynomial is wrong! – guestDiego Jun 09 '16 at 10:18
-
See https://en.wikipedia.org/wiki/Recurrence_relation#Solving – lab bhattacharjee Jun 09 '16 at 10:18
-
how is the characteristic polynomial wrong? – imc Jun 09 '16 at 10:19
-
it will be $r^2-1 =0$. – CKM Jun 09 '16 at 10:21
-
@imc: you wrote a polynomial corresponding to $x_{n}=x_{n-1}$, referenced to $x_{n-2}$. – Jun 09 '16 at 10:24
3 Answers
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.$$
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.
CKM
- 1,594
0
$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
