Kezdőlap


Cím:	Néhány érdekesség a Fibonacci- és a Fibonacci-típusú sorozatokról II. rész
Szerző(k):	Énekes Béla , Kós Géza
Füzet:	2001/január, 3 - 9. oldal	PDF \| MathML
Témakör(ök):	Szakmai cikkek

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.

Előző számunkban a ,,Fibonacci-típusú'' sorozatoknak, illetve magának a Fibonacci sorozatnak több érdekes tulajdonságát bebizonyítottuk. Most ezek felhasználásával különböző megoldásokat adunk az A. 244. feladatra. A definíciók, tételek és lemmák számozását nem kezdjük újra, mivel többször hivatkozni fogunk a cikk első részében leírtakra.

A. 244. Egy számsorozatot nevezzünk Fibonacci-típusúnak, ha a harmadiktól kezdve mindegyik eleme az előző kettő összege. Bizonyítsuk be, hogy a pozitív egész számok halmaza felbontható olyan Fibonacci-típusú végtelen sorozatok uniójára, amelyek közül semelyik kettőnek nincs közös eleme.

I. megoldás az A. 244. feladatra

Elsőként a feladatnak egy olyan megoldását vizsgáljuk meg, amely két, önmagában is érdekes segédsorozat felhasználásával konstruálja meg a kívánt felbontást.

2. definíció. Definiáljuk az

A = (a_{0}, a_{1}, ...)

és a

B = (b_{0}, b_{1}, ...)

sorozatokat a következőképpen:

*	(1) Legyen $a_{0} = b_{0} = 1$ ;

*	(2) ha $a_{0}$ , $...$ , $a_{n - 1}$ -et és $b_{0}$ , $...$ , $b_{n - 1}$ -et már definiáltuk, akkor legyen $a_{n}$ az a legkisebb pozitív egész, amelyik nem szerepel az $a_{0}$ , $a_{1}$ , $...$ , $a_{n - 1}$ , $b_{0}$ , $b_{1}$ , $...$ , $b_{n - 1}$ értékek között;

*	(3) legyen $b_{n} = a_{n} + n$ .

A következő táblázat tartalmazza az

A

és

B

első néhány elemét:

\begin{matrix} \begin{matrix} \begin{matrix} n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ a_{n} & 1 & 2 & 4 & 5 & 7 & 9 & 10 & 12 & 13 & 15 & 17 \\ b_{n} & 1 & 3 & 6 & 8 & 11 & 14 & 16 & 19 & 21 & 24 & 27 \end{matrix} \\ \begin{matrix} n & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 \\ a_{n} & 18 & 20 & 22 & 23 & 25 & 26 & 28 & 30 & 31 & 33 & 34 \\ b_{n} & 29 & 32 & 35 & 37 & 40 & 42 & 45 & 48 & 50 & 53 & 55 \end{matrix} \end{matrix} \end{matrix}

A megoldás kulcsa a következő lemma.

5. lemma. Tetszőleges

n

nemnegatív egészre

\begin{matrix} a_{b_{n}} = a_{n} + b_{n} . \end{matrix}

A lemma bizonyításához további lemmákra lesz szükségünk.

6. lemma. Az

A

és a

B

sorozat is szigorúan monoton nő,

a_{0} = b_{0} = 1

-től eltekintve nincs közös elemük, továbbá minden egyes pozitív egészt tartalmazza valamelyik sorozat.

7. lemma. Az

A

és a

B

elemeire teljesülnek a következő egyenlőtlenségek:

\begin{matrix} \begin{matrix} a_{n} + 1 & \leq a_{n + 1} \leq a_{n} + 2; & (9 a) \\ b_{n} + 2 & \leq b_{n + 1} \leq b_{n} + 3; & (9 b) \\ a_{n} + 3 & \leq a_{n + 2} \leq a_{n} + 4; & (9 c) \\ b_{n} + 5 & \leq b_{n + 2} \leq b_{n} + 6. & (9 d) \end{matrix} \end{matrix}

