Solve the following linear recurrence relations.
$$
A_n=-x A_{n-1}-\frac{1}{4}A_{n-2}
$$
This is a recurrence relations of the characteristic polynomial of a particular kind of matrix.

EDIT:
I need to prove that $M_n$ are always diagonalisable. I am only interested in $n\geq3\text{ and odd}$. $M_n$ is a tridiagonal nxn matrix. $M_n$ has 1/2 on all entries on the upper off-diagonal except the last entry, which is equal to 1. It also has 1/2 on all entries on the lower off-diagonal except the first entry, which is also equal to 1. All other entries are zero. For example:
$$
M_5=\begin{pmatrix}
0&\frac{1}{2}&0&0&0\
1&0&\frac{1}{2}&0&0\
0&\frac{1}{2}&0&\frac{1}{2}&0\
0&0&\frac{1}{2}&0&1\
0&0&0&\frac{1}{2}&0
\end{pmatrix}\

M_7=\begin{pmatrix}
0&\frac{1}{2}&0&0&0&0&0\
1&0&\frac{1}{2}&0&0&0&0\
0&\frac{1}{2}&0&\frac{1}{2}&0&0&0\
0&0&\frac{1}{2}&0&\frac{1}{2}&0&0\
0&0&0&\frac{1}{2}&0&\frac{1}{2}&0\
0&0&0&0&\frac{1}{2}&0&1\
0&0&0&0&0&\frac{1}{2}&0
\end{pmatrix}\
$$

The characteristic equation of $M_n$ is $-xA_{n-1}-\frac{1}{2}A_{n-2}, A_n=-x A_{n-1}-\frac{1}{4}A_{n-2}$. $A_n$ is the characteristic polynomial of the submatrix of $M_n$. The submatrix is generated by dropping the first row and first column of $M_n$.

For example:
$$
M_5=\begin{pmatrix}
0&\frac{1}{2}&0&0&0\
1&0&\frac{1}{2}&0&0\
0&\frac{1}{2}&0&\frac{1}{2}&0\
0&0&\frac{1}{2}&0&1\
0&0&0&\frac{1}{2}&0
\end{pmatrix}\
M_5-xI_5=\begin{pmatrix}
-x&\frac{1}{2}&0&0&0\
1&-x&\frac{1}{2}&0&0\
0&\frac{1}{2}&-x&\frac{1}{2}&0\
0&0&\frac{1}{2}&-x&1\
0&0&0&\frac{1}{2}&-x
\end{pmatrix}\

\begin{align*}
\det(M_5-xI_5)&=
-x\begin{vmatrix}
-x&\frac{1}{2}&0&0\
\frac{1}{2}&-x&\frac{1}{2}&0\
0&\frac{1}{2}&-x&1\
0&0&\frac{1}{2}&-x
\end{vmatrix}-\frac{1}{2}
\begin{vmatrix}
1&\frac{1}{2}&0&0\
0&-x&\frac{1}{2}&0\
0&\frac{1}{2}&-x&1\
0&0&\frac{1}{2}&-x
\end{vmatrix}\
&=-xA_4-\frac{1}{2}\begin{vmatrix}
-x&\frac{1}{2}&0\
\frac{1}{2}&-x&1\
0&\frac{1}{2}&-x\
\end{vmatrix}\
&=-xA_4-\frac{1}{2}A_3
\end{align*}
$$
$A_n$ has a close form solution of $A_n = \left( \dfrac{-x+\sqrt{x^2-1}}{2}\right)^n + \left(\dfrac{-x-\sqrt{x^2-1}}{2}\right)^n$ with the initial condition $A_1=-x,\,A_2=x^2-\frac{1}{2}$.

Question

Solve the following linear recurrence relations.
$$
A_n=-x A_{n-1}-\frac{1}{4}A_{n-2}
$$
This is a recurrence relations of the characteristic polynomial of a particular kind of matrix.

