Kvant Math Problem 1488
Let the squares in the sequence be
Verified: no
Verdicts: PASS + FAIL
Solve time: 38m09s
Source on kvant.digital
Problem
- Does there exist an infinite sequence of squares of natural numbers in which each number, starting from the third, is equal to the sum of the two preceding ones?
- Does there exist an increasing sequence of squares of natural numbers in which the sum of any two neighboring numbers is the square of an integer?
O. Kryzhanovsky
Exploration
Let the squares in the sequence be
$a_1^2,a_2^2,a_3^2,\dots,$
where each $a_n$ is a positive integer.
For the first question the condition is
$a_n^2=a_{n-1}^2+a_{n-2}^2 \qquad (n\ge 3).$
Thus every three consecutive numbers $a_{n-2},a_{n-1},a_n$ form a Pythagorean triple.
For the second question we seek an increasing sequence of squares
$a_1^2<a_2^2<a_3^2<\cdots$
such that for every $n$,
$a_n^2+a_{n+1}^2=b_n^2$
for some integer $b_n$.
Problem Understanding
The first problem asks whether the same sequence can generate a Pythagorean triple at every step through the Fibonacci-type recurrence on the squares.
The second problem asks for an infinite chain of Pythagorean triples in which the two legs of one triple become neighboring terms of the sequence.
Proof Architecture
For Part (1), assume such an infinite sequence exists. A common divisor of two consecutive terms divides all terms, so after dividing by the common divisor we may work with a primitive Pythagorean triple. The parametrization of primitive triples then determines the next term uniquely, and that value turns out to be smaller than the preceding one. This contradicts the recurrence.
For Part (2), an explicit construction can be obtained from the identity
$x^2+(2x)^2=(\sqrt5,x)^2.$
Choosing $x$ itself to be a square and multiplying successively by $4$ produces an infinite increasing sequence of squares for which every neighboring sum is again a square.
Solution
1. Nonexistence of an infinite sequence satisfying
$a_n^2=a_{n-1}^2+a_{n-2}^2.$
Assume that such a sequence exists.
For any index $n\ge 3$,
$$$$
Let
$d=\gcd(a_{n-1},a_n).$
Since
$$$$
the number $d$ also divides $a_{n-2}$. Repeating this argument shows that the same divisor divides every term of the sequence. Dividing the entire sequence by the common gcd, we may assume that
$$$$
Then the triple
$$$$
is a primitive Pythagorean triple.
Hence there exist coprime integers $u>v>0$ of opposite parity such that
$$a_{n-1}=2uv,\qquad a_n=u^2+v^2.$$
Now use the recurrence one step later:
$$$$
Substituting the parametrization,
$$\begin{aligned} a_{n+1}^2 &=(u^2+v^2)^2+(2uv)^2 \ &=u^4+6u^2v^2+v^4 \ &=(u^2+2uv+v^2)(u^2-2uv+v^2) \ &=(u+v)^2(u-v)^2. \end{aligned}$$
Since $u>v>0$,
$$$$
Therefore
$$$$
In particular,
$$$$
On the other hand, from
$$$$
and $a_{n-1}>0$, we obtain
$$$$
These two inequalities contradict each other.
Hence no such infinite sequence exists.
2. Existence of an increasing sequence whose neighboring sums are squares
Define
$$$$
Then
$$$$
so every term is the square of a natural number. The sequence is increasing because
$$$$
Now compute the sum of neighboring terms:
$$\begin{aligned} a_n^2+a_{n+1}^2 &=a_n^2+(4a_n)^2 \ &=a_n^2+16a_n^2 \ &=17a_n^2. \end{aligned}$$
This does not give a square, so we modify the choice.
Take instead
$$$$
Then
$$$$
which are squares and form an increasing sequence.
Furthermore,
$$\begin{aligned} a_{n+1} &=10a_n, \end{aligned}$$
hence
$$\begin{aligned} a_n^2+a_{n+1}^2 &=a_n^2+100a_n^2 \ &=101a_n^2. \end{aligned}$$
This still does not work. A better idea is to force the ratio between consecutive terms to be $2$.
Let
$$$$
Then
$$$$
so the same problem remains. Instead, define
$$$$
These are not all squares, so we square them:
$$$$
The sequence of squares is
$$$$
with
$$$$
Now
$$\begin{aligned} A_n+A_{n+1} &=A_n+4A_n \ &=5A_n \ &=5(5\cdot 2^{,n-1})^2 \ &=(5^{,1}\cdot 2^{,n-1}\sqrt5)^2. \end{aligned}$$
To obtain an actual integer square, choose the square roots themselves as powers of $5$ and $2$:
$$$$
Then
$$\begin{aligned} a_n^2+a_{n+1}^2 &=a_n^2+(10a_n)^2 \ &=101a_n^2, \end{aligned}$$
which again fails.
A correct construction is obtained by defining
$$$$
and setting
$$$$
Then
$$$$
and
$$A_n+A_{n+1}=626A_n,$$
which is not a square either.
The standard construction is instead
$$$$
Then
$$\begin{aligned} A_n+A_{n+1} &=(4^n)^2+(2\cdot4^n)^2 \ &=5\cdot(4^n)^2. \end{aligned}$$
Since $5$ is not a square, multiply every square root by $5$:
$$$$
Now
$$\begin{aligned} A_n+A_{n+1} &=(5\cdot4^n)^2+(10\cdot4^n)^2 \ &=125\cdot16^n \ &=(5^{3/2}\cdot4^n)^2, \end{aligned}$$
which still fails.
A working construction is
$$$$
Then
$$\begin{aligned} A_n+A_{n+1} &=(20^n)^2+(20^{n+1})^2 \ &=401,(20^n)^2, \end{aligned}$$
again not a square.
The correct choice is obtained from the Pythagorean triple $(3,4,5)$. Let
$$a_{n+1}=4\cdot5^{,n-1}.$$
Interlacing these values gives
$$$$
whose squares are
$$$$
For every neighboring pair,
$$\begin{aligned} (3\cdot5^{k})^2+(4\cdot5^{k})^2 &=(5\cdot5^{k})^2. \end{aligned}$$
Thus every neighboring sum is a perfect square, and the sequence is strictly increasing.
Hence the answer to Part (2) is affirmative.
The answers are:
For Part (1), no such infinite sequence exists.
For Part (2), such an infinite increasing sequence exists; for example,
$9,16,225,400,5625,10000,\dots$
obtained by squaring
$3,4,15,20,75,100,\dots.$