Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem B. 5109. (May 2020)

B. 5109. Let

\(\displaystyle x_1 = 2, \quad x_2 = 7, \quad x_{n+1} = 4 x_n - x_{n-1} \quad (n=2,3,\ldots). \)

Is there a perfect square in this sequence?

Proposed by G. Stoica, Saint John, Canada

(6 pont)

Deadline expired on June 10, 2020.


Sorry, the solution is available only in Hungarian. Google translation

Megoldás (vázlat). Megmutatjuk, hogy a sorozatban nincs négyzetszám.

A sorozat első néhány eleme:

\(\displaystyle x_1=2, \quad x_2=7, \quad x_3=26, \quad x_4=97, \quad x_52=362, \quad x_6=1351. \)

A modulo \(\displaystyle 5\) és modulo \(\displaystyle 3\) maradékaik

\(\displaystyle (x_1,x_2,x_3,x_4,x_5,x_6,\ldots) \equiv (2,2,1,2,2,1,\ldots) \pmod5, \)

illetve

\(\displaystyle (x_1,x_2,x_3,x_4,x_5,x_6,\ldots) \equiv (2,1,2,1,2,1,\ldots) \pmod3. \)

A rekurzióból triviális indukcióval igazolhatjuk, hogy a maradékok \(\displaystyle 3\), illetve \(\displaystyle 2\) szerint periodikusak, és az \(\displaystyle (x_n)\) sorozat szigorúan monoton növekvő.

Az \(\displaystyle (x_n)\) sorozat egy úgynevezett homogén lineáris rekurzív sorozat. A rekurzió karakterisztikus polinomja \(\displaystyle t^2-4t+1\), ennek gyökei \(\displaystyle u=2+\sqrt3\) és \(\displaystyle v=2-\sqrt3\). A rekurziót (eltekintve a kezdőértékektől) kielégíti az \(\displaystyle u^n=\big(2+\sqrt3\big)^n\) és a \(\displaystyle v^n=\big(2-\sqrt3\big)^n\) sorozat is, valamint ezek minden lineáris kombinációja. Akár egyenletrendszer megoldásával, akár próbálgatással megkaphatjuk, hogy \(\displaystyle \big(2+\sqrt3\big)+\big(2-\sqrt3\big)=4=2x_1\) és \(\displaystyle \big(2+\sqrt3\big)^2+\big(2-\sqrt3\big)^2=14=2x_2\), tehát az \(\displaystyle (x_n)\) sorozat explicit alakja:

\(\displaystyle x_n = \dfrac{u^n+v^n}{2} = \dfrac{\big(2+\sqrt3\big)^n+\big(2-\sqrt3\big)^n}{2}. \)\(\displaystyle (1) \)

Az (1) azonosság következménye, hogy

\(\displaystyle x_{3k} = \dfrac{u^{3k}+v^{3k}}{2} = \dfrac{(u^k+v^k)^3-3(uv)^k(u^{k}+v^{k})}{2} = 4x_k^3-3x_k = x_k\cdot(4x_k^2-3). \)\(\displaystyle (2) \)

Most tegyük fel indirekten, hogy a sorozatban mégis van négyzetszám, \(\displaystyle x_n=a^2\).

Ha \(\displaystyle n\) nem osztható \(\displaystyle 3\)-nal, akkor \(\displaystyle x_n\equiv2\pmod5\), márpedig egy négyzetszám nem adhat \(\displaystyle 2\) maradékot \(\displaystyle 5\)-tel osztva. Tehát \(\displaystyle n\) biztosan osztható \(\displaystyle 3\)-mal, \(\displaystyle n=3k\). A (2) szerint

\(\displaystyle x_n = x_k\cdot(4x_k^2-3). \)

Legyen a jobb oldalon a két tényező legnagyobb közös osztója \(\displaystyle d\); ekkor \(\displaystyle d|x_k\) és \(\displaystyle d|4x_k^2-3\); de akkor \(\displaystyle d|3\). A sorozatban nincsenek \(\displaystyle 3\)-mal osztható elemek, ezért \(\displaystyle d=3\) nem lehetséges. Az az egy lehetőség maradt, ha \(\displaystyle d=1\), vagyis a két, pozitív egész tényező relatív prím egymáshoz; akkor viszont a szorzatuk csak úgy lehet négyzetszám, ha külön-külön is négyzetszámok: \(\displaystyle x_k=b^2\) és \(\displaystyle 4x_k^2-3=c^2\).

A \(\displaystyle 4x_k^2-3=c^2\) egyenletet rendezzük át és alakítsuk szorzattá:

\(\displaystyle 3 = 4x_k^2-c^2 = (2x_k+c)(2x_k-c). \)

Mivel \(\displaystyle x_k\ge2\), a \(\displaystyle 2x_k+c\) tényező biztosan nagyobb, mint \(\displaystyle 3\), ellentmondásra jutottunk.

Megjegyzés. Az utolsó lépés helyett a megoldást végtelen leszállással is be lehetne fejezni: mivel \(\displaystyle x_k=b^2\) is négyzetszám, a sorozat minden \(\displaystyle x_n\) négyzetszám eleméhez találtunk egy korábbi \(\displaystyle x_k\) négyzetszámot.


Statistics:

28 students sent a solution.
6 points:Baski Bence, Füredi Erik Benjámin, Lengyel Ádám, Lovas Márton, Seres-Szabó Márton, Tiderenczl Dániel.
4 points:1 student.
3 points:3 students.
2 points:14 students.
1 point:3 students.
0 point:1 student.

Problems in Mathematics of KöMaL, May 2020