Kezdőlap


Feladat:	2002. évi Kürschák matematikaverseny 2. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Egri Attila , Kocsis Albert Tihamér , Pallos Péter , Zsbán Ambrus
Füzet:	2003/február, 71 - 74. oldal		PDF \| MathML
Témakör(ök):	Fibonacci-sorozat, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):	Feladatok: 2003/február: 2002. évi Kürschák matematikaverseny 2. feladata

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

I. megoldás (Kocsis Albert Tihamér és Zsbán Ambrus megoldása alapján). Az állítást $n$ -re vonatkozó teljes indukcióval bizonyítjuk. Először is győződjünk meg arról, hogy az állítás $n = 2,3$ esetén igaz. Valóban, ha $n = 2$ , akkor feltételünk $1 < \frac{a}{b} < 2$ , ahonnan $b \geq 2 = f_{3}$ . Ha pedig $n = 3$ , akkor $\frac{3}{2} < \frac{a}{b} < 2$ miatt $b \geq 3 = f_{3}$ . A továbbiakban tegyük fel tehát, hogy $m \geq 3$ és az állítást $2 \leq n \leq m$ esetén már igazoltuk.
Legyen most $n = m + 1$ , és tegyük fel, hogy $\frac{f_{n}}{f_{n - 1}} < \frac{f_{n + 1}}{f_{n}}$ , továbbá az $a$ , $b$ pozitív egészekre $\frac{f_{m + 1}}{f_{m}} = \frac{f_{n}}{f_{n - 1}} < \frac{a}{b} < \frac{f_{n + 1}}{f_{n}} = \frac{f_{m + 2}}{f_{m + 1}}$ . Az egyenlőtlenségben szereplő számokat eggyel csökkentve kapjuk, hogy

\begin{matrix} \frac{f_{m - 1}}{f_{m}} = \frac{f_{m + 1} - f_{m}}{f_{m}} < \frac{a - b}{b} < \frac{f_{m + 2} - f_{m + 1}}{f_{m + 1}} = \frac{f_{m}}{f_{m + 1}} . \end{matrix}

Mivel az egyenlőtlenség mindkét szélén (és így középen is) pozitív számok állnak, a benne szereplő kifejezések reciprokát véve az egyenlőtlenség iránya megváltozik, és a következőt kapjuk:

\begin{matrix} \frac{f_{m}}{f_{m - 1}} > \frac{b}{a - b} > \frac{f_{m + 1}}{f_{m}} . \end{matrix}

Ezért az indukciós feltevésünk alapján

a - b \geq f_{m + 1}

. Az imént nyert egyenlőtlenségben szereplő számokat megint eggyel csökkentve, majd az így kapott számok reciprokát véve most az

\begin{matrix} \frac{f_{m - 1}}{f_{m - 2}} < \frac{a - b}{2 b - a} < \frac{f_{m}}{f_{m - 1}} \end{matrix}

egyenlőtlenségre jutunk, ahonnan ismét az indukciós feltételt alkalmazva megállapíthatjuk, hogy

2 b - a \geq f_{m}

.
Az így nyert két eredményt összegezve:

\begin{matrix} b = (2 b - a) + (a - b) \geq f_{m} + f_{m + 1} = f_{m + 2} = f_{n + 1} \end{matrix}

adódik, ami azt jelenti, hogy ebben az esetben az állítás

n = m + 1

esetén is igaz. Hogy az indukciós lépést teljessé tegyük, meg kell vizsgálnunk azt is, mi történik, ha

\frac{f_{m + 1}}{f_{m}} = \frac{f_{n}}{f_{n - 1}} > \frac{a}{b} > \frac{f_{n + 1}}{f_{n}} = \frac{f_{m + 2}}{f_{m + 1}}

. Ebben az esetben is szóról szóra elmondhatjuk az előző érvelést; az egyetlen különbség, hogy a felírt egyenlőtlenségekben mindenhol fel kell cserélnünk a ,,

<

'' és ,,

>

'' relációk szerepét.

II. megoldás (Egri Attila megoldása alapján). A megoldás során feltesszük, hogy

\frac{f_{n}}{f_{n - 1}} < \frac{a}{b} < \frac{f_{n + 1}}{f_{n}}

. Minden számot megszorozva a pozitív

b f_{n - 1} f_{n}

számmal a

\begin{matrix} b f_{n}^{2} < a f_{n - 1} f_{n} < b f_{n - 1} f_{n + 1} \end{matrix}

egyenlőtlenségre jutunk. Itt az első két szám különbsége,

f_{n} \cdot (a f_{n - 1} - b f_{n})

