solutions of system that define by induction

Question

I'm new on studying Systems of equations. I just want to know how to prove that solutions of this system of equations: \begin{align} a_0 &= 2\\ a_1 &= 1\\ a_2 &= -1\\ a_{n+1} &= a_n - a_{n-1} \end{align} is $$ a_n = \frac{(1+i\sqrt{3})^n+(1-i\sqrt{3})^n}{2^n} $$

The problem is they give me the solutions but I don't how they find it from the system of equations.

Answer 1

Given a homogeneous linear recurrence of the form: $$a_n = \alpha_1 a_{n-1} + \alpha_2 a_{n-2}+\dots + \alpha_k a_{n-k}$$

We look to the associated characteristic polynomial:

$$x^k - \alpha_1 x^{k-1} - \dots - \alpha_k=0$$

The roots of the polynomial will imply what the general form of the solution will look like. If $\lambda$ is a root of the characteristic polynomial, then $\lambda^n$ satisfies the linear recurrence. If $\lambda$ is a repeated root, then so too will $n\lambda^n$ satisfy the recurrence, on up to $n^{r-1}\lambda^n$ where $r$ is the multiplicity of the root.

Applying arbitrary constants to each of these found terms and using the initial conditions will allow you to solve for exactly what the general form is.

---

For your specific example, you have the recurrence: $a_n = a_{n-1}-a_{n-2}$. (Yes, I know that you wrote it as $a_{n+1}=a_n-a_{n-1}$, they are equivalent)

This has characteristic polynomial: $x^2-x+1=0$

The roots of the polynomial are: $\frac{1\pm \sqrt{-3}}{2}$

This implies that the general solution should be of the form $a_n = c_1\left(\frac{1+\sqrt{-3}}{2}\right)^n+c_2\left(\frac{1-\sqrt{-3}}{2}\right)^n$

Using that $a_0=2$ and $a_1=1$, this tells us that $c_1 + c_2 = 2$ and $c_1\left(\frac{1+\sqrt{-3}}{2}\right) + c_2\left(\frac{1-\sqrt{-3}}{2}\right)=1$

Solving the remaining system of two equations and two unknowns will tell you what $c_1$ and $c_2$ are equal to and thus the general form of the sequence.

As it so happens, solving the system of equations will tell you that $c_1=1$ and $c_2=1$, implying the general form of the sequence is:

$$a_n = \left(\frac{1+\sqrt{-3}}{2}\right)^n+\left(\frac{1-\sqrt{-3}}{2}\right)^n$$

which can be rewritten as above in the original question.

---

As an aside, that we call it a "characteristic polynomial" is not a coincidence. This is exactly the same as the characteristic polynomial of a matrix $\det(A-\lambda I)$ from linear algebra. This comes from interpreting the linear recurrence as a matrix, solving for the eigenvalues/eigenvectors, and diagonalizing the matrix. The language of eigenvalues/eigenvectors however are unnecessary here, and the technique can be taught without ever needing to know the connection.

Answer 2

An explanation in terms of linear algebra:

Consider $T(a_n, a_{n+1}) = (a_n, a_n - a_{n-1})$.

Take T to any power $n$ with the initial values $a_0 = 2$ and $a_1 = 1$ and you'll get $a_n$.

The eigenvalues of this matrix are the roots of $x^2 - x + 1$. Express T with respect to the corresponding eigenvectors and you'll get a diagonal matrice. Taking the diagonal matrice to an arbitrary power is easy and yields the result after you change basis.