7. feladat. Igazoljuk a

6

. és a

7

. lemmát.

8. lemma. Tetszőleges

n

nemnegatív egészre

\begin{matrix} a_{a_{n}} = b_{n} + 1. \end{matrix}

(11)

Bizonyítás. Teljes indukcióval bizonyítunk. Az

n = 0

esetben

b_{0} + 1 = 1 + 1 = 2 = a + 1 = a_{a_{0}}

.
Tegyük fel, hogy az állítás teljesül

n = m

-re, azaz

a_{a_{m}} = b_{m} + 1

; ebből bebizonyítjuk az

n = m + 1

esetre is. A

b_{m + 1} + 1

szám a (9b) alapján nem szerepelhet a

B

sorozatban, tehát az

A

sorozatban szerepel:

b_{m + 1} + 1 = a_{k}

valamilyen

k

-ra. Azt kell igazolnunk, hogy

k = a_{m + 1}

.
A (9a) egyenlőtlenség szerint

a_{m} + 1 \leq a_{m + 1} \leq a_{m} + 2

. Ha

a_{m + 1} = a_{m} + 1

, akkor

b_{m + 1} = b_{m} + 2

, és

a_{k} = b_{m + 1} + 1 = (b_{m} + 1) + 2 = a_{a_{m}} + 2

. (Az utolsó lépésben az indukciós feltevést alkalmaztuk.) A (9a) és (9c) egyenlőtlenségek szerint ez csak úgy lehetséges, ha

k = a_{m} + 1 = a_{m + 1}

.
Ha

a_{m + 1} = a_{m} + 2

, akkor

b_{m + 1} = b_{m} + 3

, és

a_{k} = b_{m + 1} + 1 = (b_{m} + 1) + 3 = a_{a_{m}} + 3

. (Az utolsó lépésben ismét az indukciós feltevést alkalmaztuk.) A (9a) és (9c) egyenlőtlenségek szerint ez csak úgy lehetséges, ha

k = a_{m} + 2 = a_{m + 1}

. Ezzel a lemmát igazoltuk.

9. lemma. Tetszőleges

n

pozitív egészre

\begin{matrix} \begin{matrix} a_{b_{n} - 2} & = a_{b_{n}} - 3; & (12 a) \\ a_{b_{n} - 1} & = a_{b_{n}} - 1; & (12 b) \\ a_{b_{n} + 1} & = a_{b_{n}} + 2. & (12 c) \end{matrix} \end{matrix}

Bizonyítás. Először a (12b) egyenlőséget igazoljuk. Tegyük fel, hogy az állítás hamis; ekkor

a_{b_{n}} = a_{b_{n} - 1} + 2

, és az

a_{b_{n} - 1} + 1 = a_{b_{n}} - 1

szám a

B

sorozatban van:

a_{b_{n}} - 1 = b_{k}

valamilyen

k

-ra. A 8. lemma szerint

b_{k} + 1 = a_{a_{k}}

, tehát

a_{b_{n}} = b_{k} + 1 = a_{a_{k}}

. Az

A

sorozat monotonitása miatt ebből következik, hogy

a_{k} = b_{n}

, ami ellentmond annak, hogy az

A

és a

B

sorozatnak az

a_{0} = b_{0} = 1

-en kívül nincs közös eleme. A (12b) tehát teljesül.
A (9a) és (9c) egyenlőtlenségek alapján

a_{b_{n} - 2} \leq a_{b_{n}} - 3

és

a_{b_{n} - 2} \geq a_{b_{n} - 1} - 2 = a_{b_{n}} - 3

; ezekből (12a) következik.
Szintén a (9a) és (9c) egyenlőtlenségek alapján

a_{b_{n} + 1} \leq a_{b_{n}} + 2

és