olyan pozitív egész szám, amely osztható

f_{n}

-nel, ezért nagysága legalább

f_{n}

. Hasonló okok miatt a második két szám különbsége,

f_{n - 1} \cdot (b f_{n + 1} - a f_{n})

legalább

f_{n - 1}

. Következésképpen a két szélső szám különbsége:

\begin{matrix} b (f_{n - 1} f_{n + 1} - f_{n}^{2}) \geq f_{n} + f_{n - 1} = f_{n + 1} . \end{matrix}

Elegendő tehát annyit megmutatni, hogy

k_{n} = f_{n - 1} f_{n + 1} - f_{n}^{2} = 1

.
Ha

n = 2

, akkor

k_{n} = 1

, ha pedig

n = 3

, akkor

k_{n} = - 1

. Még néhány értéket megvizsgálva azt tapasztaljuk, hogy

k_{n}

értéke felváltva 1 és

- 1

, vagyis

k_{n} = {(- 1)}^{n}

. Valóban,

n = 2

esetén ez így van, ha pedig valamely

n \geq 2

egész számra már beláttuk, akkor

\begin{matrix} \begin{matrix} k_{n + 1} & = f_{n} f_{n + 2} - f_{n + 1}^{2} = f_{n} (f_{n} + f_{n + 1}) - f_{n + 1}^{2} = \\ = f_{n}^{2} - f_{n + 1} (f_{n + 1} - f_{n}) = f_{n}^{2} - f_{n + 1} f_{n - 1} = - k_{n} = - {(- 1)}^{n} = {(- 1)}^{n + 1} . \end{matrix} \end{matrix}

Mivel esetünkben

b

és

f_{n + 1}

is pozitív, szükségképpen

k_{n}

is pozitív, vagyis értéke nem lehet más, mint 1, amint azt bizonyítani kívántuk. Teljesen hasonló módon járhatunk el akkor is, ha

\frac{f_{n}}{f_{n - 1}} > \frac{a}{b} > \frac{f_{n + 1}}{f_{n}}

Megjegyzés. Ebből a megoldásból leolvasható az az általánosabb eredmény is, mely szerint ha az

a

b

x

y

z

v

pozitív egészekre

y z - x v = 1

és

\frac{x}{y} < \frac{a}{b} < \frac{z}{v}

, akkor szükségképpen

b \geq y + v

III. megoldás. Tegyük fel az egyszerűség kedvéért, hogy

n

páros. Az előző megoldás során használt

f_{n - 1} f_{n + 1} - f_{n}^{2} = {(- 1)}^{n}

összefüggés alapján tehát a feltétel most

\frac{f_{n}}{f_{n - 1}} < \frac{a}{b} < \frac{f_{n + 1}}{f_{n}}

alakban teljesül. Az

\begin{matrix} \frac{a}{b} - \frac{f_{n}}{f_{n - 1}} = \frac{a f_{n - 1} - b f_{n}}{b f_{n - 1}} \end{matrix}

különbség pozitív, ezért itt az egész értékű számláló legalább 1. Következésképp

\begin{matrix} \frac{1}{b f_{n - 1}} \leq \frac{a}{b} - \frac{f_{n}}{f_{n - 1}} < \frac{f_{n + 1}}{f_{n}} - \frac{f_{n}}{f_{n - 1}} = \frac{1}{f_{n - 1} f_{n}}, \end{matrix}

ahonnan

b f_{n - 1} > f_{n - 1} f_{n}

, vagyis

b > f_{n}

.
Vizsgáljuk az

\frac{f_{n + 2}}{f_{n + 1}}

törtet, ez kisebb, mint

\frac{f_{n + 1}}{f_{n}}

. Ha

\begin{matrix} \frac{f_{n + 2}}{f_{n + 1}} < \frac{a}{b} < \frac{f_{n + 1}}{f_{n}} \end{matrix}

is teljesül, akkor az előző érveléshez hasonló módon kapjuk, hogy

\begin{matrix} \frac{1}{b f_{n}} \leq \frac{f_{n + 1}}{f_{n}} - \frac{a}{b} < \frac{f_{n + 1}}{f_{n}} - \frac{f_{n + 2}}{f_{n + 1}} = \frac{1}{f_{n + 1} f_{n}}, \end{matrix}

ahonnan

b > f_{n + 1}

.
Ha

\frac{a}{b} = \frac{f_{n + 2}}{f_{n + 1}}

, akkor

b \geq f_{n + 1}

, ugyanis

f_{n + 2}

és

f_{n + 1}

relatív prímek. Erről így győződhetünk meg: ha egy

d

