Csdrhrt

Let $k in mathbb{N}$ with $k geq 2$.

$x_k=frac{2}{3}x_{k-1}+frac{1}{3}x_{k-2}$

$x_0=0$

$x_1=1$

How to find the solution for $lbrace x_k rbrace _{k in mathbb{N_0}}$?

Since it's for $k geq 2$ I got:

$k=2:$

$x_2=frac{2}{3}x_1+frac{1}{3}x_0=frac{2}{3}$

But how to continue to find the solution? I thought about using induction and I get as result:

$x_{k+1}= frac{2}{3}x_k+frac{1}{3}x_{k-1}$

Here I don't know what to do next.

Write $$
x_k=frac{2}{3}x_{k-1}+frac{1}{3}y_{k-1}\
y_k = x_{k-1}
$$
so
$$
left(x_k atop y_k right)=left({frac23 quad frac13 } atop {1 quad 0 } right) left(x_{k-1} atop y_{k-1} right)
$$
which gives you
$$
left(x_k atop y_k right)=left({frac23 quad frac13 } atop {1 quad 0 } right)^k left(x_{0} atop x_1 right)
$$
So you need the powers of the matrix which can be found by eigenvalues. They are $1$ and $ - frac13$. So you can as well make the ansatz

$$
x_k = a + b (-frac13)^k
$$
solving for $a$ and $b$ gives
$$
0 = x_0 = a + b \
1 = x_1 = a + -frac{b}{3}
$$
So
$$
x_k = frac34 (1 - (-frac13)^k)
$$