A B. 4950. feladat (2018. április)

B. 4950. Jelöljük \(\displaystyle F_n\)-nel az \(\displaystyle n\)-edik Fibonacci-számot (\(\displaystyle F_1=F_2=1\), \(\displaystyle F_{n+2}= F_{n+1}+F_n\)), és definiáljuk az \(\displaystyle a_0,a_1,a_2,\dots\) sorozatot a következő rekurzióval: legyen \(\displaystyle a_0=2018\), és minden \(\displaystyle k\ge 0\)-ra legyen \(\displaystyle a_{k+1}=a_k+F_n\), ahol \(\displaystyle F_n\) a legnagyobb \(\displaystyle a_k\)-nál kisebb Fibonacci-szám. Előfordul-e az \(\displaystyle (a_k)\) sorozatban Fibonacci-szám?

(4 pont)

A beküldési határidő 2018. május 10-én LEJÁRT.

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.

Statisztika:

91 dolgozat érkezett.
4 pontot kapott:	51 versenyző.
3 pontot kapott:	21 versenyző.
2 pontot kapott:	10 versenyző.
1 pontot kapott:	8 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2018. áprilisi matematika feladatai