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