P R E S E K
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652 Letnik 25 (1997/1998) Številka 4 Strani 232-237
Sandi Klavžar:
PRVO SREČANJE S FIBONACCIJEVIMI ŠTEVILI
Ključne besede: matematika, teorija števil, številska zaporedja, Fibonacci, rekurzivne formule.
Elektronska verzija: http://www.presek.si/25/1340-Klavzar.pdf
© 1998 Društvo matematikov, fizikov in astronomov Slovenije © 2010 DMFA - založništvo
PRVO SREČANJE S FIBONACCIJEVIMI ŠTEVILI
Verjetno marsikdo med vami že pozna Fibonaccijeva števila, saj tudi Presek pogosto piše o njih. Tako sta v lanskem letniku izšla dva računalniško obarvana prispevka o izračunavanju posplošenih Fibonaccijevih števil. Gotovo pa so med bralci tudi taki. ki Fibonaccijevih števil še niso srečali. Predvsem njim je namenjen ta prispevek, kar pa seveda še ne pomeni, da ni primeren tudi za poznavalce. V matematiki je namreč tako, da je zelo koristno, če isto strukturo spoznamo z različnih vidikov. Pogosto se nam namreč dozdeva, da neki pojem dobro razumemo, pa se kasneje izkaže, da smo v resnici ta pojem razumeli le delno ali površno.
Zakaj se ta Števila imenujejo Fibonaccijeva
Zgodba se začne leta 1202, ko je Leonardo iz Pise, bolj znan po psevdonimu Fibonacci, napisal knjigo Liber Abacti in v njej zastavil sloviti problem o zajcih. Pravzaprav je ohranjena le druga izdaja knjige iz leta 1228. Kakorkoli že, vprašanje je naslednje:
Par zajcev, ki je star vsaj dva meseca, vsak mesec skoti en par zajcev. Koliko parov zajcev imamo po enem letu, če začnemo z enim parom na novo skoteni I i zajcev?
V prvem mesecu imamo torej en par zajcev. V drugem mesecu imamo še vedno samo ta par, saj zajca iz para še nista dopolnilu dveh mesecev. V tretjem mesecu imamo nato dva para: začetni par in par, ki sta ga skotila. V naslednjem mesecu iinamo tri pare: tista dva iz prejšnjega meseca ter par, ki ga je skot.il začetni par. Namesto da sedaj nadaljujemo s takim razmišljanjem, se rajši kar vprašajmo, koliko parov zajcev imamo v 12. mesecu. Najprej ugotovimo, da imamo v 12. mesecu vse pare zajcev, ki smo jih imeli v 11. mesecu (saj v nalogi ni nobenega pogoja o umrljivosti). Koliko pa je novih parov? Vsak par, ki je dopolnil dva meseca, je skotil en par. Takih parov pa je ravno toliko, kot je bilo vseh parov v 10. mesecu. Torej, v 12. mesecu imamo toliko parov, kolikor jih je bilo v 10. in v 11. mesecu skupaj. Celo več, razmislek, ki smo ga naredili, velja za poljuben mesec in ne le za dvanajstega.
Naj bo Fn število parov zajcev v «.-tem mesecu. Ugotovili smo, tla je Fi = 1, F2 = 1, F3 = 2, F.\ = 3 in FX2 = Fn + /V Celo več, za vsak rt > 2 veija Fn — jFn_t + Fn^2- Fibonaccijeva števila so torej števila, ki so definirana takole:
Prvi dve Fibonaccijevi števili sta enaki Xi Fj = 1 in F2 = 1.
Za vse ji > 2 je 7!-to Fibonaccijevo število vsota prejšnjih dveh: F„ —
— Fn-1 + 2-
Pravimo, da so Fibonaccijeva števila podana z rekurzivno formulo. Prvih nekaj Fibonaccijevih števil je:
1,1,2, 3, 5,8,13, 21,34,55,89,144, 233,377,610,987,1597,...
Vidimo torej, da imamo v 12, mesecu 144 parov zajcev, po 12. mesecu pa jih je že 233, Skratka, množijo se kot zajci.
Kje še najdemo Fibonaccijeva števila
Seštevamo z enicami in dvojkami
Za poljubno naravno število n se vprašajmo, na koliko različnih načinov ga lahko zapišemo kot vsoto samih enic in dvojk. Na primer, število 5 lahko zapišemo na naslednjih 8 načinov:
5=1+1+1+1+1
5=1+1+1+2
5=1+1+2+1
5=1+2+1+1
5=2+1+1+1
5=1+2+2
5=2+1+2
5=2+2+1
Označimo število zapisov števila n z aTl. Gornji primer torej pravi = 8. Bralec naj sedaj poskusi zapisati vse načine za število 6, mi pa zapišimo vse načine za števila do 5:
1	= 1 (ai = 1),
2	= 1 + 1 = 2 (aa = 2),
3= 1 + 1 + 1= 1 + 2 = 2+1 (03 = 3),
4=1 + 1 + 1 + 1 = 1 + 1 + 2 = 1 + 2 + 1 = 2 + 1+1 = 2 + 2 (04 = 5)
Število načinov po vrsti je torej 1, 2, 3, 5, 8, 13; slednje naj bi bralec preizkusil sam. To pa je, z izjemo manjkajočega prvega Fibonaccijevega števila Fi, prav prvih nekaj Fibonaccijevih števil. Dokažimo, da to velja tudi v splošnem.
Poglejmo si vse zapise števila n z erucami in dvojkami. Razdelimo zapise v dve skupini: na tiste zapise, ki se začnejo z 1. in na tiste, ki se začnejo z 2. Zapisov, ki se začnejo z 1, je prav toliko, kot je zapisov števila ti — I, kar sprevidimo z odstranitvijo začetnih enic. In dalje, zapisov, ki se začnejo z 2, je prav toliko, kot zapisov števila n — 2. Torej imamo zvezo an = an^i+an-2- Ker je a\ = 1 in «2 — 2, lahko zaključimo, daje število zapisov števila n z enicami in dvojkami enako , na kratko an =
Hodimo po stopnicah
Stopnišče je sestavljeno iz n stopnic. Na koliko različnih načinov se lahko povzpnemo do vrha, če na vsakem koraku prestopimo eno ali dve stopnici?
Naj b7l označuje iskano število. Očitno velja &i = 1 in 62 = 2. Ce smo na prvem koraku prestopili eno stopnico, imamo bn_i načinov do prihoda na vrh, če pa smo na prvem koraku prestopili dve stopnici, imamo do konca f»n_2 možnosti. Torej, brl = = bn_i + in zopet lahko zaključimo, da je bn = Fn+l.
Dodajmo k temu primeru, da ga nam pravzaprav ni bilo potrebno reševati. Dovolj bi bilo uporabiti enega najljubših trikov
matematikov: problem prevedemo na že znani, rešeni primer. Vsak naj sam premisli, da je problem s stopnicami pravzaprav samo preoblečen problem z vsotami iz enic in dvojk.
Zlagamo kovance
Imamo n enakih kovancev. Zanima nas, na koliko različnih načinov lahko kovance zložimo drugega ob drugega v eno ali dve vrsti. Pri tem mora veljati, da sta pod kovancem v zgornji vrsti vedno dva kovanca v spodnji vrsti. Na sliki 1 imamo prikazanih vseh 8 načinov, kako lahko zložimo 6 kovancev.
GOCCOO
Slika 1, Sest kovancev v dve vrsti
S cn označimo število načinov, na katere lahko zložimo n kovancev v dve vrsti. Slika 1 nam torej pove, da je c6 = 8. Vsak ho sam brez težav preveril, daje c¡ = 1, c2 — 1, c-¿ — 2, c4 — 3 in c$ = 5. Začetek zaporedja števil cn se torej ujema s Fibonaccije v i m i števili Fn. V resnici za vsak n velja cn = Fn. Tega tu ne bomo dokazali, omenimo pa, daje ta lastnost Fibonaccijevih števil v tesni zvezi s slavnim Pascalovim trikotnikom.
Štejemo debele množice
Končno množico naravnih števil imenujemo debela, če je vsak njen element vsaj tako veliko število, kot ima množica elementov. Na primer, množici {4,7,12,99} in {3,4,5} sta debeli, medtem ko množici {1,2} in {2,99.100} nista debeli. Dogovorimo se tudi, da prazno množico obravnavamo kot debelo množico.
Z dn označimo število debelih podinnožic množice {1,2,... ,n}. Na primer, d\ — 8, saj ima množica {1,2,3,4} naslednje debele podmnožice:
0, {1}, {2}, {3}, {4}, {2,3}, {2,4} in {3,4}.
Verjetno ne bo nihče posebej presenečen, če kar povem, da je d\ = 2. d2 = 3, d% = 5, d4 = 8 (kot že vemo) in d5 ~ 13. Kot vse kaže, velja dn = Fn+2- Kako pa bi to dokazali?
Morda bo najlažje tako, da prevedemo pro Lil eni debelih množic na zlaganje kovancev v dve vrsti. Idejo, kako to naredimo, razložimo kar na primeru za d4. Vzemimo šest kovancev (4 + 2, tj. n + 2), jih postavimo v vrsto in v zgornjo vrsto od drugega mesta dalje zapísimo števila od 1 do 4 (glej sliko 2). Postavitev vseh šestih kovancev v vrsto ustreza prazni množici. Nato prečrtajmo prvi kovanec, ki ga moramo zato postaviti v gornjo vrsto na označena mesta. Ce to naredimo na vse možne načine, dobimo množice {1}, {2}, {3} in {4}. Nazadnje prečrtajmo prva dva kovanca. Na vse možne načine ju postavimo v gornjo vrsto, kar nam da še množice {2,3}. {2,4} in {3,4}, Torej smo ugotovili, da je d.4 = cq = Fg. Razmislek, ki smo ga naredili za ta primer, lahko brez težav ponovimo za poljuben n, torej res velja dn = F,
cxxxrb 0jáxb
Slika 2. Z debelih množic do zlaganja kovancev
Nekaj preprostih lastnosti Fibonaccijevih števil
Seštejmo nekaj prvih Fibonaccijevih števil:
1 + 1—2 1+1+2=4 1+1+2+3=7 1 + 1 + 2 + 3 + 5 = 12 1+1 + 2 + 3 + 5 + 8 = 20
Ce dobljene vsote dobro pogledamo, opazimo, da dobivamo za ena zmanjšana Fibonaccijeva števila. Dokažimo, da to velja za vse n. Upoštevajmo, da je Fn — + Frj_2, oziroma Fn-2 — Fn — Fn_i- Zato imamo:
Fi^Fs- F2 F2 = F. 1 — F3 F^ — Fs — F4
Fti-\ = Fn+1 — Fn Fn = Fn+2 — Ffi+i
Sedaj seštejemo leve strani in desne strani gornjih enakosti. Na levi dobimo Fi + F2 + + Fn, torej izraz, ki nas zanima. Na desni strani pa se skoraj vsi členi paroma odštejejo, ostane nam le Fn_2 ~ ■ Ker je F2 — 1, smo tako pokazali:
Fi+F2 + ... + Fn = Fn+2 - 1.
Na podoben način, kot. smo dokazali zadnjo enakost, lahko dokažemo tudi naslednje lastnosti Fibonaccijevih števil. Bralca vabim, da jih poskuša pokazati sam.
Fj, + Fa + Fs +... + F2n-3 + F2n-i = F2n . Npr.: 1 + 2 + 5+ 13 + 34 + 89 = 144.
F2 + Fn + Fe + ... + F2n-2 + F2n = i^n+i — 1 ■
Npr.: 1 + 3 + 8 + 21 + 55 = 88 = 89- 1.
Fi - F2 + F3 - F4 + ... + F2n-1 - F2n = -F2n~i + 1 -Npr.: 1 - 1 + 2 - 3 + 5 - 8+13 - 21 + 34 - 55 =-33 =-34 + 1.
Sedaj pa seštejmo še kvadrate prvih n Fibonaccijevih Števil. Upoštevajmo, da velja
Fn — FnFn — Fn{Fn+1 — F„_i) = F„F„+i — FnFn-i
in zapišimo:
F? = 1 = FyF2 F-2 — F2F3 — F3.F1 F3 = F-jF.i — F3F2
F2 . = F ,F— F 1F
^n—l — ^n—l^n * n—1 * n—2
= FnFn+1 — FnFn-t Seštejemo leve i» desne strani pa dobimo
F2 + F2 + F2 + ... + F2 = FnFn+1.
Npr.: 1 + 1 + 4 + 9 + 25 + 6-1 + 169 = 273 = 13 • 21.
Podobnih identitet s Fibonacdjevimi števili je še zelo veliko, vendar naj omenjene za prvo srečanje s temi števili zadoščajo.
Članek smo začeli s problemom o razmnoževanju zajcev. Resnici na ljubo povejmo, da Fibonaccijeva števila nimajo kakega posebnega pomena pri v z rej i zajcev, med drugim tudi zato ne, ker problem zanemarja umrljivost. Po drugi strani pa so Fibonaccijeva števila izjemno pomembna v matematiki, saj obstaja, posebna veja matematike, ki se ukvarja samo s problemi, povezanimi s temi števili.