a_{b_{n} + 1} \geq a_{b_{n} - 1} + 3 = a_{b_{n}} + 2

; tehát (12c) is igaz.
Most már rátérhetünk az 5. lemma bizonyítására.

Az 5. lemma bizonyítása. A bizonyításhoz ismét a teljes indukciót használjuk. Az állítás igaz

n = 0

-ra:

a_{b_{0}} = a_{1} = 2 = 1 + 1 = a_{0} + b_{0}

.
Tegyük fel, hogy az állítás igaz

n \leq m

esetén, ebből bebizonyítjuk

n = (m + 1)

-re is. Ismét két esetet vizsgálunk aszerint, hogy

a_{m + 1} = a_{m} + 1

vagy

a_{m + 1} = a_{m} + 2

.
Ha

a_{m + 1} = a_{m} + 1

, akkor

b_{m + 1} = b_{m} + 2

és

a_{m + 1} + b_{m + 1} = a_{m} + b_{m} + 3 = a_{b_{n}} + 3

. Másrészt a 8. lemma alapján

\begin{matrix} a_{b_{m + 1}} = a_{b_{m + 1} - 1} + 1 = a_{b_{m} + 1} + 1 = (a_{b_{m}} + 2) + 1 = a_{b_{m}} + 3. \end{matrix}

Ebben az esetben tehát

a_{m + 1} + b_{m + 1} = a_{b_{m + 1}}

.
Ha

a_{m + 1} = a_{m} + 2

, akkor

b_{m + 1} = b_{m} + 3

és

a_{m + 1} + b_{m + 1} = a_{m} + b_{m} + 3 = a_{b_{n}} + 5

. A 8. lemma alapján

\begin{matrix} a_{b_{m + 1}} = a_{b_{m + 1} - 2} + 3 = a_{b_{m} + 1} + 3 = (a_{b_{m}} + 2) + 3 = a_{b_{m}} + 5. \end{matrix}

Az állítás ebben az esetben is teljesül. A lemmát ezzel bebizonyítottuk.
Az 5. lemma segítségével könnyen megkonstruálható az A. 244. feladatban kívánt felbontás, erről szól a következő tétel.

6. tétel. Tekintsük az összes olyan

(a_{m}, b_{m})

paraméterű Fibonacci-típusú sorozatot, amelyre az

m

nemnegatív egész szám nem szerepel a

B

sorozatban. Az összes pozitív egész szám pontosan egy ilyen sorozatban szerepel.

Bizonyítás. Ha valamely

m

-re

a_{m}

és

b_{m}

egy Fibonacci-típusú sorozat két egymás utáni eleme, akkor az 5. lemma és a

B

sorozat definíciója alapján a következő két elem

a_{m} + b_{m} = a_{b_{m}}

, illetve

a_{b_{m}} + b_{m} = b_{b_{m}}

. Ezt a gondolatmenetet megismételve láthatjuk, hogy az

(a_{m}, b_{m})

paraméterű sorozat elemei

\begin{matrix} a_{m_{1}}, b_{m_{1}}, a_{m_{2}}, b_{m_{2}}, a_{m_{3}}, b_{m_{3}}, ... \end{matrix}

alakban írhatók, ahol

m_{1} = m

és

m_{i + 1} = b_{m_{i}}

.
Tetszőleges

(a_{m}, b_{m})

számpárhoz egyértelműen meghatározható, hogy melyik számpár áll előtte a megfelelő sorozatban. Ha

m

B

sorozatban szerepel, azaz

m = b_{k}

valamely

k

-ra, akkor ez az

(a_{k}, b_{k})

számpár. Ha

m

nem szerepel a

B

sorozatban, akkor az

(a_{m}, b_{m})

számpár a megfelelő paraméterű sorozat első két eleme. Ezen a módon visszafelé lépkedve, mindegyik pozitív egész számról egyértelműen eldönthető, hogy melyik sorozatban szerepel. Ezzel a tételt bebizonyítottuk.
A következő táblázatban felsoroltuk az első néhány sorozatot.

