Fermat's Difference Equation / Pell's Equation Solve the equation $x^2-5y^2=4$ in positive integers. 
I know that the base case is $(3,1)$, but I don't know how to get the general form (like how you do it at a pell equation)
I have the basic solutions $(3,1)$, $(4,2)$, $(11,5)$, $(29,13)$, and $(76,34)$. 
The values of $y$ mysteriously correspond to alternating terms in the Fibonacci Sequence [1], 1, [2], 3, [5], 8, [13], 21, [34]. Interesting...
 A: Note that $\frac {1+\sqrt 5}{2}\frac {1-\sqrt 5}2=-1$ so that if $$a^2-5b^2=(a+b\sqrt 5)(a-b\sqrt 5)=\pm4$$ then $\frac {1+\sqrt 5}{2}\frac {1-\sqrt 5}2(a+b\sqrt 5)(a-b\sqrt 5)=\mp 4$ and this means that $$\left(\frac {a+5b}2+\frac{a+b}2\sqrt 5\right)\left(\frac {a+5b}2-\frac{a+b}2\sqrt 5\right)=\mp 4$$
(*)This is obtained by pairing the factors with $+\sqrt 5$ and the factors with $-\sqrt 5$ and gives $$ \left(\frac {a+5b}2\right)^2-5\left(\frac {a+b}2\right)^2=\mp4$$
You then get a sequence $(a,b), (\frac {a+5b}2, \frac {a+b}2), (\frac {3a+5b}2, \frac {a+3b}2) \dots $ where alternating  elements give the same sign in the original equation.
The connection with the Fibonacci Sequence is easy to see. You can start with $(a,b)=(1,1)$

The point with this kind of equation is that you can generate additional solutions once you know one solution and some number which is a unit (i.e. a solution to the equation which gives the answer $\pm 1$). What you are really looking for is a fundamental unit - which generates the group of units in the relevant number field. You can then establish a recurrence to find solutions. Here it is $\frac {1+\sqrt 5}2$ which plays that role.
One way of showing that you have all the solutions is to show that you can work back from any solution to a minimum one. If at the stage (*) above you mix the terms so that each term with $+\sqrt 5$ is matched with a term with ${-\sqrt 5}$ then you will find that the solutions decrease.

Looking at the three terms of the sequence noted above $(a_1, b_1)=(a,b); (a_2, b_2)=(\frac {a+5b}2, \frac {a+b}2); (a_3, b_3)=(\frac {3a+5b}2 \frac {a+3b}2)$ it is clear that for any three consecutive terms $$a_1+a_2=a_3$$$$b_1+b_2=b_3$$
This makes it clear that the numbers involved are all integers (once two consecutive integer pairs are found).
The terms in the first place are Lucas Numbers and in the second place are Fibonacci Numbers.

Solutions giving $+4$ are $$(3,1); (7,3); (18,8); (47, 21); (123, 55) \dots $$
Solutions giving $-4$ are $$(1,1); (4,2); (11, 5); (29, 13); (76, 34) \dots$$
