Track / Stage 6 / 139 of 400 #1139 of 2000

Problem 1139

National olympiad, first round

Number theory Difficulty 6.2 Prove it

II. (This question is worth 40 points) Given positive integers $u, v$ . The sequence $\left\{a_{n}\right\}$ is defined as follows: $a_{1}=u+v$ , for integers $m \geq 1$ .
$\left\{\begin{array}{l} a_{2 m}=a_{m}+u, \\ a_{2 m+1}=a_{m}+v . \end{array}\right.$

Let $S_{m}=a_{1}+a_{2}+\cdots+a_{m}(m=1,2, \cdots)$ . Prove: The sequence $\left\{S_{n}\right\}$ contains infinitely many perfect squares.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

Prove that for positive integers $n$ , we have
$\begin{array}{l} S_{2 m-1}=a_{1}+\left(a_{2}+a_{3}\right)+\left(a_{4}+a_{5}\right)+\cdots+\left(a_{2 m-2}+a_{2 m-1}\right) \\ =u+v+\left(a_{1}+u+a_{1}+v\right)+\left(a_{2}+u+a_{2}+v\right)+\cdots+\left(a_{r-1}+u+a_{r-1}+v\right) \\ =2^{n}(u+v)+2 S_{r-1} \text {, } \\ \end{array}$

Therefore,
$\begin{aligned} S_{2^{n-1}} & =2^{n-1}(u+v)+2 S_{2^{n-1}-1}=2^{n-1}(u+v)+2\left(2^{n-2}(u+v)+2 S_{2^{n-2}-1}\right) \\ & =2 \cdot 2^{n-1}(u+v)+2^{2} S_{2^{n-2}-1} \\ & =\cdots=(n-1) \cdot 2^{n-1}(u+v)+2^{n-1}(u+v) \\ & =(u+v) n \cdot 2^{n-1} . \end{aligned}$

Let $u+v=2^{k} \cdot q$ , where $k$ is a non-negative integer and $q$ is an odd number. Choose $n=q \cdot l^{2}$ , where $l$ is any positive integer satisfying $l=k-1(\bmod 2)$ . At this point, $S_{2^{n-1}}=q^{2} l^{2} \cdot 2^{k-1-\alpha q^{2}}$ . Noting that $q$ is odd, we have
$k-1+q \cdot l^{2}=k-1+l^{2}=k-1+(k-1)^{2}=k(k-1)=0(\bmod 2) .$

Thus, $S_{2^{n-1}}$ is a perfect square. Since there are infinitely many $l$ , the sequence $\left\{S_{n}\right\}$ contains infinitely many perfect squares.
40 points

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.