How to find a "better description" (e.g. recurrence relation) for this sequence? My solution to a problem in Project Euler required to solve this subproblem: find values of $k\in\mathrm{N}$ such that $3k^2+4$ is a perfect square.
As I was writing a computer program, I just tried all $k$ and checking if $3k^2+4$ is a perfect square. I solved the problem, but this is not efficient and it doesn't really answer the question.
It turns out that this sequence is http://oeis.org/A052530, there is an easy recurrence relation ($k_n = 4k_{n-1} - k_{n-2}$), and some closed-form formulas for $k_n$ (e.g. $k_n = \left((2+\sqrt{3})^n-(2-\sqrt{3})^n\right)/\sqrt{3}$).
Now I know some answers, but I still don't see how to derive them from the definition. Also, I wasn't able to prove that the recurrence relation works (given that $k_{n-2}$ and $k_{n-1}$ are to consecutive terms of the sequence, prove that $4k_{n-1} - k_{n-2}$ is a term in the sequence, and that it is next term).
So my question is: given the definition of the sequence ($k\in\mathrm{N}$ such that $3k^2+4=n^2$), how can I find a recurrence relation for this sequence?
I will be very happy if can use the same procedure for other similar sequences.
 A: Suppose $$3k^2+4=m^2$$ so that $$m^2-3k^2=4$$
or $$(m+\sqrt3k)(m-\sqrt3k)=4$$
and we are also able to find a solution to
$$p^2-3q^2=1$$$$(p+\sqrt3q)(p-\sqrt3q)=1$$
Then $$(p+\sqrt3q)(p-\sqrt3q)(m+\sqrt3k)(m-\sqrt3k)=(p+\sqrt3q)(m+\sqrt3k)(p-\sqrt3q)(m-\sqrt3k)=4$$which becomes$$\left((pm+3kq)+(pk+qm)\sqrt3\right)\left((pm+3kq)-(pk+qm)\sqrt3\right)=4$$so that $$(pm+3kq)^2-3(pk+qm)^2=4$$
We note that $p=2, q=1$ works (and is the minimal solution), so that given a solution $(m,n)$, we have another solution $(2m+3k, 2k+m)$.
A: $3k^2+4=n^2$ ; as $n\to \infty$, $3k^2\cong n^2$ ; so $\sqrt 3\cong n/k, \sqrt 3-(n/k)\cong 0$ ; taking $\sqrt 3=x ;kx-n\cong (+/-)0, 
(kx-n)^m\to 0$, as $m\to \infty$
$2-x=2-1.732051=0.267949$ 
$(2-x)^2=(2^2+x^2-2\times 2\times x)=(7-4x)=0.071797$
$(7^2+4^2\times 3-2\times 7\times 4x)=(97-56x)=0.005155$
$(a_1-b_1\times x)\cong 0 $;then $a_1^2+3\times b_1^2-2\times a_1\times b_1\times x = (a_1-b_1\times x)^2 \cong 0 $or$\to  a_2-b_2\times x\cong 0$ , where $a_2=a_1^2+3\times b_1^2 ;b_2=2\times a_1\times b_1$, 
in this case $7^2-4^2\times 3 =1 ;97^2-3\times 56^2 =9409-9408=1$
This process can be repeated.
A: To derive the solution to your recurrence, you assume there is a solution of the form $r^n$.  Plugging that into the recurrence gives the characteristic polynomial $r^2=4r-1$ with solutions $r=2\pm \sqrt 3$.  Because your equation is linear and homogenous, any linear combination of the solutions is again a solution and the general solution is $k_n=a(2+\sqrt 3)^n+b(2-\sqrt 3)^n$  You evaluate $a,b$ from your initial conditions $k_0=0, k_1=2$
You can observe another recurrence:  if $(k_n,m_n)=\left(k_n,\sqrt{3k_n^2+4}\right)$ is a pair in your series, $(k_{n+1},m_{n+1})=(2k_n+m_n,2m_n+3k_n)$ is the next.
Once you have this recurrence, you can observe that $m_{n+1}^2-3k_{n+1}^2=(2m_n+3k_n)^2-3(m_n+2k_n)^2=4m_n^2+12m_nk_n+9k_n^2-3m_n^2-12m_nk_n-12k_n^2=m_n^2-3k_n^2$ which shows $3k_{n+1}^2+4$ is a square because $3k_n^2+4$ was.
This doesn't show how to find your recurrence, nor that this gets all the $(k,m)$ pairs.