\begin{matrix} \begin{matrix} m & a_{m_{1}} & b_{m_{1}} & a_{m_{2}} & b_{m_{2}} & a_{m_{3}} & b_{m_{3}} & a_{m_{4}} & b_{m_{4}} \\ 0 & 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & ... \\ 2 & 4 & 6 & 10 & 16 & 26 & 42 & 68 & 110 & ... \\ 4 & 7 & 11 & 18 & 29 & 47 & 76 & 123 & 199 & ... \\ 5 & 9 & 14 & 23 & 37 & 60 & 97 & 157 & 254 & ... \\ 7 & 12 & 19 & 31 & 50 & 81 & 131 & 212 & 343 & ... \\ 9 & 15 & 24 & 39 & 63 & 102 & 165 & 267 & 432 & ... \end{matrix} \end{matrix}

II. megoldás az A. 244. feladatra

Másodszor egy olyan megoldást mutatunk, amely egy többé-kevésbé természetes konstrukciót ad a keresett felbontásra.
Képzeljük el, hogy a pozitív egész számok halmazát már felbontottuk páronként diszjunkt Fibonacci-típusú sorozatok uniójára. Legyen

f

az a függvény, ami minden egyes pozitív egészhez hozzárendeli az őt tartalmazó egyetlen sorozat következő elemét. Tehát tetszőleges

n

pozitív egészre az

n

-et tartalmazó sorozatban az

n

után az

f (n)

, azután pedig az

f (f (n))

következik. Mivel a sorozat Fibonacci-típusú, szükséges, hogy

f (f (n)) = f (n) + n

teljesüljön. Az

f

függvény tehát pozitív egész számokhoz pozitív egész számokat rendel, és teljesül rá az

f (f (n)) = f (n) + n

függvényegyenlet.
Megoldásunk az iménti gondolatmenet megfordításával működik. Először megadunk egy

f

függvényt, amire teljesül a talált függvényegyenlet. Ezután definiáljuk a megfelelő Fibonacci-típusú sorozatokat.

3. definíció. Definiáljuk az

f

függvényt a következőképpen:

1.

Legyen

f (1) = 2

;

2.

f (1)

...

f (n - 1)

-et már definiáltuk, és az

n

nem szerepel ezek között, akkor legyen

f (n) = f (n - 1) + 1

;

3.

f (1)

...

f (n - 1)

-et már definiáltuk, és az

n

szerepel ezek között, akkor legyen

k

a legkisebb pozitív egész, amelyre

f (k) = n

, és legyen

f (n) = n + k

.
Az alábbi táblázat tartalmazza

f

első néhány értékét.

\begin{matrix} \begin{matrix} \begin{matrix} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ f (n) & 2 & 3 & 5 & 6 & 8 & 10 & 11 & 13 & 14 & 16 & 18 & 19 & 21 & 23 & 24 \end{matrix} \\ \begin{matrix} n & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30 \\ f (n) & 26 & 27 & 29 & 31 & 32 & 34 & 35 & 37 & 39 & 40 & 42 & 44 & 45 & 47 & 48 \end{matrix} \end{matrix} \end{matrix}

10. lemma. Az

f

függvényre a következők teljesülnek:
a) tetszőleges pozitív egész

n

-re

f (n) > n

;
b) az

f

függvény szigorúan monoton nő;
c) tetszőleges

n

pozitív egészre

f (f (n)) = f (n) + n

Bizonyítás. Az a) tulajdonságot teljes indukcióval igazoljuk. Az

n = 1

esetben igaz, mert

f (1) = 2 > 1

. Tegyük fel, hogy igaz

n < m

-re; ebből bebizonyítjuk

n = m

-re is. Ha

m

nem szerepel az

f (1)

...

f (m - 1)

számok között, akkor

