Maths Olympiad Prep

Library / /9 of 20

Algebra Difficulty 6.0 AIME, harder Prove it China

Given positive integers u,vu, v, the sequence {an}\{a_n\} is defined as: a1=u+va_1 = u + v, and for m1m \ge 1,
{a2m=am+u,a2m+1=am+v. \begin{cases} a_{2m} = a_m + u, \\ a_{2m+1} = a_m + v. \end{cases}

Denote Sm=a1+a2++amS_m = a_1 + a_2 + \dots + a_m (m=1,2,m = 1, 2, \dots). Prove that there are infinite terms in sequence {Sn}\{S_n\} that are square numbers.

Solution

For positive integer nn, we have
S2n+11=a1+(a2+a3)+(a4+a5)++(a2n+12+a2n+11)=u+v+(a1+u+a1+v)+(a2+u+a2+v)++(a2n1+u+a2n1+v)=2n(u+v)+2S2n1. \begin{align*} S_{2^{n+1}-1} &= a_1 + (a_2 + a_3) + (a_4 + a_5) + \dots + (a_{2^{n+1}-2} + a_{2^{n+1}-1}) \\ &= u + v + (a_1 + u + a_1 + v) + (a_2 + u + a_2 + v) + \dots + \\ & \qquad (a_{2^{n-1}} + u + a_{2^{n-1}} + v) \\ &= 2^n (u + v) + 2S_{2^{n-1}}. \end{align*}
Then
S2n1=2n1(u+v)+2S2n11=2n1(u+v)+2(2n2(u+v)+2S2n21)=22n1(u+v)+22S2n21==(n1)2n1(u+v)+2n1(u+v)=(u+v)n2n1. \begin{align*} S_{2^{n}-1} &= 2^{n-1}(u+v) + 2S_{2^{n-1}-1} \\ &= 2^{n-1}(u+v) + 2(2^{n-2}(u+v) + 2S_{2^{n-2}-1}) \\ &= 2 \cdot 2^{n-1}(u+v) + 2^2 S_{2^{n-2}-1} \\ &= \dots = (n-1) \cdot 2^{n-1}(u+v) + 2^{n-1}(u+v) \\ &= (u+v) \cdot n \cdot 2^{n-1}. \end{align*}
Suppose u+v=2kqu + v = 2^k \cdot q, where kk is a non-negative integer, and qq is an odd number. Take n=ql2n = q \cdot l^2, where ll is any positive integer satisfying lk1(mod2)l \equiv k - 1 \pmod 2. Then S2n1=q2l22k1+ql2S_{2^{n-1}} = q^2 l^2 \cdot 2^{k-1+q \cdot l^2}, and
k1+ql2k1+l2k1+(k1)2=k(k1)0(mod2). \begin{align*} k - 1 + q \cdot l^2 &\equiv k - 1 + l^2 \equiv k - 1 + (k - 1)^2 \\ &= k(k - 1) \equiv 0 \pmod 2. \end{align*}
Therefore, S2n1S_{2^{n-1}} is a square number. Since there are infinite ll's, there are infinite terms in {Sn}\{S_n\} that are square numbers. The proof is complete. \square

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.