 |
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