f (m) = f (m - 1) + 1 > (m - 1) + 1 = m

. Ha

n

szerepel az

f (1)

...

f (m - 1)

számok között és

k

a legkisebb pozitív egész, amelyre

n = f (k)

, akkor

f (n) = n + k > n

. Ezzel az a) állítást igazoltuk.
A b) állításhoz teljes indukcióval igazoljuk, hogy tetszőleges

n

pozitív egészre

f (n + 1) > f (n)

. Ez

n = 1

-re igaz, mert

f (1) = 2

és

f (2) = 3

. Tegyük fel, hogy

\begin{matrix} f (1) < f (2) < ... < f (n); \end{matrix}

ebből bebizonyítjuk, hogy

f (n) < f (n + 1)

.
Ha

n + 1

nem szerepel az

f (1)

...

f (n)

számok között, akkor

\begin{matrix} f (n + 1) = f (n) + 1 > f (n) . \end{matrix}

Tegyük tehát fel, hogy

n + 1

szerepel az

f (1), ..., f (n)

számok között, és legyen

k

a legkisebb pozitív egész, amelyre

n + 1 = f (k)

; ekkor persze

f (n + 1) = n + k + 1

. Legyen ezután

m = f (k - 1)

; ekkor

f (m) = m + k - 1

. Az indukciós feltevés szerint az

f (1)

...

f (k - 2)

számok kisebbek

f (k - 1)

-nél, ezért az

m + 1

...

n

számok egyike sem szerepel

f (1)

...

f (k - 1)

között. Az

f (k)

...

f (n - 1)

számok pedig az indukciós feltevés szerint nagyobbak

n = f (k - 1)

-nél, ezért az

f

definíciója szerint

\begin{matrix} \begin{matrix} f (m + 1) & = f (m) + 1 = m + k, \\ f (m + 2) & = f (m + 1) + 1 = m + k + 1, \\ ⋮ \\ f (n) & = f (n - 1) + 1 = n + k - 1. \end{matrix} \end{matrix}

Mivel

f (n + 1) = n + k + 1

, most is

f (n) < f (n + 1)

. Ezzel a b) állítást is igazoltuk.
Legyen most

n

tetszőleges pozitív egész. Az a) állítás szerint

f (n) > n

. A b) állítás szerint pedig az

n

-en kívül nincs még egy

k

szám, amelyre

f (n) = f (k)

teljesülne. Ezért az

f

függvény a definíció szerint

f (n)

-hez az

f (n) + n

számot rendeli:

f (f (n)) = f (n) + n

. Ezzel a c) állítást is igazoltuk.
Ezután megkonstruálhatjuk az A. 244. feladatban megkívánt felbontást. Tekintsük az összes olyan

n

f (n)

f (f (n))

f (f (f (n)))

...

sorozatot, amelyben

n

nem eleme

f

értékkészletének. A függvényegyenlet szerint ezek mind Fibonacci-típusú sorozatok:

\begin{matrix} \begin{matrix} 1 & \mapsto 2 \mapsto 3 \mapsto 5 \mapsto 8 \mapsto 13 \mapsto 21 \mapsto 34 \mapsto ... \\ 4 & \mapsto 6 \mapsto 10 \mapsto 16 \mapsto 26 \mapsto 42 \mapsto 68 \mapsto 110 \mapsto ... \\ 7 & \mapsto 11 \mapsto 18 \mapsto 29 \mapsto 47 \mapsto 76 \mapsto 123 \mapsto 199 \mapsto ... \\ 9 & \mapsto 14 \mapsto 23 \mapsto 37 \mapsto 60 \mapsto 97 \mapsto 157 \mapsto 254 \mapsto ... \\ 12 & \mapsto 19 \mapsto 31 \mapsto 50 \mapsto 81 \mapsto 131 \mapsto 212 \mapsto 343 \mapsto ... \end{matrix} \end{matrix}

