Challenge problem #2 Show that 5φ^2n+4(−1)^n is a perfect square

[Olinguito]

Define a Fibonacci sequence by
$$\varphi_0=0,\,\varphi_1=1;\ \varphi_{n+2}=\varphi_{n+1}+\varphi_n\ \forall \,n\in\mathbb Z^+\cup\{0\}.$$
Show that
$$5\varphi_n^2+4(-1)^n$$
is a perfect square for all non-negative integers $n$.

 

[Opalg]

Define a Fibonacci sequence by
$$\varphi_0=0,\,\varphi_1=1;\ \varphi_{n+2}=\varphi_{n+1}+\varphi_n\ \forall \,n\in\mathbb Z^+\cup\{0\}.$$
Show that
$$5\varphi_n^2+4(-1)^n$$
is a perfect square for all non-negative integers $n$.

[sp]Let $A = \begin{bmatrix}0&1\\1&1\end{bmatrix} = \begin{bmatrix}\varphi_0&\varphi_1\\ \varphi_1&\varphi_2\end{bmatrix}$. By induction, $A^n = \begin{bmatrix}\varphi_{n-1}&\varphi_n\\ \varphi_n&\varphi_{n+1}\end{bmatrix}$. The inductive step is given by the calculation $$A^{n+1} = A^nA = \begin{bmatrix}\varphi_{n-1}&\varphi_n\\ \varphi_n&\varphi_{n+1}\end{bmatrix} \begin{bmatrix}0&1\\1&1\end{bmatrix} = \begin{bmatrix}\varphi_{n}&\varphi_{n-1} + \varphi_n\\ \varphi_{n+1}&\varphi_{n}+\varphi_{n+1}\end{bmatrix} = \begin{bmatrix}\varphi_{n}&\varphi_{n+1}\\ \varphi_{n+1}&\varphi_{n+2}\end{bmatrix}.$$ Since $\det A = -1$, it follows that $\det A^n = (-1)^n$. Therefore $\varphi_{n-1}\varphi_{n+1} - \varphi_{n}^2 = (-1)^n$. Then $$ \varphi_{n}^2 + (-1)^n = \varphi_{n-1}\varphi_{n+1} = \varphi_{n-1}(\varphi_{n} + \varphi_{n-1}) = \varphi_{n}\varphi_{n-1} + \varphi_{n-1}^2,$$ $$4\varphi_{n}^2 + 4(-1)^n = 4\varphi_{n}\varphi_{n-1} + 4\varphi_{n-1}^2, $$ $$5\varphi_{n}^2 + 4(-1)^n = \varphi_{n}^2 + 4\varphi_{n}\varphi_{n-1} + 4\varphi_{n-1}^2 = (\varphi_{n} + 2\varphi_{n-1})^2, $$ which is a perfect square since $\psi_{n} = \varphi_{n} + 2\varphi_{n-1}$ is an integer.

(The numbers $\psi_n$ are the Lucas numbers.)[/sp]

 

[Olinguito]

[sp]Let $A = \begin{bmatrix}0&1\\1&1\end{bmatrix} = \begin{bmatrix}\varphi_0&\varphi_1\\ \varphi_1&\varphi_2\end{bmatrix}$. By induction, $A^n = \begin{bmatrix}\varphi_{n-1}&\varphi_n\\ \varphi_n&\varphi_{n+1}\end{bmatrix}$. The inductive step is given by the calculation $$A^{n+1} = A^nA = \begin{bmatrix}\varphi_{n-1}&\varphi_n\\ \varphi_n&\varphi_{n+1}\end{bmatrix} \begin{bmatrix}0&1\\1&1\end{bmatrix} = \begin{bmatrix}\varphi_{n}&\varphi_{n-1} + \varphi_n\\ \varphi_{n+1}&\varphi_{n}+\varphi_{n+1}\end{bmatrix} = \begin{bmatrix}\varphi_{n}&\varphi_{n+1}\\ \varphi_{n+1}&\varphi_{n+2}\end{bmatrix}.$$ Since $\det A = -1$, it follows that $\det A^n = (-1)^n$. Therefore $\varphi_{n-1}\varphi_{n+1} - \varphi_{n}^2 = (-1)^n$. Then $$ \varphi_{n}^2 + (-1)^n = \varphi_{n-1}\varphi_{n+1} = \varphi_{n-1}(\varphi_{n} + \varphi_{n-1}) = \varphi_{n}\varphi_{n-1} + \varphi_{n-1}^2,$$ $$4\varphi_{n}^2 + 4(-1)^n = 4\varphi_{n}\varphi_{n-1} + 4\varphi_{n-1}^2, $$ $$5\varphi_{n}^2 + 4(-1)^n = \varphi_{n}^2 + 4\varphi_{n}\varphi_{n-1} + 4\varphi_{n-1}^2 = (\varphi_{n} + 2\varphi_{n-1})^2, $$ which is a perfect square since $\psi_{n} = \varphi_{n} + 2\varphi_{n-1}$ is an integer.

(The numbers $\psi_n$ are the Lucas numbers.)[/sp]

Excellent solution! (Clapping) My own solution is much more mundane by comparison; I’ll wait and see if anyone else wants to try the problem before posting it.

 

[Olinguito]

Here’s my own solution to the challenge problem.

Spoiler

We shall prove by induction that the Fibonacci numbers satisfy the following equation:
$$\varphi_{n+1}^2-\varphi_n\varphi_{n+1}-\varphi_n^2-(-1)^n\ =\ 0.$$
It is easily checked that the equation is satisfied for $n=0$. Assume it is true for some integer $n\geqslant0$. Rewriting $\varphi_n=\varphi_{n+2}-\varphi_{n+1}$ gives
$$\varphi_{n+1}^2-(\varphi_{n+2}-\varphi_{n+1})\varphi_{n+1}-(\varphi_{n+2}-\varphi_{n+1})^2-(-1)^n\ =\ 0$$
which on simplifying becomes
$$-\varphi_{n+2}^2+\varphi_{n+1}\varphi_{n+2}+\varphi_{n+1}^2-(-1)^n\ =\ 0$$
– i.e.
$$\varphi_{n+2}^2-\varphi_{n+1}\varphi_{n+2}-\varphi_{n+1}^2-(-1)^{n+1}\ =\ 0.$$
QED. Hence: each Fibonacci number $\varphi_{n+1}$, an integer, is a root of the quadratic
$$x^2-\varphi_nx-\varphi_n^2-(-1)^n\ =\ 0$$
which has integer coefficients. Therefore its discriminant must be a perfect square. And the discriminant is
$$(-\varphi_n)^2-4\left[-\varphi_n^2-(-1)^n\right]$$
– that is to say:
$$5\varphi_n^2+4(-1)^n.$$