I've got the following problem in linear algebra under chapter eigenvector and eigenvalue.
Determine $x_{n}$ if $$\left\{\begin{matrix} x_{1}=3\\ x_{2}=0\\ x_{n}=x_{n-1}+2x_{n-2},\ n=3,4... \end{matrix}\right.$$
The answer is: $$x_{n}=2(-1)^{n-1}+2^{n-1}$$
I do not understand the problem. How should I handle this?
The equation is linear, and this is why it is relevant in the context of linear algebra: if you find several independent solutions, their linear combination will also be a solution.
Now, to get some inspiration about the possible shape of a solution, let us consider the simpler
$$z_0=1,z_n=2z_{n-1}.$$
The first terms are $z_1=2,z_2=4,z_3=8,\cdots$ and the obvious pattern $z_n=2^n$ appears. Hence, for the original problem we will try
$$x_n=r^n.$$
Plugging in the recurrence,
$$r^n=r^{n-1}+2r^{n-2},$$ or after simplification
$$r^2=r+2.$$
Solving this quadratic equation, we have established that $2^n$ and $(-1)^n$ are two solutions, and any linear combination $$a\,2^n+b\,(-1)^n$$ is also a solution. You can determine $a,b$ by using the extra information available.
Theory shows that a linear recurrence of order $k$ (largest difference between the term indexes, here $k=2$) has exactly $k$ independent solutions, which form a basis for the general solution.