Problem B. 5059. (November 2019)

B. 5059. For a positive integer \(\displaystyle c\), define the sequence \(\displaystyle \{ a_n\}\) by the following recurrence relation: \(\displaystyle a_0=c\) and \(\displaystyle a_{n+1} = \big[ a_{n} + \sqrt{a_{n}}\,\big]\) for \(\displaystyle n \ge 0\). Prove that if \(\displaystyle 2019\) occurs as a term of the sequence, then no preceding term is a perfect square, but there are infinitely many perfect squares among the following terms.

(5 pont)

Deadline expired on December 10, 2019.

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

Megoldás. Legyen \(\displaystyle b_n=\big[\sqrt{a_n}\big]\), ekkor tehát \(\displaystyle b_n^2\le a_n\le b_n^2+2b_n\), és a rekurziót az \(\displaystyle a_{n+1}=a_n+b_n\) alakba is írhatjuk. Legyen továbbá \(\displaystyle r_n\) a legkisebb pozitív egész, amelyre \(\displaystyle a_n\equiv r_n\pmod{b_n}\), végül legyen \(\displaystyle s_n=b_n+r_n\). Ennek a négy sorozatnak a viselkedését fogjuk egyszerre vizsgálni.

1. eset: \(\displaystyle a_{n+1}=(b_n+1)^2\), vagyis \(\displaystyle a_n=b_n^2+b_n+1\). Ebben az esetben \(\displaystyle r_n=1\), emiatt \(\displaystyle a_{n+1}=s_n^2\), \(\displaystyle b_{n+1}=r_{n+1}=b_n+1\) és \(\displaystyle s_{n+1}=2b_n+2=2s_n\).

2. eset: \(\displaystyle a_{n+1}<(b_n+1)^2\), vagyis \(\displaystyle a_n\le b_n^2+b_n\). Ilyenkor \(\displaystyle b_n^2\le a_n<a_{n+1}<(b_n+1)^2\), tehát az \(\displaystyle a_{n+1}\) nem négyzetszám, \(\displaystyle b_{n+1}=b_n\), \(\displaystyle r_{n+1}=r_n\) és \(\displaystyle s_{n+1}=s_n\).

3. eset: \(\displaystyle a_{n+1}>(b_n+1)^2\), vagyis \(\displaystyle b_n^2+b_n+1> a_n\le b_n^2+2b_n\). Ebben az esetben \(\displaystyle r_n>1\), \(\displaystyle a_n=b_n^2+b_n+r_n\), \(\displaystyle (b_n+1)^2<a_{n+1}=(b_n+1)^2+r_n-1<(b_n+2)^2\), tehát \(\displaystyle a_{n+1}\) nem négyzetszám, \(\displaystyle b_{n+1}=b_n+1\), \(\displaystyle r_{n+1}=r_n-1\) és \(\displaystyle s_{n+1}=s_n\).

A három esetet összefoglalva,

Az világos, hogy az \(\displaystyle a_n\) sorozat mindig egy pozitív egésszel nő, emiatt nem lehet korlátos, és így a \(\displaystyle b_n\) és \(\displaystyle s_n\) sorozat sem lehet korlátos. Az \(\displaystyle s_n\) sorozat végtelen sokszor duplázódik; mindig akkor, amikor \(\displaystyle a_{n+1}\) négyzetszám, és éppen \(\displaystyle a_{n+1}=s_n^2\). Ez igazolja, hogy az \(\displaystyle a_n\) sorozatban végtelen sok négyzetszám van. Sőt, azt is látjuk, hogy bármely \(\displaystyle a_n\) elem után a következő négyzetszám az \(\displaystyle s_n^2\).

Amikor \(\displaystyle a_n=2019\), akkor \(\displaystyle b_n=44\), \(\displaystyle r_n=39\) és \(\displaystyle s_n=83\) páratlan szám; ez korábban nem duplázódhatott, tehát a \(\displaystyle 2019\) előtt biztosan nem lehet négyzetszám a sorozatban. Az az \(\displaystyle a_n\) sorozatban szereplő négyzetszámok a \(\displaystyle (2^k\cdot83)^2\) alakú számok, \(\displaystyle k=0,1,2,\ldots\)

Statistics:

57 students sent a solution.
5 points:	Andó Viola, Argay Zsolt, Asztalos Ádám, Bán-Szabó Áron, Baski Bence, Beinschroth Ninett, Beke Csongor, Bencsik Ádám, Bognár 171 András Károly, Csonka Illés, Feczkó Nóra, Fekete Richárd, Fleiner Zsigmond, Geretovszky Anna, Gyetvai Miklós, Győrffi Ádám György, Hegedűs Dániel, Hervay Bence, Jánosik Áron, Jánosik Máté, Kercsó-Molnár Anita, Kerekes Boldizsár, Kocsis Anett, Kovács 129 Tamás, Mácsai Dániel, Metzger Ábris András, Móra Márton Barnabás, Nádor Benedek, Nagy 551 Levente, Németh Márton, Nguyen Bich Diep, Nyárfádi Patrik, Seres-Szabó Márton, Szabó 991 Kornél, Szakács Ábel, Szűcs 064 Tamás, Terjék András József, Tiderenczl Dániel, Török Mátyás, Velich Nóra, Wiener Anna.
4 points:	Füredi Erik Benjámin, Gábriel Tamás, Hámori Janka, Király Csaba Regő, Lovas Márton, Molnár Lehel, Osztényi József, Szanyi Attila, Sztranyák Gabriella.
3 points:	2 students.
2 points:	2 students.
1 point:	3 students.

Problems in Mathematics of KöMaL, November 2019