EDIT:
I need to prove that $M_n$ are always diagonalisable.  I am only interested in $n\geq3\text{ and odd}$.  $M_n$ is a tridiagonal nxn matrix.  $M_n$ has 1/2 on all entries on the upper off-diagonal except the last entry, which is equal to 1.  It also has 1/2 on all entries on the lower off-diagonal except the first entry, which is also equal to 1.  All other entries are zero.  For example:
$$
M_5=\begin{pmatrix}
0&\frac{1}{2}&0&0&0\
1&0&\frac{1}{2}&0&0\
0&\frac{1}{2}&0&\frac{1}{2}&0\
0&0&\frac{1}{2}&0&1\
0&0&0&\frac{1}{2}&0
\end{pmatrix}\

M_7=\begin{pmatrix}
0&\frac{1}{2}&0&0&0&0&0\
1&0&\frac{1}{2}&0&0&0&0\
0&\frac{1}{2}&0&\frac{1}{2}&0&0&0\
0&0&\frac{1}{2}&0&\frac{1}{2}&0&0\
0&0&0&\frac{1}{2}&0&\frac{1}{2}&0\
0&0&0&0&\frac{1}{2}&0&1\
0&0&0&0&0&\frac{1}{2}&0
\end{pmatrix}\
$$

The characteristic equation of $M_n$ is $-xA_{n-1}-\frac{1}{2}A_{n-2}, A_n=-x A_{n-1}-\frac{1}{4}A_{n-2}$.  $A_n$ is the characteristic polynomial of the submatrix of $M_n$.  The submatrix is generated by dropping the first row and first column of $M_n$.

For example:
$$
M_5=\begin{pmatrix}
0&\frac{1}{2}&0&0&0\
1&0&\frac{1}{2}&0&0\
0&\frac{1}{2}&0&\frac{1}{2}&0\
0&0&\frac{1}{2}&0&1\
0&0&0&\frac{1}{2}&0
\end{pmatrix}\
M_5-xI_5=\begin{pmatrix}
-x&\frac{1}{2}&0&0&0\
1&-x&\frac{1}{2}&0&0\
0&\frac{1}{2}&-x&\frac{1}{2}&0\
0&0&\frac{1}{2}&-x&1\
0&0&0&\frac{1}{2}&-x
\end{pmatrix}\

\begin{align*}
\det(M_5-xI_5)&=
-x\begin{vmatrix}
-x&\frac{1}{2}&0&0\
\frac{1}{2}&-x&\frac{1}{2}&0\
0&\frac{1}{2}&-x&1\
0&0&\frac{1}{2}&-x
\end{vmatrix}-\frac{1}{2}
\begin{vmatrix}
1&\frac{1}{2}&0&0\
0&-x&\frac{1}{2}&0\
0&\frac{1}{2}&-x&1\
0&0&\frac{1}{2}&-x
\end{vmatrix}\
&=-xA_4-\frac{1}{2}\begin{vmatrix}
-x&\frac{1}{2}&0\
\frac{1}{2}&-x&1\
0&\frac{1}{2}&-x\
\end{vmatrix}\
&=-xA_4-\frac{1}{2}A_3
\end{align*}
$$
$A_n$ has a close form solution of $A_n = \left(  \dfrac{-x+\sqrt{x^2-1}}{2}\right)^n +   \left(\dfrac{-x-\sqrt{x^2-1}}{2}\right)^n$ with the initial condition $A_1=-x,\,A_2=x^2-\frac{1}{2}$.

thomas5267 · Answer

x is not related to n.

ganeshie8 · Answer

characteristic eqn is  $r^2+xr+\frac{1}{4} = 0$

 $\implies r =  \dfrac{-x\pm\sqrt{x^2-1}}{2}$

ganeshie8 · Answer

therefore the general solution of recurrence relation is 
$$A_n = c_1\left(  \dfrac{-x+\sqrt{x^2-1}}{2}\right)^n +   c_2\left(\dfrac{-x-\sqrt{x^2-1}}{2}\right)^n$$

thomas5267 · Answer

Okay.  The initial condition is $A_1=-x,\,A_2=x^2-\frac{1}{2}$.  I plugged $n=1$ and $x=1$ and $x=\sqrt{2}$ to get $c_1=c_2=1$.

thomas5267 · Answer

Is it possible to simplify $A_n$?  Any identity relating to $(a+b)^n-(a-b)^n$?

thomas5267 · Answer

I mean $(a+b)^n+(a-b)^n$.

ganeshie8 · Answer

