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.

  • 7
    $\begingroup$ The keyphrase is "Pell's equation". $\endgroup$ – Gerry Myerson Feb 25 '13 at 0:33
  • $\begingroup$ @dbarbosa You must define $k_0$ and $k_1$. My answer to this question describes the method to find a closed formula in a particular example. The method used is the one described here under Linear. If you happen to guess the closed formula for a given recurrence relation you can use induction to prove it. $\endgroup$ – Git Gud Feb 25 '13 at 0:55
  • $\begingroup$ @GitGud You can use $k_0 = 0$ and $k_1 = 2$ to match with oeis definition. I am happy with the recurrence or the closed formula (for the context of the original problem that I was solving, the recurrence is actually better). Guessing + induction can be helpful, however in this case I couldn't prove that the recurrence relation was really the same sequence with induction (and I didn't guess the answer before solving the problem). I will read your other answer. $\endgroup$ – dbarbosa Feb 25 '13 at 1:46
  • $\begingroup$ @GitGud the answer that you pointed describes how to find the closed formula for a recurrence relation. Here I am actually trying to find the recurrence relation (or the closed formula) from this definition: $k$ such that $3k^2 + 4$ is a perfect square. $\endgroup$ – dbarbosa Feb 25 '13 at 1:52
  • $\begingroup$ @dbarbosa oh, ok. Sorry. I thought I misunderstood your question. $\endgroup$ – Git Gud Feb 25 '13 at 7:01

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


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

  • 5
    $\begingroup$ This is pretty much unreadable (and no justification is given for it working). $\endgroup$ – Gerry Myerson Mar 1 '13 at 12:10

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.