PEDAGOŠKA FAKULTETA
KATARINA VIDMAR
KOMBINATORIČNI DOKAZI FIBONACCIJEVIH IN SORODNIH IDENTITET
DIPLOMSKO DELO
LJUBLJANA, 2017
PEDAGOŠKA FAKULTETA
DVOPREDMETNI UČITELJ: MATEMATIKA – RAČUNALNIŠTVO
KATARINA VIDMAR
Mentor: doc. dr. BOŠTJAN KUZMAN
KOMBINATORIČNI DOKAZI FIBONACCIJEVIH IN SORODNIH IDENTITET
DIPLOMSKO DELO
LJUBLJANA, 2017
Zahvaljujem se mentorju doc. dr. Boštjanu Kuzmanu za vse napotke, popravke in strokovno pomoč pri pisanju diplomskega dela.
Hvala tudi družini in prijateljem, ki so mi v času študija stali ob strani.
V diplomskem delu obravnavamo kombinatorične dokaze Fibonaccijevih in sorodnih identitet. Kombinatorični dokazi se izkažejo za močno orodje, ki je uporabno na različnih matematičnih področjih, kot so teorija grup, teorija množic, analiza ter teorija grafov.
Pred samim dokazovanjem identitet, ki vsebujejo Fibonaccijeva ali sorodna števila, si pogledamo različne vrste dokazov, kot so algebrski direktni dokaz, dokaz z indukcijo, dokaz s protislovjem ter vizualni dokaz in jih ilustriramo na primerih. Nato opredelimo Fibonaccijeva števila ter vpeljemo njihovo kombinatorično interpretacijo. Obravnavamo tudi posplošitve Fibonaccijevih števil. Ogledamo si zaokrožen izbor Fibonaccijevih in sorodnih identitet, ki jih kombinatorično dokažemo predvsem z metodo dvojnega štetja. V diplomsko delo je vključenih tudi nekaj identitet, ki so bile na kombinatoričen način dokazane nedavno, naveden pa je tudi kombinatorični dokaz Binetove formule. Nazadnje nekaj konceptov ilustriramo tudi s pomočjo Geogebre.
Ključne besede: kombinatorični dokaz, dvojno preštevanje, Fibonaccijeva števila, Fibonaccijeve identitete
In this diploma thesis, the combinatorial proofs of Fibonacci and related identities are discussed. The combinatorial proofs prove to be strong tools, useful in different mathematical fields, such as group theory, set theory, analysis and theory of graphs.
Before the proving of identities containing Fibonacci or related numbers, different types of proofs, such as direct algebraic proof, proof with mathematical induction, proof by contradiction and visual proof, are examined and illustrated with cases. Then, Fibonacci numbers are defined and their combinatorial interpretation introduced. The generalisations of Fibonacci numbers are also discussed. A rounded selection of Fibonacci numbers and similar identities are reviewed, and combinatorically proven, in particular with the double counting method. The diploma thesis also discusses some identities that have only recently been combinatorically proven; a combinatorial proof for the Binet’s formula is also cited.
Finally, some of the concepts are illustrated also with the help of GeoGebra.
Keywords: combinatorial proof, double counting, Fibonacci numbers, Fibonacci identities
1. UVOD ... 1
2. VRSTE DOKAZOV ... 3
2. 1. Algebrski direktni dokaz ... 3
2. 2. Dokaz z indukcijo... 3
2. 3. Dokaz s protislovjem ... 4
2. 4. Vizualni dokaz... 4
2. 5. Kombinatorični dokaz ... 5
2. 5. 1. Bijektivni dokaz ... 5
2. 5. 2. Metoda dvojnega štetja ... 7
3. FIBONACCIJEVA ŠTEVILA... 9
3. 1. Kombinatorična interpretacija Fibonaccijevih števil ... 9
3. 2. Posplošitve Fibonaccijevih števil ... 10
3. 2. 1. Kombinatorična interpretacija Lucasovih števil ... 11
3. 2. 2. Kombinatorična interpretacija Gibonaccijevih števil ... 12
4. FIBONACCIJEVE IDENTITETE IN NJIHOVI KOMBINATORIČNI DOKAZI ... 15
5. LUCASOVE IN GIBONACCIJEVE IDENTITETE TER NJIHOVI KOMBINATORIČNI DOKAZI ... 29
6. BINETOVE FORMULE ... 34
7. PONAZORITVE DOKAZOV S POMOČJO GEOGEBRE... 46
8. SKLEP ... 48
VIRI IN LITERATURA ... 49
SLIKA 1:VIZUALNI DOKAZ IDENTITETE 1 + 3 + 5 + ⋯ + 2 − 1 = ... 5
SLIKA 2:VIZUALNI DOKAZ IDENTITETE 1 + 3 + 5 + ⋯ + 2 − 1 = ... 6
SLIKA 3:TLAKOVANJA ZA = 8 ... 10
SLIKA 4:VSA MOŽNA TLAKOVANJA KROŽNE DESKE DOLŽINE 4 ... 11
SLIKA 5:FAZNA 4-TLAKOVANJA ... 13
SLIKA 6:VSA TLAKOVANJA DOLŽINE 3 PRI ZAČETNIH POGOJIH = 2, = 3 ... 14
SLIKA 7:LOMLJIVOST TLAKOVANJA DOLŽINE + ... 17
SLIKA 8:SREDINSKI KVADRAT ... 19
SLIKA 9:TLAKOVANJE DOLŽINE 3 − 1(BENJAMIN IDR.,2008:3) ... 23
SLIKA 10:TLAKOVANJE RAZDELIMO NA BLOKE (BENJAMIN IDR.,2008:3) ... 24
SLIKA 11:DOBLJENO BARVNO TLAKOVANJE (BENJAMIN IDR.,2008:3) ... 24
SLIKA 12:TLAKOVANJE DOLŽINE 2 − 1(BENJAMIN IDR.,2008:4) ... 24
SLIKA 13:PRESLIKAVA PAROV V BARVNE PLOŠČICE (BENJAMIN IDR.,2008:7) ... 26
SLIKA 14:TLAKOVANJE DOLŽINE 12(BENJAMIN IDR.,2008:8) ... 26
SLIKA 15:PRESLIKAVA PAROV (BENJAMIN IDR.,2008:8) ... 27
SLIKA 16:PRESLIKAVA BLOKOV V PLOŠČICO BARVE 5(BENJAMIN IDR.,2008:8) ... 27
SLIKA 17:TLAKOVANJE DOLŽINE 12(BENJAMIN IDR.,2008:9)... 27
SLIKA 18:PRESLIKAVA BLOKOV (BENJAMIN IDR.,2008:9) ... 28
SLIKA 19:INTERPRETACIJA FIBONACCIJEVIH ŠTEVIL V GEOGEBRI ... 46
SLIKA 20:DELOVNI LIST OMOGOČA ODKRIVANJE UGOTOVITEV ... 46
SLIKA 21:PONAZORITEV KOMBINATORIČNEGA DOKAZA V GEOGEBRI ... 47
1
1. UVOD
Diplomsko delo Kombinatorični dokazi Fibonaccijevih in sorodnih identitet sodi na področje kombinatorike, kot pove že sam naslov. Kombinatorika je veja matematike, ki se ukvarja z izbiranjem objektov iz množice ali z razporejanjem objektov glede na specifična pravila. Poskuša odgovarjati na dva tipa vprašanj – ali je razporeditev objektov sploh možna ter na koliko različnih načinov jo lahko izvedemo, in ali obstaja izbor oziroma razporeditev objektov z določeno množico lastnosti. (Cameron, 1994; Wallis in George, 2017)
V diplomskem delu se ukvarjamo s kombinatoričnimi dokazi identitet. Dokazi so sami po sebi pomembni za matematiko. Različni tipi dokazov odprejo nove poglede na rezultate in na povezave med različnimi vejami matematike. Spoznavamo se z metodo dvojnega štetja, torej štetja objektov na dva različna načina. Na primer, če se vprašamo koliko krav se pase na pašniku, lahko le-te preštejemo po številu glav, lahko pa preštejemo vse noge in dobljeno število delimo s štiri. Metoda dvojnega štetja lahko na prvi pogled izgleda zelo preprosta, vendar je ta prvi vtis lahko varljiv. Gre namreč za zelo močno orodje, ki ga lahko uporabimo tudi na drugih področjih matematike in ne samo v kombinatoriki ter teoriji množic.
Uporabno je tudi v teoriji grafov, kjer lahko na ta način dokažemo na primer lemo o rokovanju oziroma v teoriji grup, kjer lahko s pomočjo metode dvojnega štetja dokažemo izrek o orbitah in stabilizatorjih permutacijskih grup. (Alsina in Nelsen, 2010; Klavžar, 2008)
Dokazi pa niso bistvenega pomena samo za matematike, ampak tudi v izobraževanju.
Svetovno največja matematična izobraževalna organizacija »National council of teachers of mathematics« (National Council of Teachers of Mathematics, 2000) priporoča, naj učni načrt vse od prvega razreda naprej omogoča vsem učencem prepoznati dokaze kot temeljni vidik matematike. Vsi učenci bi morali priti do točke, ko razumejo naravo dokaza, saj je ravno dokaz tisto, kar naredi matematiko posebno. (Alsina in Nelsen, 2010)
V diplomskem delu opišemo nekaj osnovnih pojmov, ki jih bralec potrebuje za razumevanje diplomskega dela. Posvetimo se različnim vrstam dokazov, nato pa se osredotočimo na glavno temo diplomskega dela – Fibonaccijeve identitete in njihovi
2
kombinatorični dokazi, pri tem si najprej ogledamo kombinatorično interpretacijo Fibonaccijevih števil. Fibonaccijeva števila interpretiramo kot število možnih tlakovanj deske dolžine . Kombinatorično interpretiramo tudi Lucasova in Gibonaccijeva števila, nato pa se lotimo kombinatoričnih dokazov identitet. V diplomskem delu si ogledamo tudi nekaj novejših rezultatov iz raziskovalne literature, in sicer dokažemo nekatere Vajdove identitete, predstavimo pa tudi kombinatorični dokaz Binetove formule. Za konec si ogledamo še kako bi lahko s pomočjo Geogebre ponazorili kombinatorično dokazovanje prej omenjenih identitet.
3
2. VRSTE DOKAZOV
Narava matematičnih dokazov temelji na vsebini matematične trditve. Alsina in Nelsen navajata formalno definicijo, ki pravi, da je matematični dokaz končno zaporedje formalnih matematičnih izjav, tako da je vsaka izjava bodisi aksiom ali predpostavka bodisi s formalnimi pravili logične dedukcije sledi prejšnji izjavi v zaporedju. Dokaze lahko klasificiramo glede na metode, ki jih uporabimo za dokazovanje matematične trditve.
Poglejmo si nekaj vrst dokazov. (Alsina in Nelsen, 2010; Dumas in McCarthy, 2015)
2. 1. Algebrski direktni dokaz
Z algebrskim direktnim dokazom s pomočjo definicij, aksiomov in predhodno dokazanimi izreki pokažemo, da zaključek logično sledi iz hipotez. (Alsina in Nelsen, 2010) Poglejmo si kako bi z algebrskim direktnim dokazom pokazali, da velja 1 + 3 + 5 + ⋯ + (2 − 1) = .
Dokaz: Naj bo
= 1 + 3 + 5 + ⋯ + (2 − 5) + (2 − 3) + (2 − 1).
Zaradi komutativnosti seštevanja sledi
= (2 − 1) + (2 − 3) + (2 − 5) + ⋯ + 5 + 3 + 1.
Če seštejemo enačbi, dobimo
2 = 2 + 2 + 2 + ⋯ + 2 = ∙ (2 ) = 2 .
Torej, = . S tem smo dokazali, da enakost 1 + 3 + 5 + ⋯ + (2 − 1) = res velja.
■
2. 2. Dokaz z indukcijo
Matematična indukcija je metoda, s pomočjo katere pokažemo, da je trditev oblike ( ) resnična za vsak pozitiven ∈ ℕ. V prvem koraku pokažemo, da je (1) resnična, v drugem koraku pa pokažemo, da če je resnična ( ), je resnična tudi ( + 1). (Alsina in Nelsen, 2010) Za zgled bomo s pomočjo indukcije dokazali, da velja 1 + 3 + 5 + ⋯ + (2 − 1) = .
Dokaz: Najprej preverimo, če trditev velja za = 1. Sledi, 1 = 1 = 1. V vsoti na levi strani je le en člen, ki je enak 1, desna stran pa je 1. Ker sta leva in desna stran enaki, trditev
4
za = 1 velja. V naslednjem koraku privzamemo, da enačba velja za naravno število in preverimo, če velja tudi za + 1. Dokazujemo, da pri tej predpostavki velja:
1 + 3 + 5 + ⋯ + (2 − 1) + (2 + 1) = ( + 1) . Začnemo na levi strani in upoštevamo indukcijsko predpostavko:
1 + 3 + 5 + ⋯ + (2 − 1) + (2 + 1) = + (2 + 1).
Sledi:
1 + 3 + 5 + ⋯ + (2 − 1) + (2 + 1) = ( + 1) .
Ker indukcijski sklep velja za poljubno naravno število , po načelu popolne indukcije enakost velja za vsa naravna števila .
■
2. 3. Dokaz s protislovjem
Z dokazom s protislovjem pokažemo, da je logično nemogoče, da bi bila trditev napačna.
Običajno to storimo tako, da predpostavimo, da je trditev, ki jo dokazujemo napačna, kar pa nas pripelje do logičnega protislovja. (Alsina in Nelsen, 2010) Za zgled bomo pokazali, da število √3 + √13 ni racionalno število.
Dokaz: Recimo, da je število √3 + √13 = racionalno število. Enačbo kvadriramo in dobimo 3 + 2√39 + 13 = . Sledi, da je √39 = . Od tod sklepamo, da je √34 racionalno število, kar pa ni mogoče, ker število 39 ni popoln kvadrat. Za korene naravnih števil namreč vemo, da so bodisi naravna bodisi iracionalna števila. Prišli smo do protislovja s predpostavko, da je √3 + √13 racionalno število.
■
2. 4. Vizualni dokaz
Vizualni dokaz je »dokaz«, ki temelji na izključno vizualnih elementih. Služi kot pomoč pri predstavi in formalnem dokazovanju. (Proof without words, b. d.) Kombinatorični dokaz je lahko vizualni, če ilustriramo kako smo prešteli objekte v množici na dva načina oziroma če ilustriramo bijektivno preslikavo med dvema množicama. Ostale tehnike pa vključujejo uporabo geometrijskih transformacij, kot sta refleksija in rotacija, tlakovanje in
5
uporabo barv. (Alsina in Nelsen, 2010) Poglejmo si primer vizualnega dokaza identitete 1 + 3 + 5 + ⋯ + (2 − 1) = . (Nelsen, 1993)
Slika 1: Vizualni dokaz identitete 1 + 3 + 5 + ⋯ + (2 − 1) =
2. 5. Kombinatorični dokaz
Kombinatorični dokaz je metoda, s pomočjo katere dokazujemo algebrske identitete tako, da števila predstavimo kot množico objektov, nato pa objekte preštevamo. Pojem kombinatorični dokaz v matematiki največkrat pomeni enega od naslednjih dveh principov.
2. 5. 1. Bijektivni dokaz
Bijektivni dokaz je tehnika dokazovanja, kjer eksplicitno opišemo bijektivno preslikavo med dvema končnima množicama. S tem pokažemo, da imata množici enako moč. (Alsina in Nelsen, 2010)
Za dokaz identitete 1 + 3 + 5 + ⋯ + (2 − 1) = lahko podamo kombinatorični dokaz, in sicer lahko identiteto dokažemo tako z metodo dvojnega štetja kot tudi z bijektivnim dokazom. Na sliki 1 lahko štejemo kroglice na dva načina, najprej štejemo število kroglic v vsakem območju L-oblike, nato pa še preštejemo koliko kroglic sestavlja stranico kvadrata. S tem navedemo dokaz z metodo dvojnega štetja. Lahko pa eksplicitno opišemo bijektivno preslikavo med območjem trikotne oblike sestavljene iz kroglic in območjem kvadratne oblike kot je prikazano na sliki 2. (Alsina in Nelsen, 2010)
6
Slika 2: Vizualni dokaz identitete 1 + 3 + 5 + ⋯ + (2 − 1) =
Poglejmo si še en zgled bijektivnega dokaza. Dokazovali bomo naslednjo identiteto:
∑ 2 = ∑ 2 + 1 , za > 0.
Obe vsoti v identiteti sta končni, saj velja = 0, če > .
Dokaz: Poglejmo si, kaj šteje posamezna stran identitete. Leva stran predstavlja množico, v kateri so vsi izbori sodega števila elementov izmed elementov. Desna stran pa predstavlja množico, v kateri so vsi izbori lihega števila elementov izmed elementov. Za lažjo predstavo si predstavljajmo, da govorimo o skupinah študentov. Leva stran torej predstavlja vse skupine sode velikosti, ki jih lahko sestavimo iz razreda študentov. Desna stran pa predstavlja vse skupine lihe velikosti, ki jih lahko sestavimo iz razreda študentov.
Da bi pokazali, da imata množici enako moč, moramo poiskati bijektivno preslikavo med njima. Predpostavimo, da je enemu študentu v razredu ime Luka. Vsako skupino sode velikosti lahko spremenimo v skupino lihe velikosti, če se vprašamo »Kje je Luka?«. Če je Luka v skupini sode velikosti, ga odstranimo, sicer ga dodamo. V obeh primerih spremenimo skupino sode velikosti v skupino lihe velikosti. Opisan proces je popolnoma reverzibilen, torej smo našli bijektivno preslikavo med danima množicama. Posledično imata množici enako velikost. Zapišimo dokaz še formalno. Naj množica predstavlja razred in ∈ osebo po imenu Luka. Definirajmo funkcijo ( ) = − { }; č ∈
∪ { }; č ∉ . Dobljena funkcija množici vselej doda ali odvzame en element, torej res preslika podmnožice sodega reda v podmnožice lihega reda v . Pokažimo, da je injektivna. Naj bo ( ) = ( ) in ločimo dva primera:
1. Če je ∈ ( ) in ∈ ( ), potem ∉ in ∉ . ( ) = ⋃{ } in ( ) =
⋃{ }, torej je = .
7
2. Če ∉ ( ) in ∉ ( ), potem ∈ in ∈ . Zato je ( ) = − { } in ( ) = − { }. Spet sledi = .
Pokažimo še, da je funkcija surjektivna. Naj bo poljubna podmnožica v lihega reda.
Če vsebuje , potem za množico = − { } velja ( ) = . Če pa ne vsebuje , potem za množico = ⋃{ } velja ( ) = . V vsakem primeru smo našli množico lihega reda, ki se preslika v . Dokazali smo, da je funkcija injektivna in surjektivna, torej je bijektivna. S tem smo dokazali identiteto. (Benjamin in Quinn, 2003)
■
2. 5. 2. Metoda dvojnega štetja
Dokaz z metodo dvojnega štetja, s katerim pokažemo, da sta izraza na levi in desni strani identitete = enaka. To storimo tako, da si postavimo pravo vprašanje. Na vprašanje odgovorimo s preštevanjem elementov množice objektov na dva različna načina.
Posamezni način štetja nam predstavlja eno stran enačbe. (Alsina in Nelsen, 2010)
Poglejmo si primer. Kot smo že omenili, je metoda kombinatoričnega dokaza uporabna na različnih področjih. Za zgled si poglejmo kombinatorični dokaz osnovnega rezultata iz področja teorije grafov, in sicer Leme o rokovanju.
Lema o rokovanju: Naj bo = ( , ) graf. Tedaj velja, da je vsota stopenj vozlišč enaka dvakratniku števila povezav: ∑ ∈ ( ) = 2| |.
Dokaz: Vsaka povezava ima dve krajišči, vsako vozlišče pa leži na deg ( ) povezavah.
Če seštejemo stopnje vseh vozlišč, smo torej vsako povezavo šteli dvakrat. Zato sledi
∑ ∈ ( ) = 2| |. (Klavžar, 2008)
■ S pomočjo dokaza z metodo dvojnega štetja pa lahko pokažemo tudi, da nekaj ni mogoče.
Poglejmo si zgled. Zanimalo nas bo, če v mreži 4 × 5 lahko pobarvamo nekaj kvadratkov tako, da bo v vsakem stolpcu in v vsaki vrstici pobarvanih liho število kvadratkov?
Recimo, da lahko. Preštejmo pobarvane kvadratke na dva načina. Če štejemo po stolpcih, seštejemo štiri liha števila, rezultat pa je sodo število. Če pa štejemo po vrsticah, seštejemo pet lihih števil, rezultat pa je liho število. Torej, v mreži 4 × 5 ne moremo pobarvati nekaj
8
kvadratkov tako, da bo v vsakem stolpcu in v vsaki vrstici pobarvanih liho število kvadratkov. (Juhász, 2017)
■ Skozi naslednji primer kombinatoričnega dokaza pa si bomo pogledali tehniko, ki jo bomo uporabljali za dokazovanje v nadaljevanju diplomske naloge. Dokazali bomo identiteto
∑ = 2 . Namesto uporabe formule = !( ! )! , bomo interpretirali kot število podmnožic z močjo , množice z močjo . Za lažjo predstavo bomo to prevedli na naslednji problem. Na koliko načinov lahko iz razreda izberemo skupino učencev, če je v razredu učencev? Na naše vprašanje bomo odgovorili na dva različna načina, prvi bo predstavljal levo, drugi pa desno stran identitete.
Leva stran: Število skupin z 0 učenci je 0 , število skupin z enim učencem je enako 1 . V splošnem je število skupin z natančno učenci enako , torej skupino učencev lahko iz razreda z učenci izberemo na natanko ∑ načinov.
Desna stran: Za kreiranje skupine poljubne velikosti se za posameznega učenca odločamo ali bo v skupini ali ne bo v skupini. Za vsakega učenca torej izbiramo med dvema možnima stanjema, kar pomeni, da obstaja 2 načinov za kreiranje skupine.
Ker oba odgovora predstavljata rešitev istega vprašanja, morata biti enaka. S tem smo dokazali identiteto ∑ = 2 . (Benjamin in Quinn, 2003)
■
9
3. FIBONACCIJEVA ŠTEVILA
Fibonaccijeva števila so dobila ime po italijanskem matematiku Leonardu Pisanu, čigar psevdonim je Fibonacci. Definirana so z začetnima členoma = 0, = 1, za ≥ 2 pa velja rekurzivna zveza = + . Prvih nekaj števil v Fibonaccijem zaporedju je 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … (Benjamin in Quinn, 2003) Omeniti velja, da so ta števila preučevali Hemachandra in drugi indijski matematiki že pred Fibonaccijem, zato so le-ta znana tudi pod imenom Hemachandrejeva števila. (Roberts, 2016)
3. 1. Kombinatorična interpretacija Fibonaccijevih števil
Znano je (glej Benjamin in Quinn, 2003), da lahko Fibonaccijeva števila lahko opišemo tudi kombinatorično na različne načine, na primer kot binarne −terke brez zaporednih ničel, kot podmnožice množice naravnih števil, ki ne vsebujejo dveh zaporednih naravnih števil ali kot število zaporedij enic in dvojk, ki se seštejejo v . Za zgled si oglejmo, kako na ta način dobimo Fibonaccijevo število = 8:
1 + 1 + 1 + 1 + 1 1 + 1 + 1 + 2 1 + 1 + 2 + 1 1 + 2 + 1 + 1
2 + 1 + 1 + 1 1 + 2 + 2 2 + 2 + 1 2 + 1 + 2 (Benjamin in Quinn, 2003)
V našem delu pa bomo Fibonaccijeva števila največkrat interpretirali kot število različnih tlakovanj, zato zapišimo definicijo ter ustrezno trditev z dokazom.
Definicija: Naj = 1 šteje prazno tlakovanje deske dolžine 0 in naj bo = 0.
Trditev 1: Naj šteje načine tlakovanja deske, velikosti × 1, s kvadrati velikosti 1 × 1 in z dominami velikosti 2 × 1. Potem je Fibonaccijevo število. Natančneje, za ≥ 1 velja:
= . Poglejmo si tlakovanja, ki jih dobimo za = 8.
10
Slika 3: Tlakovanja za = 8
Dokaz: Zaporedje lahko opišemo tako z enicami in dvojkami, ki se seštejejo v , kot tudi s kvadrati in z dominami. Opisa sta enakovredna, saj enice ponazorimo s kvadrati velikosti 1 × 1, dvojke pa z dominami velikosti 2 × 1, pri tem nas zanima število načinov tlakovanja deske velikosti × 1 s kvadrati in z dominami.
Opazimo, da se zaporedje začne kot zaporedje Fibonaccijevih števil, pravzaprav se izkaže, da narašča kot Fibonaccijevo zaporedje, tj. za ≥ 2 velja = + . Da enakost res velja, lahko pokažemo s kombinatoričnim dokazom. Premislimo na koliko načinov lahko dokončamo zaporedje glede na to, s katerim številom zaporedje začnemo.
Če je prvo število v zaporedju število 1, se preostalo zaporedje sešteje v − 1, kar pomeni, da obstaja načinov za dokončanje zaporedja. Če pa je prvo število v zaporedju število 2, se preostalo zaporedje sešteje v − 2, torej obstaja načinov za dopolnitev zaporedja. Sledi = + , pri čemer smo začetne vrednosti izbrali tako, da je =
in = . (Benjamin in Quinn, 2003)
■
3. 2. Posplošitve Fibonaccijevih števil
Lucasova števila so definirana z začetnima pogojema = 2, = 1, za ≥ 2 pa velja rekurzivna zveza = + . Prvih nekaj števil v zaporedju Lucasovih števil je 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, … Gibonaccijeva števila pa so posplošitev Fibonaccijevih in Lucasovih števil. Zaporedje nenegativnih števil , , , … je Gibonaccijevo zaporedje, če za vse ≥ 2 velja rekurzivna zveza = + . Fibonaccijevo zaporedje je torej Gibonaccijevo z začetnima pogojema = 0 in = 1,
11
Lucasovo zaporedje pa Gibonaccijevo z začetnima pogojema = 2 in = 1. (Benjamin in Quinn, 2003)
3. 2. 1. Kombinatorična interpretacija Lucasovih števil
Naj bo število načinov za tlakovanje krožne deske, razdeljene na označenih celic, ki jih bomo imenovali ukrivljeni kvadrati in domine. Obstaja več načinov za tlakovanje krožne deske dolžine (oziroma razdeljene na celic) v primerjavi s številom načinov tlakovanja ravne deske, dolžine , saj lahko domina v prvem primeru pokriva tudi celici in 1 hkrati. Za primer si poglejmo vsa možna tlakovanja krožne deske dolžine 4.
Slika 4: Vsa možna tlakovanja krožne deske dolžine 4
Kot vidimo iz primera, je = 7. Definirajmo -zapestnico kot tlakovanje krožne deske, dolžine . Rekli bomo, da je zapestnica izven faze, ko ena domina pokriva celici in 1 ter v fazi sicer. Na sliki 4 lahko vidimo, da je v fazi pet 4-zapestnic, izven faze pa dve 4- zapestnici. Poglejmo si število -zapestnic za majhne .
1 2 3 4
1 11
2 (2)
111 12 21 (2)1
1111 211 121 112 (2)11
12
22 (2)2
= = = =
V tabeli so prikazani načini tlakovanj -zapestnice oziroma vse različne − zapestnice, pri tem (2) ponazarja, da domina pokriva celici in 1, torej je ustrezna zapestnica izven faze. Opazimo, da 2-zapestnico lahko z eno domino izdelamo na dva načina, in sicer tako, da je 2-zapestnica bodisi v fazi bodisi izven nje. Za majhne tako razberemo, da števila
− zapestnic ustrezajo ravno Lucasovim številom . To pa velja tudi nasploh.
(Benjamin in Quinn, 2003)
Definicija: Naj bo = 2 in to interpretirajmo, da obstajata dve prazni tlakovanji krožne deske dolžine 0, in sicer 0-zapestnica v fazi ter 0-zapestnica izven faze.
Trditev 2: Naj , za vsak ≥ 0, šteje načine tlakovanja krožne deske dolžine s kvadrati in z dominami. Potem je -to Lucasovo število, to je
= .
Dokaz: Trdimo, da za ≥ 2 velja = + . Da bi to trditev dokazali, postavimo pogoj na zadnjo ploščico zapestnice. Definirajmo, da prva ploščica pokriva celico 1, kar je lahko kvadrat, domina, ki pokriva celici 1 in 2 ali pa domina, ki pokriva celici in 1. Druga ploščica je naslednja ploščica v smeri urinega kazalca, zadnja pa leži pred prvo ploščico.
Ker prva ploščica določa ali je tlakovanje v fazi ali izven nje, odstranitev zadnje ploščice ne vpliva na fazo, zato obstaja -zapestnic, ki se končajo s kvadratom in - zapestnic, ki se končajo z domino. Z odstranitvijo zadnje ploščice in zapiranjem nastale vrzeli, tvorimo manjše zapestnice. (Benjamin in Quinn, 2003)
■ 3. 2. 2. Kombinatorična interpretacija Gibonaccijevih števil
Za kombinatorično interpretacijo Gibonaccijevih števil bomo izhajali iz kombinatorične interpretacije Lucasovih števil. Trditev 2 nam pove, da šteje število načinov tlakovanja -zapestnice s kvadrati in z dominami. Opazimo, da -zapestnico lahko iztegnemo tako, da se -tlakovanje začne s prvo ploščico, to je ploščica, ki pokriva celico 1. Če je prva ploščica domina, moramo dodatno označiti še, ali je domina v fazi ali izven nje. Za zgled
13
vzemimo sedem 4-zapestnic iz slike 4. Če zapestnice iztegnemo in označimo na opisani način, dobimo tlakovanja, ki jim bomo rekli fazna − tlakovanja.
Slika 5: Fazna 4-tlakovanja
Če povzamemo, šteje število faznih -tlakovanj, kjer ima začetna domina dve možni fazi, in sicer je bodisi v fazi bodisi izven nje, začetni kvadrat pa ima le eno možno fazo – vedno je v fazi. To si lahko predstavljamo tudi tako, da imamo za začetno domino 2 možni barvi, za začetni kvadrat pa le eno.
Definicija: Naj bo število faznih 0-tlakovanj enako , torej številu možnih faz domine.
Trditev 3: Naj bo , , , … Gibonaccijevo zaporedje nenegativnih celih števil. Potem , za ≥ 1, šteje število -tlakovanj, pri čemer je začetni ploščici dodeljena faza, tako da obstaja izbir za fazo domine in izbir za fazo kvadrata.
Za kombinatorično interpretacijo posplošenih Fibonaccijevih števil torej gledamo koliko faznih − tlakovanj obstaja, pri čemer tlakujemo desko dolžine s kvadrati in z dominami, kjer se prva ploščica na nek način razlikuje od drugih, recimo po barvi. Če je prva ploščica domina, ji lahko pripišemo eno od faz oziroma barv, če pa je prva ploščica kvadrat, ji pripišemo eno od faz. Poglejmo si primer. Recimo, da za začetna pogoja vzamemo = 2 in = 3. Po rekurzivni formuli bo = 8. Preštejmo vsa tlakovanja dolžine 3, pri katerih je začetna domina lahko dveh barv (recimo rdeča ali zelena), začetni kvadrat treh barv (recimo rdeč, zelen ali moder), ostale ploščice pa so vselej sive. Na spodnji sliki lahko vidimo, da je vseh takih tlakovanj dolžine 3 res osem.
14
Slika 6: Vsa tlakovanja dolžine 3 pri začetnih pogojih = 2, = 3
Dokaz: Naj označuje število faznih -tlakovanj z oziroma faz za začetne domine oziroma kvadrate. Torej, = . Fazno 2-tlakovanje je sestavljeno bodisi iz fazne domine ( izbir) bodisi iz faznega kvadrata, temu pa sledi nefazni kvadrat ( izbir).
Torej, = + = . Želimo dokazati, da narašča kot Gibonaccijeva števila, zato postavimo pogoj na zadnjo ploščico. To nam da = + . (Benjamin in Quinn, 2003)
■
15
4. FIBONACCIJEVE IDENTITETE IN NJIHOVI KOMBINATORIČNI DOKAZI
Znanih je veliko Fibonaccijevih identitet, ki so bile prvotno običajno dokazane z indukcijo ali algebrskimi metodami. Nekatere Fibonaccijeve identitete pa lahko dokažemo tudi z metodo dvojnega štetja, ki pogosto bolje ilustrira kombinatorično vsebino dokazane enakosti, zato so tovrstni dokazi bolj zanimivi in privlačni. (Benjamin in Quinn, 2003)
4. 1. Identiteta 1
Za ≥ 0 velja:
+ + + ⋯ + = − 1.
Dokaz: Za kombinatorični dokaz te identitete se bomo vprašali, koliko tlakovanj deske dolžine + 2 vsebuje vsaj eno domino?
Desna stran: Po definiciji obstaja tlakovanj deske dolžine + 2. Če odštejemo tlakovanje, ki je sestavljeno iz samih kvadratov, dobimo − 1 tlakovanj, ki so sestavljeni iz vsaj ene domine.
Leva stran: V tem primeru bomo postavili pogoj na lokacijo zadnje domine. Recimo, da zadnja domina pokriva celici + 1 in + 2. Torej, so celice 1 do po definiciji lahko tlakovane na načinov, celici + 1 in + 2 sta prekriti z domino, celice + 3 do pa morajo biti prekrite s kvadrati. Če zadnja domina pokriva celici + 1 in + 2, obstaja torej tlakovanj. Če zadnja domina pokriva celici in + 1, obstaja tlakovanj. Tako pogledamo vse možne postavitve zadnje domine. Dobimo, da obstaja + + + ⋯ +
(= ∑ ) tlakovanj deske dolžine + 2, ki vsebujejo vsaj eno domino. (Benjamin in Quinn, 2003)
■
4. 2. Identiteta 2
Za ≥ 0 velja:
+ + + ⋯ + = .
Dokaz: V tem primeru nas bo zanimalo, koliko tlakovanj deske dolžine 2 + 1 obstaja.
Desna stran: Desna stran identitete sledi iz definicije.
16
Leva stran: Da bomo dobili levo stran identitete bomo postavili pogoj na lokacijo zadnjega kvadrata. Ker je deska lihe dolžine, mora biti tlakovanje sestavljeno iz vsaj enega kvadrata, le-ta pa mora pokrivati liho celico, saj kvadratu sledijo same domine, za kar potrebujemo sodo število celic. Recimo, da zadnji kvadrat pokriva celico 2 + 1, torej so celice 1 do 2 lahko tlakovane na načinov. Podobno kot pri prejšnji identiteti pogledamo vse možne postavitev zadnjega kvadrata, pri tem pa upoštevamo, da bo zadnji kvadrat vedno pokrival liho celico. Iz tega sledi, da obstaja + + + ⋯ + tlakovanj deske dolžine 2 + 1. (Benjamin in Quinn, 2003)
■
4. 3. Identiteta 3
Za ≥ 1 velja:
+ + + ⋯ + = − 1.
Dokaz: Postavimo si vprašanje, na katerega bomo odgovorili z levo in desno stranjo identitete. Zanima nas koliko je tlakovanj deske dolžine 2 , sestavljenih iz vsaj enega kvadrata.
Desna stran: Po definiciji obstaja tlakovanj deske dolžine 2 . Če odštejemo tlakovanje, ki je sestavljeno iz samih domin, dobimo − 1 ustreznih tlakovanj.
Leva stran: Poglejmo si kaj dobimo, če postavimo pogoj na zadnji kvadrat. Ker je deska sode dolžine, bo moral zadnji kvadrat pokrivati sodo celico, saj bodo celice za zadnjim kvadratom pokrivale domine, torej mora ostati prostih sodo število celic. Recimo, da zadnji kvadrat pokriva celico 2 , torej je za celice 1 do 2 − 1 po definiciji možnih tlakovanj. Če torej zadnji kvadrat pokriva celico 2 , je možnih tlakovanj, če pokriva celico 2 − 2, je možnih tlakovanj,… Sledi, da je skupaj možnih + +
+ ⋯ + tlakovanj. (Benjamin in Quinn, 2003)
■
4. 4. Identiteta 4
Za , ≥ 0 velja:
= + .
Preden se lotimo dokazovanja identitete, si poglejmo pojem lomljivosti. Rečemo, da je tlakovanje deske dolžine lomljivo pri celici , če tlakovanje lahko ločimo na dve tlakovanji – prvo pokriva celice 1 do , drugo pa celice + 1 do . Tlakovanju rečemo
17
nelomljivo pri celici , če domina zaseda celici in + 1. Tlakovanje deske dolžine n, je vedno lomljivo pri celici .
Dokaz: Lotimo se dokazovanja identitete, zanima nas na koliko načinov lahko tlakujemo desko dolžine + .
Leva stran: Po definiciji obstaja tlakovanj.
Desna stran: Za drugi del kombinatoričnega dokaza bomo postavili pogoj na lomljivost v celici . Tlakovanje dolžine + , ki je lomljivo v celici , je sestavljeno iz tlakovanja dolžine , sledi pa mu tlakovanje dolžine . Takih tlakovanj je .
Slika 7: Lomljivost tlakovanja dolžine +
Poglejmo si še koliko je tlakovanj, ki so nelomljiva v celici . Če tlakovanje dolžine + ni lomljivo v celici , mora celici in + 1 pokrivati domina. Tako tlakovanje je torej sestavljeno iz tlakovanja dolžin − 1, le-temu sledi domina, nato pa tlakovanje dolžine
− 1. Takih tlakovanj je torej . Ker je tlakovanje bodisi lomljivo bodisi nelomljivo v celici , obstaja + tlakovanj dolžine + . (Benjamin in Quinn, 2003)
■ Poglejmo si poseben primer identitete 4, kjer je = = + 1.
4. 5. Identiteta 5
Za ≥ 0 velja:
+ = .
Dokaz: Postavimo si vprašanje, koliko tlakovanj deske dolžine 2 + 2 obstaja.
18
Desna stran: Desna stran identitete sledi iz definicije.
Leva stran: Preštejmo število načinov tlakovanja deske dolžine 2 + 2, če postavimo pogoj na lomljivost v celici + 1. Če je tlakovanje lomljivo v celici + 1, potem je sestavljeno iz tlakovanja dolžine + 1, sledi pa mu tlakovanje enake dolžine. Takih tlakovanj je torej
= . Če pa je tlakovanje v celici + 1 nelomljivo, potem je sestavljeno iz dveh tlakovanj dolžine . Takih tlakovanj pa je = . Ker je tlakovanje bodisi lomljivo bodisi nelomljivo, je vseh tlakovanj deske dolžine 2 + 2 natanko + . (Benjamin in Quinn, 2003)
■ Dosedanje identitete bi zlahka dokazali tudi z indukcijo. Pri naslednji in nekaterih kasnejših identitetah pa bi se dokaz z indukcijo precej zakompliciral, medtem ko je dokaz z dvojnim preštevanjem čist in eleganten.
4. 6. Identiteta 6
Za ≥ 0 velja:
0 + − 1
1 + − 2
2 + ⋯ = .
Leva stran identitete vsebuje binomske koeficiente. Binomski koeficient šteje število načinov izbora elementov iz nabora elementov, pri čemer je = 0, če > . Torej je zgornja vsota v identiteti končna.
Dokaz: Pri dokazovanju te identitete bomo iskali število načinov za tlakovanje deske dolžine .
Desna stran: Po definiciji obstaja tlakovanj deske dolžine .
Leva stran: Poglejmo si, kaj dobimo, če postavimo pogoj na število domin, ki sestavljajo tlakovanje deske dolžine . Zanima nas, koliko tlakovanj deske dolžine sestavlja natanko domin. Za število različno od 0, mora veljati 0 ≤ ≤ , saj domina zavzame dve celici.
Taka tlakovanja so nujno sestavljena iz − 2 kvadratov, vseh ploščic pa je − 2 + =
− . Obstaja torej − načinov izbora domin izmed − ploščic. Če tlakovanje ne vsebuje nobene domine obstaja 0 načinov izbora, če vsebuje 1 domino, obstaja − 1
1
19
načinov izbora. Nadaljujemo za vse 0 ≤ ≤ . Dobimo, da obstaja 0 + − 1
1 +
− 2
2 + ⋯ tlakovanj deske dolžine . (Benjamin in Quinn, 2003)
■
4. 7. Identiteta 7
Za ≥ 0 velja:
− − = .
Dokaz: Vprašajmo se koliko tlakovanj deske dolžine 2 + 1 obstaja?
Desna stran: Po definiciji obstaja takih tlakovanj.
Leva stran: Tokrat bomo postavili pogoj na število domin, ki ležijo na vsaki strani sredinskega kvadrata. Vsako tlakovanje deske dolžine 2 + 1 mora vsebovati liho število kvadratov. Kvadratu, ki ima na levi in desni strani enako število kvadratov, rečemo sredinski kvadrat.
Slika 8: Sredinski kvadrat
Zanima nas koliko tlakovanj vsebuje natanko domin na levi strani sredinskega kvadrata in natanko domin na desni strani sredinskega kvadrata. Tako tlakovanje ima + domin in posledično 2 + 1 − 2( + ) kvadratov. Sredinski kvadrat ima torej − + kvadratov na vsaki strani. Levo stran tlakovanja glede na sredinski kvadrat sestavlja ( − + ) + = − ploščic. Torej, obstaja − načinov tlakovanja leve strani.
Podobno, desno stran tlakovanja glede na sredinski kvadrat sestavlja − ploščic, torej obstaja −
načinov tlakovanja desne strani sredinskega kvadrata. Leva in desna stran
20
sta neodvisni, zato skupno obstaja − − tlakovanj. Ker pa sta in različna, velja ∑ ∑ − − . (Benjamin in Quinn, 2003)
■ Poglejmo si, kako na ta način za = 2 dobimo število kot vsoto ustreznih binomskih simbolov:
= 2 − 2 − .
Sledi
= 2 − 0
0 2 − 0
0 + 2 − 0
1 2 − 1
0 + 2 − 0
2 2 − 2
0 + 2 − 1
0 2 − 0 1 + 2 − 11 2 − 1
1 + 2 − 20 2 − 0
2 = 1 + 2 + 1 + 2 + 1 + 1 = 8.
Razmislimo še, katera tlakovanja ustrezajo posameznim členom v vsoti. Kvadrate bomo označili s , domine pa z .
Člen v vsoti Ustrezna tlakovanja
2 − 0
0 2 − 0 0 2 − 0
1 2 − 1 0 2 − 0
2 2 − 2 0 2 − 1
0 2 − 0 1 2 − 1
1 2 − 1 1 2 − 2
0 2 − 0 2
4. 8. Identiteta 8
Za ≥ 0 velja:
21
= .
Dokaz: Po trditvi 1 velja = . Identiteto lahko preoblikujemo:
= .
Dokazovali bomo preoblikovano identiteto. Postavimo si vprašanje, in sicer nas zanima koliko tlakovanj dolžine 2 − 1 obstaja.
Desna stran: Desna stran sledi po definiciji.
Leva stran: Leva stran identitete šteje isto množico tlakovanj dolžine 2 − 1, in sicer štejemo tlakovanja glede na število kvadratov, ki se pojavijo med prvimi ploščicami. Pri tem upoštevamo, da mora vsako tlakovanje dolžine 2 − 1 vsebovati vsaj ploščic.
Želimo ustvariti tlakovanje deske dolžine 2 − 1, ki med prvimi ploščicami vsebuje kvadratov in − domin. Najprej izberemo, katere izmed prvih ploščic bodo kvadrati, to lahko naredimo na načinov. Teh ploščic ima dolžino + 2( − ) = 2 − . Preostala deska pa ima dolžino (2 − 1) − (2 − ) = − 1. Torej je po definiciji lahko tlakovana na načinov. Če tlakovanja združimo skupaj v eno samo in seštejemo tlakovanja glede na vrednosti , obstaja ∑ tlakovanj deske dolžine 2 − 1.
(Benjamin, Eustis in Plott, 2008)
■
4. 9. Identiteta 9
Za ≥ 0 velja:
+ + 2 = 2 .
Dokaz: Pri dokazovanju te identitete nas bo zanimalo, koliko binarnih zaporedij dolžine obstaja. Za neko tlakovanje, dolžine , bomo ustvarili binarno zaporedje dolžine , in sicer tako, da bomo vsak kvadrat pretvorili v »1«, vsako domino pa v »01«. Nastalo binarno zaporedje ne bo imelo zaporednih ničel, poleg tega pa se bo vedno končalo z 1. Če gledamo poljubno binarno zaporedje, dolžine , ki ne vsebuje zaporednih ničel in se konča z 1, potem to binarno zaporedje predstavlja natanko eno tlakovanje. Če se tako zaporedje konča
22
z 0, potem predstavlja tlakovanje dolžine − 1. Sedaj si poglejmo odgovora na naše vprašanje.
Desna stran: Binarnih zaporedij dolžine je po definiciji 2 .
Leva stran: Za vsako binarno zaporedje lahko poiščemo eno ali več ustreznih tlakovanj. Če zaporedje nima zaporednih ničel, mu pripada enolično določeno tlakovanje dolžine ali
− 1, odvisno ali se konča z 1 ali z 0. To nam da + binarnih zaporedij. Če pa zaporedje vsebuje 00, ki se prvič pojavi v celicah + 1 in + 2 za nek , 0 ≤ ≤ − 2, potem vzamemo prvih členov zaporedja in tvorimo pripadajoče enolično določeno tlakovanje dolžine . Poglejmo si primer. Recimo, da iščemo tlakovanje dolžine 10, binarnega zaporedja 1011100101. Binarno zaporedje vsebuje zaporedni ničli v celicah 6 in 7. Torej mu lahko priredimo tlakovanje, dolžine 5, ki predstavlja kvadrat-domino- kvadrat-kvadrat. Tako tlakovanje pa bi dobili iz vsakega binarnega zaporedja oblike 1011100 , kjer so , , lahko bodisi 0 bodisi 1. Opisano tlakovanje dolžine 5 lahko generirano iz osmih različnih binarnih zaporedij dolžine 10, pri čemer pa se vsa ta zaporedja začnejo z 1011100. Poglejmo si katera so ta binarna zaporedja:
1011100000 1011100001 1011100010 1011100011
1011100100 1011100101 1011100110 1011100111
Torej je v splošnem za 0 ≤ ≤ − 2, vsako tlakovanje dolžine , šteto 2 -krat. Za tlakovanje dolžine , je možnih tlakovanj, temu tlakovanju sledi 00, preostali členi, ki so bodisi 0 bodisi 1, pa dajo 2 možnosti za tlakovanje. Skupno obstaja torej +
+ ∑ 2 binarnih zaporedij dolžine . (Benjamin in Quinn, 2003)
■
Zadnje tri identitete v tem poglavju so posebej zanimive, saj predstavljajo razmeroma nove rezultate. Medtem, ko so kombinatorični dokazi prej naštetih Fibonaccijevih identitet večinoma že dolgo znani in del matematične tradicije, so kombinatorične dokaze teh identitet objavili šele leta 2008 avtorji Benjamin, Eustis in Piott.
23
4. 10. Identiteta 10
Za ≥ 0 velja:
= 2 .
Dokaz: Naj bo množica tlakovanj dolžine 2 − 1, kjer vsaki izmed prvih ploščic priredimo barvo – črno ali belo. Zanima nas koliko je takšnih tlakovanj.
Desna stran: Moč množice je tako 2 , kar je ravno desna stran identitete.
Leva stran: Da bomo dobili levo stran identitete generiramo tlakovanja tako, da najprej izberemo − izmed prvih ploščic, ki bodo bele domine. To lahko naredimo na načinov. Nato pa moramo uporabiti še tlakovanje dolžine 3 − 1, tako da določimo preostalo tlakovanje dolžine 2 − 1. Naj bo poljubno (nebarvno) tlakovanje dolžine 3 − 1. Uporabili bomo , tako da bomo določili preostalo tlakovanje, končni rezultat pa bo tlakovanje dolžine 2 − 1. Postopek je sledeč: je dolžine 3 − 1, zato poiščemo prvih blokov v . Blok je dolžine 2, če je sestavljen iz dveh kvadratov ali ene domine oziroma dolžine 3, če je sestavljen iz kvadrata in domine, v tem vrstnem redu. Poglejmo si primer:
za lažjo predstavljivost, bomo kvadrat označili s , domino pa z . Naj bo = 4, potem so prvi štirje bloki tlakovanja dolžine 11, ki je sestavljeno iz : , , , . Preostalim ploščicam tlakovanja rečemo rep. V našem primeru bi bil rep . Opazimo, da bo tlakovanje, dolžine 3 − 1 vedno imel vsaj blokov, rep pa je lahko tudi prazen. Če označimo te bloke s števili od 1 do , potem lahko teh blokov preslikamo v barvnih ploščic, ki pa niso bele domine, saj smo te določili že zgoraj. Natančneje, vsak blok sestavljen iz dveh kvadratov preslikamo v bel kvadrat, vsak blok sestavljen iz domine preslikamo v črn kvadrat, blok dolžine 3 pa preslikamo v črno domino. Rep ostane enak in predstavlja nebarven del tlakovanja. Preslikane dele sestavimo, dodamo rep, nato pa na izbrana mesta dodamo še bele domine. Poglejmo si primer. Naj bo = 7 in = 4. Sestaviti želimo tlakovanje dolžine 2 − 1 = 14 − 1 = 13. Tlakovanje dolžine 3 − 1 pa naj bo tako kot zgoraj, torej .
Slika 9: Tlakovanje dolžine 3 − 1 (Benjamin idr., 2008: 3)
24
To tlakovanje razdelimo na štiri bloke in jih preslikamo v bel kvadrat, črn kvadrat, črno domino ter črn kvadrat. Ostane še rep, ki je sestavljen iz dveh kvadratov.
Slika 10: Tlakovanje razdelimo na bloke (Benjamin idr., 2008: 3)
Ko to spojimo, dobimo barvno tlakovanje, kot je prikazano na sliki 11.
Slika 11: Dobljeno barvno tlakovanje (Benjamin idr., 2008: 3)
Da dobimo končno tlakovanje dolžine 2 − 1, moramo vstaviti še domine na prej izbrana mesta. Pa recimo, da smo izbrali, da bodo bele domine na mestih 1, 4 in 5. Dobimo tlakovanje, ki je prikazano na spodnji sliki.
Slika 12: Tlakovanje dolžine 2 − 1 (Benjamin idr., 2008: 4)
Opazimo, da se dolžina vsakega bloka skrči za ena, ko ga preslikamo v barvno ploščico.
Torej, če ima dolžino 3 − 1, se preslika v ( ) dolžine 2 − 1. Ko dodamo − belih domin, dosežemo, da je naše tlakovanje dolžine (2 − 1) + 2( − ) = 2 − 1, kot smo želeli. To preslikavo lahko tudi obrnemo, in sicer tako, da izberemo element iz množice , si zapomnimo pozicije belih domin, nato pa pretvorimo preostalih barvnih ploščic v bloke, tako da ustvarimo tlakovanje . (Benjamin idr., 2008)
■
4. 11. Identiteta 11
Za ≥ 0 velja:
2 = 5 .
Dokaz: Dokaz te identitete bomo izpeljali tako, da bomo definirali dve množici, poiskali bijektivno preslikavo med njima in s tem dokazali, da imata množici enako moč. Naj bo množica tlakovanj dolžine 2 , kjer vsaki izmed prvih ploščic priredimo eno od petih
25
barv. Število takih tlakovanj je očitno 5 , kar je ravno desna stran naše identitete.
Definirajmo še množico , katero sestavljajo tlakovanja dolžine 4 , dominam izmed prvih 2 ploščic pa priredimo eno izmed dveh barv – črno ali belo. Tlakovanje iz množice konstruiramo tako, da najprej za nek 0 ≤ ≤ 2 , izberemo 2 − izmed prvih 2 ploščic, ki bodo črne domine. To lahko naredimo na 2 načinov. Preostane nam še nebarvno tlakovanje dolžine 4 − 2(2 − ) = 2 , ki ga lahko tlakujemo na načinov – tlakujemo s kvadrati in z belimi dominami. Dobljeno seštejemo po vseh možnih vrednostih , kar nam da moč množice , to pa je ravno leva stran naše identitete. Ker tokrat nismo preštevali elementov iste množice na dva različna načina, moramo poiskati še bijektivno preslikavo med množicama in , s čimer bomo pokazali, da imata množici res enako moč.
Naj bo ∈ tlakovanje dolžine 4 . Označimo prvih 2 ploščic kot barven del tlakovanja , preostali del pa kot rep tlakovanja . Opazimo, da je dolžina repa enaka številu kvadratov med prvimi 2 ploščicami tlakovanja , saj tlakovanje sestavlja 2 − črnih domin, preostalo tlakovanje je dolžine 2 , barvni del pa sestavlja še dodatnih ploščic.
Poglejmo si tabelo, ki prikazuje kakšno je lahko preostalo tlakovanje, kaj poleg črnih domin sestavlja še barvni del, iz česa je sestavljen rep in kolikšna je dolžina repa. Iz tabele je razvidno, da je dolžina repa res enaka številu kvadratov med prvimi 2 ploščicami tlakovanja .
Možno tlakovanje Barvni del (poleg
črnih domin) Rep Dolžina repa
2 kvadratov kvadratov kvadratov
2 − 2 kvadratov in 1 bela domina
kvadratov − 2 kvadratov in
1 bela domina − 2 + 2 ∙ 1 =
− 1 kvadratov in
1 bela domina − 1 kvadratov − 1
2 − 4 kvadratov in 2 beli domini
kvadratov − 4 kvadratov +
2 beli domini − 4 + 2 ∙ 2 =
− 1 kvadratov in 1 bela domina
− 3 kvadratov in 1 bela domina
− 3 + 1 ∙ 2 =
− 1
26
− 2 kvadratov in
2 beli domini − 2 kvadratov − 2
⋮ ⋮ ⋮ ⋮
2 kvadrata in − 1 belih domin
2 kvadratov in −
2 belih domin 1 domina 2 ∙ 1 = 2 1 kvadrat in − 1
belih domin 1 kvadrat 1
domin domin / 0
Uporabili bomo prvih parov ploščic za določitev barvnih ploščic tlakovanja dolžine 2 iz množice . Preostale ploščice repa tlakovanja, se bodo preslikale same vase. Natančneje, pari ploščic dolžine 3 se bodo preslikali v barvne kvadrate, pari ploščic dolžine 4 pa se bodo preslikali v barvne domine. Kam se preslika posamezna kombinacija parov, prikazuje slika 13.
Slika 13: Preslikava parov v barvne ploščice (Benjamin idr., 2008: 7)
Manjka nam še par, ki ga sestavljata dva kvadrata. Ta se bo preslikal v ploščico barve 5.
Razmisliti moramo, ali bo ta ploščica domina ali kvadrat. Za začetek ilustrirajmo našo preslikavo, ko v tlakovanju ni nobenega para, sestavljenega iz dveh kvadratov. Za = 3 imamo tlakovanje dolžine 12, prikazano na sliki 14. Tlakovanje je sestavljeno iz 2 − = 3 črnih domin med prvimi šestimi ploščicami.
Slika 14: Tlakovanje dolžine 12 (Benjamin idr., 2008: 8)
Prvih = 3 parov preslikamo v barvne ploščice, preostale ploščice pa se preslikajo same vase, kot prikazuje slika 15. Dobimo pripadajoče tlakovanje iz množice .
27
Slika 15: Preslikava parov (Benjamin idr., 2008: 8)
Poglejmo si, kako obravnavamo tlakovanje, ki vsebuje par, sestavljen iz dveh kvadratov.
Spomnimo se, da je dolžina repa enaka številu kvadratov med prvimi 2 ploščicami. Če torej prvih 2 ploščic vsebuje blokov, sestavljenih iz dveh kvadratov, potem mora biti dolžina repa vsaj 2 , da je rep sestavljen iz najmanj ploščic. Ko torej naletimo na prvi par, sestavljen iz dveh kvadratov, pogledamo prvo ploščico, ki gradi rep. Če je ta ploščica kvadrat, z njim naš blok razširimo do dolžine 3 in ga preslikamo v kvadrat barve 5, v primeru ko je ploščica domina pa našemu bloku pripnemo domino in ga s tem razširimo do dolžine 4. Novonastali blok preslikamo v domino barve 5, kot je prikazano na sliki 16.
Slika 16: Preslikava blokov v ploščico barve 5 (Benjamin idr., 2008: 8)
V splošnem, če ima naše tlakovanje blokov, sestavljenih iz dveh kvadratov, potem je za vsak 1 ≤ ≤ −ti blok razširjen do dolžine 3 oziroma 4, glede na −to ploščico repa tlakovanja. Ostanek repa, začenši s ploščico 2 + + 1, se preslika sam vase. Vsak blok dolžine 3 oziroma 4, se preslika v barvno ploščico dolžine 1 oziroma 2. Torej bo nastalo tlakovanje dolžine 4 − 2 = 2 . Poglejmo si primer za = 3 in tlakovanje, dolžine 12, sestavljeno iz , kjer kvadrat, črna domina in bela domina, kot prikazuje slika 17.
Slika 17: Tlakovanje dolžine 12 (Benjamin idr., 2008: 9)
Prvi trije pari tlakovanja so , in . Za prvi blok vzamemo prvo ploščico repa, kar je kvadrat in ga pripnemo našemu bloku. Podobno drugemu bloku , pripnemo drugo ploščico repa, kar pa je v našem primeru domina. Dobimo bloke , in , ostane pa nam še en kvadrat. Dobljene bloke preslikamo, kot je prikazano na sliki 18.
28
Slika 18: Preslikava blokov (Benjamin idr., 2008: 9)
Ta postopek zlahka tudi obrnemo, in sicer tako, da vsako barvno ploščico deske dolžine 2 , preslikamo v ustrezni par ploščic, pri čemer upoštevamo, da se ploščica barve 5 preslika v oziroma , kjer je tretja ploščica del repa tlakovanja. Na koncu ostane še nebarvni del, ta postane ostanek repa tlakovanja, ki le-tega dopolni do dolžine 4 . (Benjamin idr., 2008)
■
4. 12. Identiteta 12
Za ≥ 0 velja:
2 = 5 .
Ta identiteta je posledica identitete 11, za dokaz lahko uporabimo enako preslikavo kot za dokaz identitete 11. S tem ko dodamo , le podaljšamo dolžino repa – del, ki ga preprosto pripnemo med samo preslikavo. (Benjamin idr., 2008)
■
29
5. LUCASOVE IN GIBONACCIJEVE IDENTITETE TER NJIHOVI KOMBINATORIČNI DOKAZI
Veliko identitet z Lucasovimi števili je podobnih Fibonaccijevim identitetam. Poleg tega obstaja tudi veliko identitet, kjer so Lucasova in Fibonaccijeva števila v interakciji.
(Benjamin in Quinn, 2003) V nadaljevanju si bomo pogledali nekatere izmed njih.
Pogledali pa so bomo tudi nekaj Gibonaccijevih identitet.
5. 1. Identiteta 13
Za ≥ 1 velja:
= + .
Dokaz: Pri dokazovanju te identitete bomo iskali število tlakovanj krožne deske, dolžine .
Leva stran: Po definiciji obstaja − zapestnic.
Desna stran: Poglejmo si kaj dobimo, če postavimo pogoj na fazo tlakovanja. Tlakovanje, ki je v fazi, lahko iztegnemo v tlakovanje dolžine . V tem primeru obstaja zapestnic, ki so v fazi. Če pa imamo −zapestnico izven faze, mora domina pokrivati celici in 1.
Celice od 2 do − 1 lahko tlakujemo kot ravno tlakovanje dolžine − 2, kar pomeni, da jo lahko tlakujemo na načinov. Ker je tlakovanje bodisi v fazi bodisi izven nje, obstaja skupaj + načinov tlakovanja. (Benjamin in Quinn, 2003)
■
5. 2. Identiteta 14
Za ≥ 2 velja:
= + 2 .
Dokaz: Tudi pri dokazovanju te identitete bomo iskali število tlakovanj krožne deske dolžine .
Leva stran: Po definiciji obstaja natanko − zapestnic.
Desna stran: Postavimo pogoj na ploščico, ki pokriva celico 1. Če celico 1 pokriva kvadrat, potem tlakovanje lahko iztegnemo in ga tlakujemo na načinov. Če pa celico 1 pokriva domina, ločimo dva primera. V primeru, ko domina pokriva celici 1 in 2, tlakovanje iztegnemo in ga tlakujemo na načinov. V primeru, ko domina pokriva celici in 1,
30
pa lahko celice od 2 do − 1 tlakujemo kot ravno tlakovanje, in sicer na načinov.
Skupaj obstaja torej + + = + 2 načinov za tlakovanje krožne deske dolžine . (Benjamin in Quinn, 2003)
■
5. 3. Identiteta 15
Za ≥ 0 velja:
5 = + .
Dokaz: Identiteto bomo dokazali s pomočjo preslikave med dvema množicama. Naj množica vsebuje tlakovanja deske dolžine . Moč množice je enaka . Množica pa naj vsebuje tlakovanja krožne deske dolžine oziroma tlakovanja krožne deske dolžine + 2. Moč množice je enaka + . Za dokaz identitete, bomo za vsako tlakovanje iz množice ustvarili pet zapestnic iz množice , in sicer tako, da bo vsaka zapestnica iz množice uporabljena natanko enkrat. S tem bomo dokazali, da je množica petkrat večja od množice . Za dano tlakovanje dolžine , štiri zapestnice ustvarimo na naslednje načine:
1. Zlepimo celici in 1, tako nastane − zapestnica v fazi.
2. Na konec vstavimo dva kvadrata in tlakovanje zlepimo, tako da nastane ( + 2) − zapestnica v fazi.
3. Na konec vstavimo domino, s čimer spet dobimo ( + 2) − zapestnico v fazi.
4. Na začetek vstavimo domino, zlepimo tako, da dobimo ( + 2) − zapestnico izven faze.
Manjkajo nam še − zapestnice izven faze ter ( + 2) − zapestnice, ki se začnejo s kvadratom in nadaljujejo z domino. Peta zapestnica, ki jo ustvarimo iz danega tlakovanja deske, dolžine je odvisna od ploščice s katero se začne dano tlakovanje. Če se tlakovanje začne z domino ustvarimo
5a. − zapestnico izven faze, tako da rotiramo zapestnico 1 za eno celico v smeri urinega kazalca.
V primeru, ko se tlakovanje začne s kvadratom, pa ustvarimo
5b. ( + 2) − zapestnico v fazi, ki se začne s kvadratom in mu sledi vstavljena domina.
(Benjamin in Quinn, 2003)
31
■
5. 4. Identiteta 16
Za ≥ 0 velja:
= − .
Dokaz: Za dokaz identitete bomo odgovarjali na vprašanje, koliko faznih tlakovanj dolžine + 2, je sestavljenih iz vsaj ene domine.
Desna stran: Po definiciji obstaja faznih tlakovanj dolžine + 2 . Le-ta pa vsebujejo tudi tista, ki so sestavljena iz samih kvadratov. Takih je . Skupaj je torej faznih tlakovanj dolžine + 2, sestavljenih iz vsaj ene domine enako − , kar je desna stran naše identitete.
Leva stran: Koliko je iskanih tlakovanj, bomo ugotavljali glede na lokacijo zadnje domine.
Za 0 ≤ ≤ , obstaja tlakovanj, pri katerih zadnja domina pokriva celici + 1 in + 2. Če zadnja domina pokriva celici 1 in 2, mora biti tlakovanje v eni izmed faz, torej naš postopek velja tudi za ta primer. Ko seštejemo po vseh možnih vrednostih , dobimo levo stran naše identitete. (Benjamin in Quinn, 2003)
■
5. 5. Identiteta 17
Za ≥ ≥ 0 velja:
= .
Dokaz: Vprašajmo se, koliko faznih tlakovanj dolžine + obstaja. Leva stran dobimo po definiciji, Desna stran pa glede na število domin, ki sestavljajo zadnjih ploščic tlakovanja.
Poglejmo si odgovora.
Leva stran: Obstaja faznih tlakovanj dolžine + , kar je leva stran identitete.
Desna stran: Če je med zadnjimi ploščicami vsebovanih domin in − kvadratov, potem te ploščice lahko razporedimo na načinov. Dolžina tlakovanja, sestavljenega iz teh ploščic je enaka 2 + ( − ) = + . Torej ima preostala deska dolžino ( + ) − ( + ) = − in jo lahko tlakujemo na načinov. Ko to seštejemo po vseh možnih vrednostih , dobimo desno stran identitete. (Benjamin in Quinn, 2003)
32
■
5. 6. Identiteta 18
Za ≥ 0 velja:
= − .
Dokaz: Pri dokazu te identitete bomo tlakovali dve deski hkrati. Pri tem si bomo pomagali tako, da bomo eno desko označili kot »zgornjo«, drugo pa kot »spodnjo« desko. Postavimo si vprašanje, in sicer nas bo zanimalo na koliko načinov lahko dve deski dolžine 2 , fazno tlakujemo tako, da bo vsak par tlakovanj zgornje in spodnje deske nekje vseboval vsaj en kvadrat. Pri tem bomo za Desna stran potrebovali pojem »napake«.
Naj bosta in dva tlakovanja dolžine . Tlakovanje tlakuje celice 1 do , tlakovanje pa celice 2 do + 1. Rečemo, da imamo »napako« v celici , za 2 ≤ ≤ , če sta oba tlakovanja lomljiva v celici . Napaka v celici 1 se pojavi, ko je prvo tlakovanje lomljivo v celici 1. Če povemo na drug način, par tlakovanj ima napako v celici , za 1 ≤ ≤ , če nobeno tlakovanje ne vsebuje domine, ki pokriva celici in + 1.
Desna stran: Vsaka deska posebej je lahko tlakovana na načinov, torej za obe skupaj obstaja načinov tlakovanja, pri čemer pa ta tlakovanja vsebujejo tudi tista, ki ne premorejo nobenega kvadrata. Takih je v obeh tlakovanjih skupaj , kar pomeni, da je odgovor na naše vprašanje enak − .
Leva stran: Naj bo zgornja deska sestavljena iz celic 1 do 2 in naj bo spodnja deska sestavljena iz celic 2 do 2 + 1. Ker iščemo par faznih tlakovanj, ki vsebuje vsaj en kvadrat, mora obstajati vsaj ena napaka. Postavimo pogoj na lokacijo zadnje napake.
Zadnja napaka se pojavi v celici , če sta oba tlakovanja lomljiva v celici in v nobeni od naslednjih celic. Če se zadnja napaka pojavi v celici ≥ 2, obstaja načinov tlakovanja zgornje deske do celice v kateri se pojavi napaka, načinov tlakovanja spodnje deske do celice v kateri se pojavi napaka in en način tlakovanja obeh desk za celice, ki desko sestavljajo po napaki. Vse ploščice desno od napake so namreč domine, razen v celici + 1 deske z liho dolžino repa. V primeru, ko je = 1 pa je število parov tlakovanj enako
. Za 1 ≤ ≤ 2 , torej obstaja parov faznih tlakovanj z zadnjo napako v celici . Ko seštejemo po vseh vrednosti , dobimo ∑ parov faznih tlakovanj z vsaj enim kvadratom. (Benjamin in Quinn, 2003)
33
■
5. 7. Identiteta 19
Za ≥ 1 velja:
+ = .
Dokaz: Tudi ta dokaz bo vseboval tlakovanja dveh desk, in sicer nas bo zanimalo na koliko načinov lahko fazno tlakujemo desko dolžine 2 in desko dolžine 2 − 1, pri čemer ima prva deska začetnih faz domine in začetnih faz kvadrata, druga deska pa začetnih faz domine ter začetnih faz kvadrata.
Desna stran: Po definiciji je takih tlakovanj .
Leva stran: Naj zgornja deska pokriva celice 1 do 2 in spodnja deska celice 1 do 2 − 1.
Postavimo pogoj na zadnjo napako, če le-ta obstaja. Prva deska je sode dolžine, zato so edina tlakovanja, ki ne vsebujejo napake tista, ki so sestavljena iz samih domin, razen enega faznega kvadrata na spodnji deski. Torej, obstaja tlakovanj brez napak. Po drugi strani pa obstaja tlakovanj, kjer se zadnja napaka pojavi v celici , kjer je 1 ≤ ≤ 2 − 1.
To dobimo na enak način kot pri identiteti 18. Če to seštejemo, obstaja + ∑ načinov za tlakovanje naših desk. (Benjamin in Quinn, 2003)
■
34
6. BINETOVE FORMULE
6. 1. Identiteta 20 (Binetova formula)
Za ≥ 0 velja:
= 1
√5
1 + √5
2 − 1 − √5 2 .
Preko Binetove formule lahko direktno izračunamo − to Fibonaccijevo število. Izpeljal jo je matematik Jacques Philippe Marie Binet leta 1843, rezultati pa so bili znani že več kot stoletje prej matematikom Euleju, Danielu Bernoulli-ju ter Abrahamu de Moivre-u.
Formulo lahko zapišemo v krajši obliki, in sicer z uporabo simbola , ki predstavlja razmerje zlatega reza. Upoštevamo, da je = √ . Zlati rez ima nekatere lastnosti, ki nam bodo pri kombinatoričnem dokazu te formule koristile. Ena izmed teh je enakost + = 1. (Benjamin in Quinn, 2003; Binet's Fibonacci Number Formula, b. d.)
Preden začnemo s kombinatoričnim dokazom pa omenimo, da lahko Binetovo formulo dokažemo tudi na druge načine. Eden izmed teh je dokaz z indukcijo, formulo pa lahko dokažemo tudi preko diagonalizacije matrike ter s pomočjo karakterističnih enačb. V nadaljevanju si bomo pogledali slednja dva dokaza.
Najprej si poglejmo dokaz Binetove formule preko diagonalizacije matrike. Začetne pogoje in rekurzivno enačbo lahko zapišemo s pomočjo matrik
= 11 ,
= 0 1
1 1 .
S pomočjo naslednje leme bomo v nadaljevanju pokazali veljavnost Binetove formule.
Lema: Za vsak ∈ ℕ velja:
= 0 1 1 1
1 1 .
Dokaz: Za dokaz bomo uporabili metodo indukcije. Preverimo, če trditev velja za = 1.
35
= 0 11 1 1 1 = 11
Sedaj privzemimo, da trditev velja za naravno število in dokažimo, da velja tudi za naravno število + 1. Dokazujemo, da velja:
= 0 11 1 1 1 .
Začnemo na levi strani enačbe in upoštevamo indukcijsko predpostavko:
= 0 11 1
= 0 11 1 0 1
1 1 1
1 = 0 11 1 1
1
□ Sedaj se lahko lotimo dokaza Binetove formule. Naj bo = 0 1
1 1 matrika, ki jo bomo v nadaljevanju diagonalizirali. Najprej poiščimo lastne vrednosti matrike :
| − | = − 1
1 1 − = − (1 − ) − 1
= − − 1 Dobimo dve rešitvi za lastne vrednosti
= 1 + √5
2 =
= 1 − √5 2 = .
Poiščimo še odgovarjajoče lastne vektorje. Za = in = :
( − ) = ( − ) = − 1
1 1 − = 00 .
36 Ko matriki množimo, dobimo sledeči sistem enačb:
− + = 0
+ (1 − ) = 0
Drugo enačbo pomnožimo z in upoštevamo, da je = 1 + oziroma − = −1, dobimo:
− = 0.
Iz novega sistema enačb izrazimo ter zapišemo vektor :
= = = 1 .
Odgovarjajoči lastni vektor za je torej 1
. Podobno poiščemo lastni vektor za , ki je 1 . Zapišimo sedaj matriko v obliki = , kjer je = 1 1
, =
−1
− 1 in = 0
0 . S pomočjo diagonalne matrike lahko enostavno izračunamo potence matrike:
= 0 1
1 1 1
1 = 1 1 0
0
1
−
−1
− 1 1
1 = 1
−
1 1 0
0
− 1
− + 1 = 1
−√5
1 1 ( − 1)
(− + 1) = − 1
√5
(− ) + ( ) (− ) + ( ) = 1
√5
−
−
Enakost zgornje vrstice v začetni in končni matriki predstavlja ravno Binetovo formulo.
(Miliyon, 2014)
37
■ Sedaj pa si poglejmo še dokaz Binetove formule s pomočjo standardne metode za reševanje linearnih rekurzij s konstantnimi koeficienti preko korenov karakteristične enačbe.
Fibonaccijevo zaporedje je definirano z rekurzivno formulo:
= + .
Formulo lahko preoblikujemo sledeče:
− − = 0.
Zgornja enačba je homogena enačba, njena karakteristična enačba pa je naslednja:
− − 1 = 0.
Dobimo dve rešitvi karakteristične enačbe, to sta
= 1 + √5 2 ,
= 1 − √5 2 . Splošno rešitev lahko zapišemo v obliki
= 1 + √5
2 + 1 − √5
2 .
V nadaljevanju bomo s pomočjo začetnih pogojev = 0 in = 1 poiskali vrednosti spremenljivk in . V splošno rešitev vstavimo = 0 ter = 1, dobimo
= 1 + √5
2 + 1 − √5
2 ,
= 1 + √5
2 + 1 − √5
2 .
Dobimo dve enačbi + = 0 in √ + √ = 1. Iz prve izrazimo = − in spremenljivko vstavimo v drugo enačbo, nato poračunamo:
1 + √5
2 − 1 − √5
2 = 1
38
1 + √5 − 1 − √5 = 2 1 + √5 − 1 + √5 = 2
= 1
√5
= − 1
√5
Vrednosti spremenljivk in vstavimo v rešitev in dobimo Binetovo formulo:
= 1
√5
1 + √5
2 − 1
√5
1 − √5 2 . (Miliyon, 2014)
■ Na tej točki si bomo pogledali še kombinatorični dokaz Binetove formule, za katerega bomo vključili tudi malo verjetnosti, in sicer bomo tlakovali neskončno desko v obliki poltraka širine 1 tako, da bomo neodvisno, eno ploščico za drugo, polagali kvadrate in domine, pri čemer bomo pri vsaki odločitvi uporabili kvadrat z verjetnostjo 1/ oziroma domino z verjetnostjo 1 − = 1/ . Verjetnost, da se tako tlakovanje začne s podanim zaporedjem kvadratov in domin dolžine , je enaka 1/ .
Upoštevajmo, da je √ = −1/ ter = in poglejmo kaj pove naša identiteta:
= 1
√5 − −1
.
Naj bo verjetnost, da je naključno tlakovanje lomljivo v celici . Ker za tlakovanje prvih celic obstaja načinov, verjetnost vsakega pa je 1/ velja:
= .
Tlakovanje, ki ni lomljivo v celici , mora biti lomljivo v celici − 1, kar se zgodi z verjetnostjo , saj celici in + 1 v tem primeru pokriva domina. Verjetnost, da pri
39
naključnem tlakovanju ti dve celici pokriva domina, je 1/ . To pomeni, da za ≥ 1, velja 1 − = / , oziroma
= 1 − ,
in je = = 1. Predpostavimo, da limita zaporedja = 1 − obstaja, potem mora limita = lim
⟶ zadoščati enačbi = 1 − / . Dobimo, da je = 1 + = /√5. V kombinaciji z = , dobimo asimptotično obliko Binetove formule, da za velike velja:
≈ √5 .
Za natančno izpeljavo Binetove formule, razvijemo vrsto, ki jo dobimo iz rekurzivne enačbe = 1 − , pri čemer upoštevamo, da je = 1:
= 1 −
= 1 − 1 −
= 1 − 1 +
= 1 − 1 +
1 −
= 1 − 1 + 1
−
⋮ Dobimo:
= −1
+ −1
+ −1
+ −1
+ ⋯ + −1 .
To je končna geometrijska vrsta oz. zaporedje, katero lahko po identiteti 1 + + + + ⋯ + = , ki velja za vsak ≠ 1 in vsako pozitivno celo število , seštejemo:
40
= 1 − 1 + 1
− 1
+ ⋯ + −1
=
1 − −1 1 − −1 . Sledi:
= 1 − 1 + 1
− 1
+ ⋯ + −1
= 1 + 1
1 − −1
.
Pri tem velja 1 + =
√ , torej se izraz za poenostavi v:
= √5 1 − −1
.
Sledi
= =
√5 1 − −1
= 1
√5 − −1
.
■ Binetovo formulo lahko poenostavimo na naslednji način. (Benjamin in Quinn, 2003) 6. 1. 1. Posledica 1
Za ≥ 0 velja, da je najbližje celo število številu
√ .
Dokaz: Posledica je ekvivalentna trditvi, da velja neenakost −
√ < . Po Binetovi formuli velja:
1
√5 − −1
− √5 < 1 2 1
√5 − −1
< 1 2 1
√5 <1 2
√5 > 2.
41
To pa je očitno res za vsak ≥ 0, saj √5 > 2 in > 1.
■ Binetova formula prikazuje, da zaporedna Fibonaccijeva števila za velike naraščajo za faktor . Bolj natančno o tem pove posledica 2. (Benjamin in Quinn, 2003)
6. 1. 2. Posledica 2 Za ≥ 0 velja:
lim→ =
Dokaz: Iz asimptotične oblike Binetove formule, z izračunom vrednosti limite , za vsak
≥ 0, dobimo:
√5= lim
→ = lim
→ .
Sledi
1 = lim
→
/
/ = lim
→ .
Torej, lim
→ = .
■ Poglejmo si še ostale posledice. (Benjamin in Quinn, 2003)
6. 1. 3. Posledica 3 Za ≥ 1 velja:
= + .
Dokaz: Posledico dobimo, če vstavimo enačbo = v enačbo = 1 − in dobljeno pomnožimo s :
= 1 −
= 1 −
42
= − .
(Benjamin in Quinn, 2003)
■ 6. 1. 4. Posledica 4
Za ≥ 1 velja
= + .
Dokaz: Posledico 4 dobimo, če v posledico 3 vstavimo = + = − + :
= −
− 1
+ = −
− + = −
= + .
(Benjamin in Quinn, 2003)
■ 6. 1. 5. Posledica 5
Za ≥ 1 velja:
− =(−1)
.
Dokaz: Po enačbi = 1 − + − + ⋯ + , dobimo
− = 1 − 1 + 1
− 1
+ ⋯ + −1
− 1 − 1 + 1
− 1
+ ⋯ + −1
