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.

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