it looks good the way it is now
i don't see any easy way to simplify it further

recall the formula for fibonacci sequence

ganeshie8 · Answer

|dw:1441096564281:dw|

thomas5267 · Answer

Any idea how to prove this polynomial has n distinct root?

thomas5267 · Answer

I want to prove that matrix is always diagonalisable.

ganeshie8 · Answer

oh if you show that eigenvalues are distinct, then that essentially shows that enough eigenvectors are available

ganeshie8 · Answer

Is $n$ the size of matrix here ?

thomas5267 · Answer

Yes n is the size of the matrix.

ganeshie8 · Answer

and you want to prove that the polynomial eqn $A_n=0$ always has $n$ distinct roots ?

thomas5267 · Answer

I want to prove these matrices are always diagonalisable.
$$
M_5=\begin{pmatrix}
0&\frac{1}{2}&0&0&0\
1&0&\frac{1}{2}&0&0\
0&\frac{1}{2}&0&\frac{1}{2}&0\
0&0&\frac{1}{2}&0&1\
0&0&0&\frac{1}{2}&0
\end{pmatrix}\

M_7=\begin{pmatrix}
0&\frac{1}{2}&0&0&0&0&0\
1&0&\frac{1}{2}&0&0&0&0\
0&\frac{1}{2}&0&\frac{1}{2}&0&0&0\
0&0&\frac{1}{2}&0&\frac{1}{2}&0&0\
0&0&0&\frac{1}{2}&0&\frac{1}{2}&0\
0&0&0&0&\frac{1}{2}&0&1\
0&0&0&0&0&\frac{1}{2}&0
\end{pmatrix}\

M_7-xI_7=\begin{pmatrix}
-x&\frac{1}{2}&0&0&0&0&0\
1&-x&\frac{1}{2}&0&0&0&0\
0&\frac{1}{2}&-x&\frac{1}{2}&0&0&0\
0&0&\frac{1}{2}&-x&\frac{1}{2}&0&0\
0&0&0&\frac{1}{2}&-x&\frac{1}{2}&0\
0&0&0&0&\frac{1}{2}&-x&1\
0&0&0&0&0&\frac{1}{2}&-x
\end{pmatrix}\
$$
$A_n$ is the first entry of the cofactor expansion of $M_n-xI_n$.
$$
A_6=\begin{vmatrix}
-x&\frac{1}{2}&0&0&0&0\
\frac{1}{2}&-x&\frac{1}{2}&0&0&0\
0&\frac{1}{2}&-x&\frac{1}{2}&0&0\
0&0&\frac{1}{2}&-x&\frac{1}{2}&0\
0&0&0&\frac{1}{2}&-x&1\
0&0&0&0&\frac{1}{2}&-x
\end{vmatrix}\
$$

thomas5267 · Answer

Proving $A_n$ always has n distinct solution would be a good start I think.

ganeshie8 · Answer

Ahh these are special matrices
they are called tridiagonal matrices or something, very interesting ones..

thomas5267 · Answer

It is a transition matrix of a Markov chain.  I used this matrix to model the gunplay of a first person shooter called Planetside 2 XD.

ganeshie8 · Answer

Wow! cool stuff xD
you found that recurrence relation by working 1x1, 2x2, 3x3, and then using induction is it ?

thomas5267 · Answer

I didn't bother with induction.  I expanded the matrix corresponded to $A_4$ and found the empirical relations.

ganeshie8 · Answer

Ohk, I remember a nice simple way to get that earlier reccurrence relation
let me pull that up quick

ganeshie8 · Answer

here it is https://en.wikipedia.org/wiki/Tridiagonal_matrix#Determinant

ganeshie8 · Answer

okay lets get back to proving that $A_n=0$ has $n$ distinct roots

thomas5267 · Answer

I am only interested in the diagonalisability of $M_n,\,n\geq3 \text{ and is odd}$.  Actually proving $A_n$ has n distinct roots is not that useful since $\det(M_n-xI_n)$ is not $A_n$.

ganeshie8 · Answer

this looks interesting https://en.wikipedia.org/wiki/Tridiagonal_matrix#Eigenvalues

ganeshie8 · Answer

