|
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? |
|||
|
|
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. |
||||
|
|
|
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). |
|||
|
|
