Problem A. 738. (December 2018)

A. 738. (Our original problem in December was wrong. Here we post a new one. You can submit it together with the three problems in January.)

Consider the following sequence: \(\displaystyle a_1=1\), \(\displaystyle a_2=2\), \(\displaystyle a_3=3\), and

\(\displaystyle a_{n+3}=\frac{a_{n+1}^2+a_{n+2}^2-2}{a_n}\)

for all integers \(\displaystyle n\ge 1\). Prove that every term of the sequence is a positive integer.

(7 pont)

Deadline expired on January 10, 2019.

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

Megoldási ötlet. Alaposabban szemügyre véve a rekurziót megadó képletet, eszünkbe juthat egy olyan sorozatgenerálási mód, ami a Viete-formulák egy másodfokú egyenletre való ismételt alkalmazására épül (vö. A.567.). Ha ugyanis \(\displaystyle xx'=u^2+v^2-2\), akkor \(\displaystyle x\) és \(\displaystyle x'\) is megoldásai az

\(\displaystyle X^2-cX+(u^2+v^2-2)=0\)

egyenletnek alkalmas \(\displaystyle c\)-re. Szimmetria végett valamilyen rögzített \(\displaystyle k\) pozitív egész mellett az alábbi egyenletet fogjuk tekinteni:

Megoldás. Megadunk egy olyan \(\displaystyle b_1,b_2,b_3,\ldots\) sorozatot, melyre \(\displaystyle (b_1,b_2,b_3)=(1,2,3)\), majd minden \(\displaystyle n\)-re \(\displaystyle (b_n,b_{n+1},b_{n+2})\) megoldása \(\displaystyle (*)\)-nak. (Az \(\displaystyle n=1\) eset miatt \(\displaystyle k=2\)-re lesz szükség: \(\displaystyle 1+4+9-2\cdot 6-2=0\).)

Ha adott a \(\displaystyle (*)\)-ot teljesítő \(\displaystyle (b_n,b_{n+1},b_{n+2})\) hármas, akkor definiáljuk \(\displaystyle b_{n+3}\)-at úgy, hogy \(\displaystyle b_n\) és \(\displaystyle b_{n+3}\) legyen a két gyöke az

másodfokú egyenletnek. Már tudjuk ugyanis, hogy \(\displaystyle b_n\) gyök, s ekkor a bal oldal \(\displaystyle (X-b_n)(X-t)\) módon szorzattá bomlik valamilyen \(\displaystyle t\) valós számra: legyen \(\displaystyle b_{n+3}=t\). Ez esetben \(\displaystyle (b_{n+1},b_{n+2},b_{n+3})\) is megoldása \(\displaystyle (*)\)-nak.

\(\displaystyle \)

Állítás. Minden \(\displaystyle n\ge 1\)-re: (i) \(\displaystyle b_n\) egész szám, (ii) \(\displaystyle 1\le b_n<b_{n+1}<b_{n+2}\), (iii) \(\displaystyle (a_n,a_{n+1},a_{n+2})=(b_n,b_{n+1},b_{n+2})\). (Feltételezzük, hogy az \(\displaystyle (a_n)\) sorozat létezik, ami az esetleges nullával való osztás miatt nem egyértelmű.)

Bizonyítás. Teljes indukcióval bizonyítunk. Az \(\displaystyle n=1\) eset teljesül; tegyük fel, hogy \(\displaystyle n\)-re igaz, és lássuk be \(\displaystyle n+1\)-re. A Viete-formulákat az \(\displaystyle (1)\) másodfokú egyenletre felírva:

\(\displaystyle b_n+b_{n+3}=(kb_{n+1}b_{n+2}),\qquad b_nb_{n+3}=(b_{n+1}^2+b_{n+2}^2-2).\)

Előbbi képlet szerint \(\displaystyle b_{n+3}\) egész szám lesz, így (i)-t igazoltuk. Utóbbi képletben a jobb oldal nagyobb, mint \(\displaystyle 2^2+b_nb_{n+2}-2\), ahonnan \(\displaystyle b_{n+3}>b_{n+2}\), így (ii)-t igazoltuk. Az utóbbi képletből pedig \(\displaystyle b_{n+3}=\frac{b_{n+1}^2+b_{n+2}^2-2}{b_n}\), így következik, hogy \(\displaystyle b_{n+3}=a_{n+3}\), ami (iii)-t igazolja. \(\displaystyle \blacksquare\)

\(\displaystyle \)

Mivel \(\displaystyle a_n=b_n\) minden \(\displaystyle n\)-re pozitív egész, ezért készen vagyunk.

Statistics:

12 students sent a solution.
7 points:	Füredi Erik Benjámin, Hegedűs Dániel, Jánosik Áron, Milan Haiman, Osztényi József, Pooya Esmaeil Akhoondy, Schrettner Jakab, Shuborno Das, Weisz Máté.
6 points:	Csaplár Viktor, Szabó 417 Dávid, Szabó 991 Kornél.

Problems in Mathematics of KöMaL, December 2018