Recurrence relation and invariant Consider the recurrence relation $S_{n+2} = \ 3S_{n+1}-S_n$ with $s_1=\ s_2=\ 1$
Find its invariant of the form $S^2_{n+1}\ +\  aS_nS_{n+1}\ + \ bS^2_n$ 
Although i understand that the invariant is the form such that when a transformation is applied the result is unchanged, or in this case, the distance between each number in the sequence is the same but i am not sure where to start, is it simple mathematics? Squaring the first equation and messing around with it?
 A: I believe you are trying to show that $S^2_{n+1}\ +\  aS_nS_{n+1}\ + \ bS^2_n$ stays the same as n goes to n+1. 
That is $S^2_{n+1}\ +\  aS_nS_{n+1}\ + \ bS^2_n$ = $S^2_{n+2}\ +\  aS_{n+1}S_{n+2}\ + \ bS^2_{n+1}$
Using the recurrence relationship: 
$S_{n+2} = \ 3S_{n+1}-S_n$ 
You can solve for a and b. 
A: If you write the recurrence in matrix form $\pmatrix{S_{n+2}\cr S_{n+1}\cr} = A \pmatrix{S_{n+1}\cr S_{n}\cr}$, the invariant would correspond to a matrix $B$ such that 
$A^T B A = B$.  Note that if $v$ is an eigenvector of $A$ for eigenvalue $\lambda$, 
$B v = A^T B A v = \lambda A^T B v$, so $Bv$ (if nonzero) is an eigenvector of $A^T$ for eigenvalue 
$1/\lambda$.  Fortunately, in this case $A$ has two eigenvalues that are reciprocals of each other.  If $v_1$ and $v_2$ are  eigenvectors of $A$ for eigenvalues $\lambda$ and $1/\lambda$, and $w_1$ and $w_2$ corresponding eigenvectors of $A^T$, we can define $B$ so
that $B v_1 = w_2$ and $B v_2 = w_1$.  This can be done conveniently by taking 
$B = W V^{-1}$ where $V$ is the matrix with columns $v_1$ and $v_2$ while $W$ is the matrix with columns $w_2$ and $w_1$ (note the reversed order).
