Problem B. 4950. (April 2018)

B. 4950. Let \(\displaystyle F_n\) denote the \(\displaystyle n\)th Fibonacci number (\(\displaystyle F_1=F_2=1\), \(\displaystyle F_{n+2}= F_{n+1}+F_n\)), and define the sequence \(\displaystyle a_0,a_1,a_2,\dots\) with the following recurrence relation: let \(\displaystyle a_0=2018\), and for all \(\displaystyle k\ge 0\) let \(\displaystyle a_{k+1}=a_k+F_n\), where \(\displaystyle F_n\) is the largest Fibonacci number less than \(\displaystyle a_k\). Will there be any Fibonacci number in the sequence \(\displaystyle (a_k)\)?

(4 pont)

Deadline expired on May 10, 2018.

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

Megoldás. Először is megjegyezzük, hogy a Fibonacci-számok egy monoton növekedő (\(\displaystyle F_2\)-től kezdve szigorúan monoton növekedő) sorozatot alkotnak. Annak ellenőrzéséhez, hogy \(\displaystyle a_0=2018\) Fibonacci-szám-e, meghatározzuk a sorozat tagjait egészen addig, amíg át nem lépjük 2018-at:

\(\displaystyle 1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,\dots\)

Tehát a 2018 nem Fibonacci-szám. Megmutatjuk \(\displaystyle k\geq -1\)-re vonatkozó teljes indukcióval, hogy \(\displaystyle a_{k+1}\) nem Fibonacci-szám. Ha \(\displaystyle k=-1\), akkor \(\displaystyle a_{k+1}=a_0=2018\), amiről ellenőriztük, hogy nem Fibonacci-szám. Ha \(\displaystyle k>-1\), akkor annak igazolásához, hogy \(\displaystyle a_{k+1}\) nem Fibonacci-szám már felhasználhatjuk, hogy \(\displaystyle a_k\) sem az (az indukciós feltevés szerint). Mivel a \(\displaystyle 2018\leq a_k\) szám nem Fibonacci-szám, ezért két szomszédos Fibonacci-szám közé esik: \(\displaystyle F_n<a_k<F_{n+1}\). Az \(\displaystyle (a_k)\) sorozat rekurziója szerint ekkor \(\displaystyle a_{k+1}=a_k+F_n\). Mivel \(\displaystyle F_n<a_k<F_{n+1}\), ezért

\(\displaystyle F_{n+1}=F_{n-1}+F_n<F_n+F_n<a_k+F_n<F_{n+1}+F_n=F_{n+2}, \)

tehát \(\displaystyle a_{k+1}\) is két szomszédos Fibonacci-szám közé esik, és így nem lehet Fibonacci-szám, amivel az indukciós lépést igazoltuk.

Tehát az \(\displaystyle (a_k)\) sorozatban nem fordul elő Fibonacci-szám.

Statistics:

91 students sent a solution.
4 points:	51 students.
3 points:	21 students.
2 points:	10 students.
1 point:	8 students.
0 point:	1 student.

Problems in Mathematics of KöMaL, April 2018