I thought $A_n$ is the characteristic polynomial of nxn matrix ?

ganeshie8 · Answer

by that, i mean solutions of $A_n=0$ are the eigenvalues that you're interested in

ganeshie8 · Answer

or did i get that whole thing wrong ?

thomas5267 · Answer

$$
\det(M-xI_n)=-xA_{n-1}-\frac{1}{4}A_{n-2}
$$

thomas5267 · Answer

I am only interested in the diagonalisability of $M_n, n\geq3\text{ and is odd}$.  $A_n$ is the characteristic polynomial of the submatrix of $M_{n+1}$ with the first row and first column removed.

thomas5267 · Answer

Sorry I didn't made it clear.

thomas5267 · Answer

Actually the characteristic polynomial of $M_n$ is not what I stated above.

thomas5267 · Answer

The relationship should be $\det(M_n-xI_n)=-xA_{n-1}-\frac{1}{2}A_{n-2}$

ganeshie8 · Answer

Okay I think I'm beginning to understand..
looks more involved than I thought..

thomas5267 · Answer

Just to reiterate.
$$
A_n = \left(  \dfrac{-x+\sqrt{x^2-1}}{2}\right)^n +  \left(\dfrac{-x-\sqrt{x^2-1}}{2}\right)^n$$

ganeshie8 · Answer

not so sure how you got that relation but it seems
 you want to show $-xA_{n-1}-\frac{1}{2}A_{n-2}=0$ has $n$ distinct solutions

thomas5267 · Answer

Yes.  I want to show $\det(M_n-xI_n)=-xA_{n-1}-\frac{1}{2}A_{n-2}=0$ has n distinct solution.

ganeshie8 · Answer

something is wrong

ganeshie8 · Answer

nvm

thomas5267 · Answer

$$
M_5=\begin{pmatrix}
0&\frac{1}{2}&0&0&0\
1&0&\frac{1}{2}&0&0\
0&\frac{1}{2}&0&\frac{1}{2}&0\
0&0&\frac{1}{2}&0&1\
0&0&0&\frac{1}{2}&0
\end{pmatrix}\
M_5-xI_5=\begin{pmatrix}
-x&\frac{1}{2}&0&0&0\
1&-x&\frac{1}{2}&0&0\
0&\frac{1}{2}&-x&\frac{1}{2}&0\
0&0&\frac{1}{2}&-x&1\
0&0&0&\frac{1}{2}&-x
\end{pmatrix}\

\begin{align*}
\det(M_5-xI_5)&=
-x\begin{vmatrix}
-x&\frac{1}{2}&0&0\
\frac{1}{2}&-x&\frac{1}{2}&0\
0&\frac{1}{2}&-x&1\
0&0&\frac{1}{2}&-x
\end{vmatrix}-\frac{1}{2}
\begin{vmatrix}
1&\frac{1}{2}&0&0\
0&-x&\frac{1}{2}&0\
0&\frac{1}{2}&-x&1\
0&0&\frac{1}{2}&-x
\end{vmatrix}\
&=-xA_4-\frac{1}{2}\begin{vmatrix}
-x&\frac{1}{2}&0\
\frac{1}{2}&-x&1\
0&\frac{1}{2}&-x\
\end{vmatrix}\
&=-xA_4-\frac{1}{2}A_3
\end{align*}
\
$$

thomas5267 · Answer

$A_n$ are all polynomials from 1 to 10.

ganeshie8 · Answer

right, i see..

ganeshie8 · Answer

thats really a clever derivation for determinant !
il give it a try in the evening again, right now i must go..

thomas5267 · Answer

Thank you!  It is not really that hard to find once you tried to find the characteristic polynomial of $M_n$ by induction.

thomas5267 · Answer

$$
\begin{align*}
\det(M_n-x I_n)&=-xA_{n-1}-\frac{1}{2}A_{n-2}\
&=A_n-\frac{1}{4}A_{n-2}
\end{align*}
$$

thomas5267 · Answer

The eigenvalues of $M_{n},\,n\geq3 \text{ and odd}$ are symmetric (x and -x are both eigenvalues.) and distinct.  0 is always one of the eigenvalues.  The characteristic polynomial is also odd.

thomas5267 · Answer

@Kainui Help!