pozitív egész szám osztója

f_{n + 2}

-nek és

f_{n + 1}

-nek is, akkor osztója az

f_{n} = f_{n + 2} - f_{n + 1}

különbségnek is. Ezt a gondolatmenetet tovább folytatva látható, hogy

d

osztója az

f_{n - 1}, f_{n - 2}, ..., f_{1}

számoknak is. Mivel

f_{1} = 1

d

nem lehet más, mint 1.
Már csak azt kell megvizsgálnunk, mi van akkor, ha

\frac{f_{n}}{f_{n - 1}} < \frac{a}{b} < \frac{f_{n + 2}}{f_{n + 1}}

. Ehhez az

ℓ_{n} = f_{n + 2} f_{n - 1} - f_{n} f_{n + 1}

különbséget tekintve, teljes indukcióval könnyen kapható, hogy

ℓ_{n} = {(- 1)}^{n}

, és ezért

\begin{matrix} \frac{1}{b f_{n - 1}} \leq \frac{a}{b} - \frac{f_{n}}{f_{n - 1}} < \frac{f_{n + 2}}{f_{n + 1}} - \frac{f_{n}}{f_{n - 1}} = \frac{1}{f_{n + 1} f_{n - 1}}, \end{matrix}

ahonnan ismét

b > f_{n + 1}

adódik.
Teljesen hasonló eljárással érhetünk célt akkor is, ha

n

páratlan szám.

Többen az úgynevezett Farey-sorozatok elméletét használták fel bizonyításuk során. Az alábbiakban erre mutatunk egy példát.

IV. megoldás (Pallos Péter megoldása alapján). Az

F_{1} = (\frac{0}{1}; \frac{1}{1})

sorozatból kiindulva rekurzív módon készítsük el a következő sorozatokat. Ha az

F_{n}

sorozatot már definiáltuk, akkor annak bármely két egymást követő

\frac{a}{b}

és

\frac{c}{d}

eleme közé illesszük be az

\frac{a + c}{b + d}

törtet. Könnyű ellenőrizni, hogy ha az

F_{n}

sorozat szigorúan növekedő volt, akkor ugyanez igaz az így kapott

F_{n + 1}

sorozatra is. Megoldásunk az alábbi két tételre támaszkodik: 1) az

F_{n}

sorozatban minden tört redukált alakban jelenik meg; 2) minden

0

és

1

közé eső racionális szám eleme valamelyik

F_{n}

sorozatnak.
Vegyük észre, hogy

\frac{f_{n - 1}}{f_{n}}

és

\frac{f_{n}}{f_{n + 1}}

szomszédos elemei az

F_{n}

sorozatnak. Valóban, ez

n = 2

esetén így van, ha pedig valamely

n \geq 2

egész számra

\frac{f_{n - 1}}{f_{n}}

és

\frac{f_{n}}{f_{n + 1}}

F_{n}

sorozat szomszédos elemei, akkor az

F_{n + 1}

sorozatban e két tört közé éppen az

\begin{matrix} \frac{f_{n - 1} + f_{n}}{f_{n} + f_{n + 1}} = \frac{f_{n + 1}}{f_{n + 2}} \end{matrix}

törtet illesztjük be, így az állítás

n + 1

-re is teljesülni fog.
Mivel az

f_{n}

sorozat szigorúan növekedő, a feladatban szereplő

\frac{a}{b}

tört 1-nél nagyobb. A fent említett tételek alapján a

\frac{b}{a}

tört tehát valamilyen redukált

\frac{b'}{a'}

alakban megjelenik valamely

F_{m}

sorozatban. Mivel

\frac{b'}{a'}

\frac{f_{n - 1}}{f_{n}}

és

\frac{f_{n}}{f_{n + 1}}

törtek egyikénél nagyobb, másikánál kisebb, nyilvánvaló, hogy

m > n

. Az

F_{m}

sorozatok konstrukciójából adódóan viszont látható, hogy minden, az

\frac{f_{n - 1}}{f_{n}}

és

\frac{f_{n}}{f_{n + 1}}

közé bekerülő tört számlálója legalább

f_{n - 1} + f_{n}

lesz, amiért is

\begin{matrix} b \geq b' \geq f_{n - 1} + f_{n} = f_{n + 1}, \end{matrix}

ahogyan azt bizonyítani akartuk.

Megjegyzés. Ebben a megoldásban tulajdonképpen ,,ágyúval lőttünk verébre'', tudniillik a Farey-sorozatokra vonatkozó tételek bizonyításához éppen azokra a gondolatokra van szükség, amelyeket az előző megoldások során használtunk.