Azt is könnyű végiggondolni, hogy minden pozitív egész pontosan egy sorozatban szerepel: ez a szigorúan monoton növekedő tulajdonságból következik.

III. megoldás az A. 244. feladatra*

^{$^{*}$} * Versenyzőink közül Horváth Illés, a Fazekas Mihály Főv. Gyak. Gimn. 11. osztályos tanulója oldotta meg így a feladatot.
Ebben a megoldásban az

f

helyett egy másik függvény segítségével adjuk meg a keresett felbontást.
Mint már láttuk, a Fibonacci-típusú sorozatok bizonyos értelemben hasonlítanak a

q = \frac{1 + \sqrt[]{5}}{2}

hányadosú mértani sorozatokhoz. Ez adja a konstrukció alapötletét.

4. definíció. Legyen tetszőleges

n

pozitív egészre

g (n)

az az egész szám, amelyik a legközelebb van a

q n

számhoz, azaz

| g (n) - q n | < \frac{1}{2}

11. lemma. Tetszőleges

n

pozitív egészre

g (g (n)) = g (n) + n

Bizonyítás. Legyen

m = g (n)

és

k = g (g (n)) = g (m)

. Azt kell igazolnunk, hogy

k = m + n

. A

g

definíciója szerint

\begin{matrix} | m - q n | < \frac{1}{2} és | k - q m | < \frac{1}{2} . \end{matrix}

Felhasználva, hogy

q (q - 1) = q^{2} - q = 1

\begin{matrix} \begin{matrix} | k - m - n | = | k - q m + (q - 1) m - q (q - 1) n | < \\ < | k - q m | + (q - 1) | m - q n | < \frac{1}{2} + (q - 1) \frac{1}{2} = \frac{q}{2} < 1. \end{matrix} \end{matrix}

Mivel

k

m

és

n

egész számok, ez csak úgy lehet, ha

k - m - n = 0

.
Innen a II. megoldás szerint haladhatunk az

f

függvény helyett a

g

függvénnyel.

IV. megoldás az A. 244. feladatra

Ez a megoldás Csikvári Péter és Zsbán Ambrus (mindketten a Fazekas M. Főv. Gyak. Gimn. 11. osztályos tanulói) dolgozatából származik.

12. lemma. Minden pozitív egész számot egyértelműen felírhatunk különböző Fibonacci-számok összegeként úgy, hogy nem használunk fel szomszédos Fibonacci-számokat, például

17 = 1 + 3 + 13

49 = 2 + 13 + 34

.
Ennek a lemmának a felhasználásával egy szép konstrukció adható a szükséges Fibonacci-típusú sorozatokra.
Tekintsünk egy olyan számot, amelynek a 12. lemma szerinti felírásában a tagok között szerepel az

1

\begin{matrix} F_{i_{1}} + F_{i_{2}} + ... + F_{i_{k}}, \end{matrix}

ahol

i_{j + 1} \geq i_{j} + 2

és

i_{1} = 2

. (

F_{1} = F_{2} = 1

miatt nem engedjük meg a

0

és

1

indexeket.) Ha ebben az összegben az összes tagot a rákövetkező Fibonacci-számra cseréljük ki, akkor egy másik számot kapunk. Ezt a műveletet ismételve pedig egy sorozatot:

\begin{matrix} F_{i_{1}} + ... + F_{i_{k}}, F_{i_{1} + 1} + ... + F_{i_{k} + 1}, F_{i_{1} + 2} + ... + F_{i_{k} + 2}, ... \end{matrix}

Ez a sorozat a Fibonacci-sorozat

k

darab eltoltjának összege, tehát maga is Fibonacci-típusú.
Minden pozitív egész

n

pontosan egy ilyen sorozatban szerepel. Ha ugyanis

n

-et felírjuk a 12. lemmának megfelelően, akkor a tagokat a megfelelő kisebb Fibonacci-számokra cserélve egyértelműen meghatározható annak a sorozatnak az első eleme, amelyik az

