# Thread: Challenge problem #7 [GLaw]

1. ## Challenge problem #7 [GLaw]

Prove that there are infinitely many natural numbers $n$ such that $5n^2+4$ is a perfect square. Is this also true for $5n^2-4$?

2. ## Re: Challenge problem #7 [GLaw]

Spoiler:
I can't prove anything but a bit of toying around shows that

the recurrent sequence

$a_n=3 a_{n-1}-a_{n-2},~~a_0=0, ~a_1=1, ~2\leq n$

will always satisfy

$\sqrt{5 a_n^2 + 4} \in \mathbb{N}$

and the same sequence with initial conditions $a_0=a_1=1$

will always satisfy

$\sqrt{5a_n^2 -4} \in \mathbb{N}$

3. ## Re: Challenge problem #7 [GLaw]

Spoiler:
Define the Fibonacci sequence

$n_0\ =\ 0,\ n_1\ =\ 1$
$n_k\ =\ n_{k-1}+n_{k-2},\ k\geq2$

Then

$n_k\ =\ \frac1{\sqrt5}\left[\left(\frac{1+\sqrt5}2\right)^k-\left(\frac{1-\sqrt5}2\right)^k\right]$

as can be verified by induction (or otherwise).

Using this formula, we can check that

$n_{k+1}^2\ =\ \frac15\left[\left(\frac{3+\sqrt5}2\right)\left(\frac{1+\sqrt5} 2\right)^{2k} + \left(\frac{3-\sqrt5}2\right)\left(\frac{1-\sqrt5}2\right)^{2k} + 2(-1)^k\right]$

$n_kn_{k+1}\ =\ \frac15\left[\left(\frac{1+\sqrt5}2\right)^{2k+1} + \left(\frac{1-\sqrt5}2\right)^{2k+1} - (-1)^k\right]$

$n_k^2\ =\ \frac15\left[\left(\frac{1+\sqrt5}2\right)^{2k} + \left(\frac{1-\sqrt5}2\right)^{2k} - 2(-1)^k\right]$

Hence the following relation is satisfied:

$\boxed{n_{k+1}^2 - n_kn_{k+1} - \left[n_k^2+(-1)^k\right]\ =\ 0}$

This is a quadratic equation in $n_{k+1}$; its discriminant is $5n_k^2+4$ when k is even. This must be a perfect square since $n_{k+1}$ is an integer, and since there are infinitely many Fibonacci numbers such that k is even, there are infinitely many integers n such that $5n^2+4$ is a perfect square.

Similarly the discriminant is $5n_k^2-4$ when k is odd; this must be a perfect square, and as there are infinitely many Fibonacci numbers such that k is odd, there are also infinitely many integers n such that $5n^2-4$ is a perfect square.

4. ## Re: Challenge problem #7 [GLaw]

Solution:

Define a sequence as follows:

$a_1\ =\ 1$

$a_{n+1}\ =\ \frac{a_n+\sqrt{5a_n^2+4(-1)^n}}2\quad\left(n\in\mathbb N\right)$

If $a_n\ge1$ then $5a_n^2+4(-1)^n\ge1$ and $a_{n+1}\ge\frac{1+1}2=1$; since $a_1=1\ge1$ it follows by induction that $a_n\ge1$ for all $n\in\mathbb N$. Thus $\left(a_n\right)_{n\in\mathbb N}$ is a sequence of positive real numbers.

Now

$a_{n+1}\ =\ \dfrac{a_n+\sqrt{5a_n^2+4(-1)^n}}2\quad\left(n\in\mathbb N\right)$

$\implies\ \left(2a_{n+1}-a_n\right)^2\ =\ 5a_n^2+4(-1)^n$

$\implies\ a_n^2+a_{n+1}a_n-a_{n+1}^2+(-1)^n$

Noting that $a_n>0$ we get

$a_n\quad=\ \frac{-a_{n+1}+\sqrt{5a_{n+1}^2-4(-1)^n}}2$

$=\ -a_{n+1}+\frac{a_{n+1}+\sqrt{5a_{n+1}^2+4(-1)^{n+1}}}2$

$=\ -a_{n+1}+a_{n+2}$

Hence the $a_n$ form a Fibonacci sequence with $a_1=a_2=1$ and so are all integers. Hence $5a_n^2+4(-1)^n=\left(2a_{n+1}-a_n\right)^2$ is a perfect square for all n. As there are infinitely many even terms of the Fibonacci sequence, there are therefore infinitely many n such that $5n^2+4$ is a perfect square. Similarly there are infinitely many such that $5n^2-4$ is a perfect square as the Fibonacci sequence has infinitely many odd terms.