How to find algebraic simplification for recurrence relation with closed-form solution, specifically for the Lucas-Lehmer primality test I have a question based on the section Proof of correctness in the article Lucas-Lehmer primality test, see following link.
https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test#Proof_of_correctness
"We begin by noting that $\langle s_i\rangle$ is a recurrence relation with a closed-form solution. Define $\omega = 2 + \sqrt{3}$ and $\bar{\omega} = 2 - \sqrt{3}; ...$"
How does $\omega$ and $\bar{\omega}$ come in to the picture? I have no problem following the prof ones $\omega$ and $\bar{\omega}$ is defined but I don't understand how they where defined in the first place.
 A: The whole setup began with Lucas. For given integers $P,Q$ we get Lucas sequences $U_n, V_n,$ where $V_n = a^n + b^n.$
In your case, $P=14, \; Q=1.$ 
Among the relations we find $$ V_{2n} = V_n^2 - 2 Q^n, $$ the fact that $Q=1$ takes us to
$$  V_{2n} = V_n^2 - 2;  $$ furthermore $V_0 = 2, V_1 = P.$
For your application, define 
$$ s_j = V_{2^{j-1}},  $$ so that $$  s_1 = V_1 = P, \; s_2 = V_2 = P^2 - 2, \; s_3 = V_4 = P^4 - 4P^2 +2.   $$
$$  s_{j+1} = s_j^2 - 2. $$
In case $P+2$ is a square, we may also define $s_0 = \sqrt{P+2}$ as another integer. With $P=14$ this works. 
So, with $Q=1,$ we get the roots $$ a = \frac{P + \sqrt{P^2 - 4}}{2}, \;  b = \frac{P - \sqrt{P^2 - 4}}{2}  $$
$$ s_j = a^{\left( 2^{(j-1)} \right)} + b^{\left( 2^{(j-1)} \right)}.  $$
Go Figure. 
EDIT: Well, I like this, and want to remember it in a simple format. 
Given any real number $t_0 > 2,$ define the sequence $t_1 = t_0^2 - 2$ and, generally, $t_{n+1} = t_n^2 - 2.$ Then,
taking
$$  \color{magenta}{ A = \frac{t_0 + \sqrt {t_0^2 - 4}}{2}, \; \; \; B = \frac{t_0 - \sqrt {t_0^2 - 4}}{2} } $$
One may check quickly that $$ AB = 1.  $$ 
Indeed, both are positive, $A$ is the larger, and
$$ A + B = t_0.   $$
So, think about it, using $AB= 1,$ also $A^m B^m = 1$ for any positive integer $m,$ 
$$ t_1 = t_0^2 - 2 = A^2 + 2 A B + B^2 - 2 =  A^2 + 2 A B + B^2 - 2 AB = A^2 + B^2.  $$
Then $$ t_2 = t_1^2 - 2 = A^4 + 2 A^2 B^2 + B^4 - 2 =  A^4 + 2 A^2 B^2 + B^4 - 2 A^2 B^2 = A^4 + B^4.  $$
Then $$ t_3 = t_2^2 - 2 = A^8 + 2 A^4 B^4 + B^8 - 2 =  A^8 + 2 A^4 B^4 + B^8 - 2 A^4 B^4 = A^8 + B^8.  $$
Pattern holds true forever, by induction: given
$$ \color{magenta}{ t_n = A^{\left( 2^n \right)} +  B^{\left( 2^n \right)},}  $$
we get
$$  t_{n+1} = t_n^2 - 2 =  A^{\left( 2^{n+1} \right)} + 2 A^{\left( 2^n \right)}   B^{\left( 2^n \right)}+ B^{\left( 2^{n+1} \right)} -2 =  A^{\left( 2^{n+1} \right)} + 2 A^{\left( 2^n \right)}   B^{\left( 2^n \right)}+ B^{\left( 2^{n+1} \right)} -2 A^{\left( 2^n \right)}   B^{\left( 2^n \right)},   $$
$$ t_{n+1} =   A^{\left( 2^{n+1} \right)} + B^{\left( 2^{n+1} \right)}.  $$