n

-et tartalmazza.

Az így kapott Fibonacci-típusú sorozatok:

1

2

3

5

8

...

4 = 1 + 3

7 = 2 + 5

11 = 3 + 8

18 = 5 + 13

...

6 = 1 + 5

10 = 2 + 8

16 = 3 + 13

26 = 5 + 21

...

9 = 1 + 8

15 = 2 + 13

24 = 3 + 21

39 = 5 + 34

...

12 = 1 + 3 + 8

20 = 2 + 5 + 13

32 = 3 + 8 + 21

52 = 5 + 13 + 34

...

⋮

8. feladat. Bizonyítsuk be a

12

. lemmát!

További feladatok

9. feladat. Bizonyítsuk be, hogy az I. és a II. megoldás ugyanazt a felbontást állítja elő.

10. feladat. Mutassuk meg, hogy az I., a III. és a IV. megoldás három különböző konstrukciót ad a feladatra.

11. feladat. Két játékos a következő játékot játssza: Két kupac kavicsból felváltva vesznek el. Egy lépésben vagy az egyik kupacból vehetnek el legalább egy kavicsot, vagy pedig mindkét kupacból ugyanannyit. Az veszít, aki nem tud lépni. Mutassuk meg, hogy a második játékosnak pontosan akkor van nyerő stratégiája, ha a kiinduló állásban az egyik kupacban

a_{n} - 1

, a másik kupacban

b_{n} - 1

darab kavics van, ahol

n

alkalmas természetes szám,

a_{n}

és

b_{n}

pedig a 2. definícióban szereplő sorozatok megfelelő elemei.

12. feladat. Legyen

(a_{n})

, illetve

(b_{n})

a 2. definícióban szereplő sorozat. Igazoljuk, hogy tetszőleges

n

nemnegatív egészre

a_{n} = [q n] + 1

és

b_{n} = [q^{2} n] + 1

. (

[x]

x

egész része.)

13. feladat. Jelöljük

h

-val azt a függvényt, amely minden pozitív egészhez a IV. megoldásban látott felírása eltoltját rendeli; más szóval, ha az

1 < i_{1} < ... < i_{k}

egész számok között nincsenek szomszédosak, akkor legyen

h (F_{i_{1}} + ... + F_{i_{k}}) = F_{i_{1} + 1} + ... + F_{i_{k} + 1}

. Bizonyítsuk be, hogy tetszőleges

n

pozitív egészre

\begin{matrix} q n - \frac{1}{q^{2}} < h (n) < q n + \frac{1}{q} . \end{matrix}

14. feladat. Azt mondjuk, hogy a

(c_{n})

sorozat a

(d_{n})

sorozat bővítése, ha létezik olyan

k

nemnegatív egész szám, amelyre

c_{n + k} = d_{n}

, azaz a

(c_{n})

sorozatot úgy kapjuk, hogy a

(d_{n})

sorozat elé további elemeket írunk. Bizonyítsuk be, hogy ha

(c_{n})

és

(d_{n})

pozitív számokból álló, monoton növő Fibonacci-típusú sorozatok és egyik sem a másik bővítése, akkor
a) legfeljebb két közös elemük van;
b) ha két közös elemük van, akkor az első elemeik megegyeznek.

15. feladat. Bizonyítsuk be a következő azonosságokat teljes indukcióval és a 2. lemma segítségével is.

\begin{matrix} \begin{matrix} F_{n}^{2} - F_{n - 1} F_{n + 1} & = {(- 1)}^{n + 1} \\ F_{2 n - 1} & = F_{n}^{2} + F_{n - 1}^{2} \\ F_{3 n - 1} & = F_{n}^{3} + 3 F_{n}^{2} F_{n - 1} + F_{n - 1}^{3} \end{matrix} \end{matrix}

Énekes Béla, Kós Géza

^{$^{*}$}