Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

A B. 5109. feladat (2020. május)

B. 5109. Legyen

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

Van-e négyzetszám ebben a sorozatban?

Javasolta: George Stoica (Saint John, Canada)

(6 pont)

A beküldési határidő 2020. június 10-én LEJÁRT.


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.


Statisztika:

28 dolgozat érkezett.
6 pontot kapott:Baski Bence, Füredi Erik Benjámin, Lengyel Ádám, Lovas Márton, Seres-Szabó Márton, Tiderenczl Dániel.
4 pontot kapott:1 versenyző.
3 pontot kapott:3 versenyző.
2 pontot kapott:14 versenyző.
1 pontot kapott:3 versenyző.
0 pontot kapott:1 versenyző.

A KöMaL 2020. májusi matematika feladatai