Fibonaccin luvuista ja matriiseista

TAMPEREEN YLIOPISTO Pro gradu -tutkielma

Maria Jännes

Fibonaccin luvuista ja matriiseista

Informaatiotieteiden yksikkö Matematiikka

Toukokuu 2012

Tampereen yliopisto

Informaatiotieteiden yksikkö

MARIA, JÄNNES: Fibonaccin luvuista ja matriiseista Pro gradu -tutkielma, 27 s.

Matematiikka Toukokuu 2012

Tiivistelmä

Tässä työssä tutustutaan Fibonaccin lukuihin ja matriiseihin. Fibonaccin ja Lucas’n luvut määritellään ensin rekursiivisesti, ja kultaisen leikkauksen esittelyn jälkeen johdetaan vielä molemmille eksplisiittiset, ns. Binet’n kaa- vat, joiden avulla voidaan laskea haluttu Fibonaccin tai Lucas’n luku, vaik- kei edellisiä lukuja tunneta. Tutustutaan sitten joihinkin tunnettuihin Fibo- naccin ja Lucas’n lukujen ominaisuuksiin. Pääluvussa esitellään Fibonaccin matriiseja, siis matriiseja, joiden alkioina Fibonaccin luvut esiintyvät. Fibo- naccin lukujen ja matriisien ominaisuuksia ja laskusääntöjä käyttäen johde- taan ja todistetaan lisää Fibonaccin lukujen identiteettejä. Päälähdeteokse- na on käytetty Thomas Koshyn teosta Fibonacci and Lucas numbers with applications.

Sisältö

1 Johdanto 3

2 Valmistelevia tarkasteluja 3

3 Fibonaccin luvuista 3

3.1 Fibonaccin luvut . . . 4

3.2 Lucas’n luvut . . . 5

3.3 Kultainen leikkaus . . . 6

3.4 Binet’n kaavat . . . 7

4 Fibonaccin matriiseista 10 4.1 Q-matriisi . . . 10

4.2 Cassinin lause . . . 11

4.3 M-matriisi . . . 14

4.4 Karakteristinen yhtälö ja ominaisarvot . . . 15

4.5 R-matriisi . . . 16

4.6 Cramerin lause . . . 17

4.7 Lambda-funktio . . . 19

4.8 P-matriisi . . . 20

Viitteet 27

1 Johdanto

Tässä työssä tarkastellaan Fibonaccin lukuja ja matriiseja. Päälähteenä on käytetty Thomas Koshyn teosta Fibonacci and Lucas numbers with applica- tions, jonka lukua 32 työ pääpiirteissään seuraa. Työssä tarvittavat pohja- tiedot Fibonaccin ja Lucas’n luvuista ja ominaisuuksista on koottu suurelta osin saman kirjan edeltävistä luvuista 1, 5 ja 8. Tämän tutkielman luvussa 2 esitellään lyhyesti joitakin työn kannalta oleellisia matriisien ominaisuuksia ja laskusääntöjä. Luvussa 3 määritellään Fibonaccin ja Lucas’n luvut en- sin rekursiivisesti ja kultaisen leikkauksen esittelyn jälkeen johdetaan vielä molemmille ns. Binet’n kaavat, joiden avulla voidaan laskea haluttu Fibo- naccin tai Lucas’n luku, vaikkei tunneta edellisiä lukuja. Pääluvussa esitel- lään Fibonaccin matriiseja, siis matriiseja, joiden alkioina Fibonaccin luvut esiintyvät. Fibonaccin lukujen ja matriisien ominaisuuksia ja laskusääntö- jä käyttäen johdetaan ja todistetaan lisää Fibonaccin lukujen identiteettejä.

Ensimmäisenä esitellään Q-matriisi, jonka avulla todistetaan mm. Cassinin lause. Työn edetessä saamme näin hiukan tutustua Fibonaccin ja Lucas’n lukujen moninaisiin ominaisuuksiin ja niiden yhteyksiin matriiseihin.

2 Valmistelevia tarkasteluja

Luvussa 2 esitämme lyhyesti muutamia pääaiheemme käsittelyssä tarvitse- miamme apuneuvoja. Luettelemme joitakin matriisien ominaisuuksia ja las- kusääntöjä (vrt. [3, s. 547–549]). Määrittelemme mm. matriisin ominais- arvot ja esitämme neliömatriisin karakteristista yhtälöä koskevan Cayley- Hamiltonin lauseen.

Huomautus 2.1. MatriisinA determinanttia merkitään detA=|A|.

Huomautus 2.2. Matriisin raja-arvolla tarkoitamme alkioittaista raja-arvoa.

Määritelmä 2.1. OlkoonA= (a_ij)n×n, ja olkoonI n×n-identiteettimatriisi.

Sanomme yhtälöä

|A−xI|= 0

matriisin Akarakteristiseksi yhtälöksi. Yhtälön ratkaisuja kutsumme matrii- sinA ominaisarvoiksi.

Lause 2.1 (Cayley-Hamiltonin lause). Jokainen neliömatriisi toteuttaa ka- rakteristisen yhtälönsä (ks. [3, s. 366]).

3 Fibonaccin luvuista

Luvussa 3 määrittelemme Fibonaccin ja Lucas’n lukujonot (vrt. [3, s. 6]).

Lisäksi esittelemme kultaisen leikkauksen, ja johdamme siitä Binet’n kaa-

van Fibonaccin lukujen laskemiseksi. Tähän lukuun on myös kerätty jatkon kannalta tarpeellisia Fibonaccin lukujen ominaisuuksia todistuksineen.

3.1 Fibonaccin luvut

Fibonaccin lukujono määritellään antamalla ensin alkuehto, jonka mukaan jonon ensimmäiset luvut ovat F₀ = 0 ja F₁ = 1. Jonon seuraava luku laske- taan näiden jälkeen aina kahden edellisen luvun summana.

Määritelmä 3.1. Olkoon F₀ = 0, F₁ = 1,

F_n =F_n−1+F_n−2, kunn >1.

Lukujonoa F₀, F₁, F₂, . . . , F_n, . . . sanomme Fibonaccin lukujonoksi. Sen jäse- niä sanommeFibonaccin luvuiksi.

Esimerkki 3.1. Taulukkoon 1 on laskettu Fibonaccin lukujonon ensimmäi- siä jäseniä.

Taulukko 1: Fibonaccin lukuja

n 0 1 2 3 4 5 6 7 8 9 10 F_n 0 1 1 2 3 5 8 13 21 34 55

Huomautus 3.1. Myöhemmin tarvitaan mm. seuraavia yhtälöitä, jotka voi- daan johtaa suoraan määritelmästä 3.1 sijoittamallan= 2k+1 jan = 2k+2:

F2k−1+F_2k =F_2k+1, F_2k+F_2k+1 =F_2k+2.

Määritelmän 3.1 mukaan F_n+2 = F_n+1 +F_n ja F_n+1 = F_n +F_n−1, joten F_n+2 = (F_n+Fn−1) +F_n = 2F_n+Fn−1. Kun n = 2k, saadaan tästä lisäksi tulos

F_2k+2 = 2F_2k+F2k−1, ja kun n= 2k+ 1, saadaan

F_2k+3 = 2F_2k+1+F_2k.

Luvussa 4.6 käytämme apuna tulosta, jonka mukaan kahden peräkkäisen Fibonccin luvun suurin yhteinen tekijä, syt(F_n, F_n+1) = 1. Tämän ominai- suuden voisi helposti johtaa myöhemmin esitetystä Cassinin lauseesta 4.2 ku- ten lähdeteoksessa on tehty (ks.[3, s. 75]). Koska käytämme tulosta myöhem- min nimenomaan Cassinin lauseen todistuksessa, vältämme kehäpäätelmän, kun todistamme sen tässä lähdeteoksesta poiketen.

Apulause 3.1. Olkoon syt(a, b) = 1. Tällöin syt(b, a+b) = 1.

Todistus. Oletetaan, että syt(a, b) = 1. Tehdään vastaoletus, että on olemas- sa jokin sellainen lukur >1 että syt(b, a+b) =r. Nytrjakaa siis sekä luvun b että luvun a+b, joten voimme kirjoittaa b = rc ja a+b = rd joillakin c, d∈Z. Koska a=a+b−b=rd−rc=r(d−c),r jakaa myös luvun a, ja päädymme näin ristiriitaan oletuksen kanssa. Siis syt(b, a+b) = 1.

Lause 3.2. Kahden peräkkäisen Fibonccin luvun suurin yhteinen tekijä, syt(F_n, F_n+1) = 1.

Todistus. Todistamme lauseen induktiolla. Toteamme, että väite on tosi, kun n = 0, sillä syt(F₀, F₁) = syt(0,1) = 1. Oletetaan sitten, että väite on tosi, kun n = k, siis syt(F_k, F_k+1) = 1. Nyt voimme Fibonaccin luku- jen määritelmän mukaan kirjoittaa syt(F_k+1, Fk+2) = syt(F_k+1, Fk +Fk+1).

Induktio-oletuksen perusteella syt(F_k, F_k+1) = 1 joten apulauseen 3.1 mu- kaan syt(F_k+1, F_k+F_k+1) = 1 ts. syt(F_k+1, F_k+2) = 1. Siis väite on tosi, kun n =k+ 1. Induktioperiaatteen mukaan väite on tosi aina, kun n≥0.

3.2 Lucas’n luvut

Lucas’n luvut lasketaan samoin kuin Fibonaccin luvut aina kahden edelli- sen luvun summana. Jonon ensimmäiset luvut ovat kuitenkin toiset, ja näin saadaan uusi lukujono.

Määrittelemme Lucas’n luvut lähdeteoksesta ([3, s. 8]) poiketen alkaen luvusta L₀ = 2, sillä tämä on yleisen standardin mukainen tapa.

Määritelmä 3.2. Olkoon L₀ = 2, L₁ = 1,

Ln=Ln−1+Ln−2, kun n >1.

Lukujonoa L0, L1, L2, . . . , Ln, . . . sanomme Lucas’n lukujonoksi. Sen jäseniä sanomme Lucas’n luvuiksi.

Esimerkki 3.2. Taulukkoon 2 on laskettu Lucas’n lukujonon ensimmäisiä jäseniä.

Taulukko 2: Lucas’n lukuja

n 0 1 2 3 4 5 6 7 8 9 10

L_n 2 1 3 4 7 11 18 29 47 76 123

Lause 3.3. Olkoon n ≥1. Tällöin L_n=F_n+1+F_n−1.

Todistus. Todistus on lähdeteoksessa (ks.[3, s. 80]) jätetty harjoitustehtäväk- si. Todistetaan lause induktiolla. Väite on tosi, kunn= 1, sillä 1 = 1 + 0. Siis L₁ =F₂+F₀. LisäksiL₂ =F₃+F₁, sillä 3 = 2+1. Siis väite on tosi, kunn = 2.

Teemme induktio-oletuksen, että L_k = F_k+1 +Fk−1 ja Lk−1 = F_k+Fk−2 , kun k≥2. Nyt Lucas’n lukujen määritelmän 3.2 mukaan voimme kirjoittaa

L_k+1 =L_k+Lk−1.

Induktio-oletuksen ja Fibonaccin lukujen määritelmän perusteella saamme L_k+1 =F_k+1+Fk−1+F_k+Fk−2

= (F_k+1+F_k) + (Fk−1+Fk−2)

=F_k+2+F_k

=F_(k+1)+1+F(k+1)−1.

Siis väite on tosi, kun n =k+ 1. Induktioperiaatteen mukaan L_n =F_n+1+ Fn−1 aina, kun n≥1.

3.3 Kultainen leikkaus

Kultainen leikkaus tai kultainen suhde esiintyy, samoin kuin Fibonaccin lu- vut, useissa geometrisissa kuvioissa, taiteessa ja luonnon mittasuhteissa. Kul- tainen leikkaus syntyy, kun jaamme janan kahteen osaan siten, että koko ja- nan suhde sen pitempään osaan on sama kuin pitemmän osan suhde lyhyem- pään. Kultaisen leikkauksen suhdelukua merkitään yleisesti kreikkalaisella kirjaimella φ (fii). Merkinnän sanotaan juontuvan kuuluisan kreikkalaisen kuvanveistäjän Phidias’n (490-430 eKr.) nimestä. (Vrt. [4, s. 110].)

Määritelmä 3.3. Olkoon φ luku, joka toteuttaa yhtälön 1

φ =φ−1.

Sanomme, että yhtälön positiivinen ratkaisu φ on kultainen suhde.

Voimme kirjoittaa määritelmän 3.3 yhtälön muotoon φ² −φ−1 = 0, ja saamme ratkaisut

φ= 1 +√ 5

2 tai φ= 1−√ 5 2 ,

joista vasen on positiivinen. Merkitsemme ratkaisuja jatkossa α= 1 +√

5

2 ja β = 1−√ 5 2 .

3.4 Binet’n kaavat

Suhdelukuφliittyy myös Fibonaccin lukuihin. Näiden välinen yhteys selviää, kun johdamme Fibonaccin luvuille lausekkeen, jonka avulla voimme laskea luvunF_n, vaikka emme tietäisi jonon edellisiä jäseniä. Koska tämä esitys tuo selkeyttä myös luvun 4 tarkasteluihinQ-matriisin karakteristisesta yhtälöstä (4.4) ja voimme hyödyntää sitä useiden Fibonaccin ja Lucas’n lukuja koske- vien ominaisuuksien todistuksissa, uhraamme seuraavaksi muutaman sivun asian esittelyyn.

Olkoot α ja β yhtälön x²−x−1 = 0 ratkaisut kuten edellä on todettu.

Voimme laskea, että

α+β = 1 +√

5 + 1−√ 5

2 = 1,

αβ = 1 +√ 5 2

1−√ 5

2 =−1, α−β = 1 +√

5−1 +√ 5

2 =√

5.

Lause 3.4. Olkoon n ≥1 ja α= ¹⁺

√5

2 . Tällöin αⁿ =αF_n+Fn−1.

Todistus. Todistus on lähdeteoksessa (vrt. [3, s. 78]) jätetty harjoitusteh- täväksi. Todistamme lauseen induktiolla. Väite on tosi, kun n = 1, sillä α¹ =αF₁+F₀ =α. Oletamme sitten, ettäα^k=αF_k+Fk−1. Nyt

α^k+1 =α^kα= (αF_k+Fk−1)α=α²F_k+αFk−1. Laskemme α² =¹⁺

√ 5 2

2

= ¹⁺²

√ 5+5

4 = ¹⁺

√ 5

2 + 1 = α+ 1, ja voimme jatkaa yhtälöketjua termejä järjestelemällä:

α²F_k+αFk−1 = (α+ 1)F_k+αFk−1

=αF_k+F_k+αFk−1

=α(F_k+F_k−1) +F_k

=αFk+1+Fk+1−1.

Siis väite on tosi, kun n = k+ 1. Induktioperiaatteen mukaan väite on tosi aina, kun n≥1.

Vastaava tulos on voimassa betalle: βⁿ=βF_n+Fn−1, kunn ≥1.(Ks. [3, s. 78])

Lause 3.5(Binet’n kaava). Olkoonn ≥0ja olkootαjaβ yhtälönx²−x−1 = 0 ratkaisut. Tällöin

Fn = αⁿ−βⁿ α−β .

Todistus. (Vrt. [3, s. 78]) Olkoon n ≥0 ja u_n= αⁿ−βⁿ

α−β = αⁿ−βⁿ

√5 . Tällöin

u₀ = α⁰−β⁰

√5 = 0 ja u₁ = α¹−β¹

√5 =

√5

√5 = 1.

Kun n ≥2, saamme

un−1+un−2 = αⁿ⁻¹−βⁿ⁻¹

√5 +αⁿ⁻²−βⁿ⁻²

√5

= ααⁿ⁻²−ββⁿ⁻²+αⁿ⁻²−βⁿ⁻²

√5

= (α+ 1)αⁿ⁻²−(β+ 1)βⁿ⁻²

√5

= α²αⁿ⁻²−β²βⁿ⁻²

√5

= αⁿ−βⁿ

√5 =u_n.

Huomaamme, että u_n toteuttaa Fibonaccin lukujen rekursiokaavan ja al- kuehdot määritelmän 3.1 mukaisesti. Voimme siis kirjoittaau_n=F_n, ja näin olemme johtaneet Fibonaccin luvuille eksplisiittisen lausekkeen.

Lucas’n luvuille on olemassa Binet’n kaavaa vastaava kaava (vrt. [3, s. 79]).

Lause 3.6. Olkoon n ≥0 ja olkoot α ja β yhtälön x²−x−1 = 0 ratkaisut.

Tällöin

L_n=αⁿ+βⁿ.

Todistus. Todistus on lähdeteoksessa jätetty harjoitustehtäväksi. Se onnis- tuisi lauseen 3.5 todistuksen tapaan, mutta käytämme tässä kuitenkin apu- na lausetta 3.3, jonka mukaan kirjoitamme Lucas’n luvun muodossa L_n = Fn+1 +Fn−1, kun n ≥ 1. Tarkastelemme ensin erikseen tapauksen n = 0.

Tällöin

α⁰+β⁰ = 1 + 1 = 2 =L₀.

Kun n ≥1 voimme käyttää Fibonaccin lukuja koskevaa Binet’n kaavaa 3.5, jonka perusteella voimme kirjoittaa

Fn+1+Fn−1 = αⁿ⁺¹−βⁿ⁺¹

α−β +αⁿ⁻¹−βⁿ⁻¹ α−β

= αⁿ⁺¹−βⁿ⁺¹+αⁿ⁻¹−βⁿ⁻¹

α−β .

Koska αβ = −1, saamme edelleen termejä järjestämällä ja potenssin las- kusääntöjä noudattaen

αⁿ⁺¹+αⁿ⁻¹−βⁿ⁺¹−βⁿ⁻¹

α−β = αⁿ⁺¹−αⁿ⁻¹αβ−βⁿ⁺¹+βⁿ⁻¹αβ α−β

= αⁿ⁺¹−αⁿβ−βⁿ⁺¹+βⁿα α−β

= αⁿα−αⁿβ+βⁿα−βⁿβ α−β

= (αⁿ+βⁿ)(α−β) α−β

=αⁿ+βⁿ.

Seuraavaa tulosta käytämme jäljempänä esitetyn Q-matriisin ominaisar- vojen ratkaisemisessa. Lähdeteoksessa ei tätä tulosta erikseen mainita.

Apulause 3.7. Olkoon n ≥ 0 ja olkoot α ja β yhtälön x² − x− 1 = 0 ratkaisut. Tällöin

5F_n² = (αⁿ−βⁿ)². Todistus. Lauseen 3.5 mukaan

F_n = αⁿ−βⁿ α−β , joten

F_n² = αⁿ−βⁿ α−β

!2

. Koska α−β =√

5, saamme

F_n² = (αⁿ−βⁿ)² (√

5)² . Siis

5F_n² = (αⁿ−βⁿ)².

Huomautus 3.2. Tiedämme (ks. [3, s. 122]), että

n→∞lim F_n Fn−1

=φ.

4 Fibonaccin matriiseista

Fibonaccin lukujen teoriaan voidaan erinomaisesti yhdistää erilaisia matrii- sien sovellutuksia. Tämä on tehokas tapa tuottaa ja todistaa uusia ominai- suuksia Fibonaccin luvuille. Tässä luvussa tutustumme ensin Q-matriisiin.

Todistamme sen avulla Cassinin lauseen ja joitakin muita Fibonaccin lukujen ominaisuuksia. Esittelemme Fibonaccin luvuista muodostuvanM-matriisin, ja tutkimme sen yhteydessä myös raja-arvoja. Jatkamme tarkastelemallaQ- matriisin karakteristista yhtälöä ja ominaisarvoja ja huomaamme taas yh- teyden kultaiseen leikkaukseen. Yhdistämällä Q-matriisin tarkasteluun R- matriisi johdamme näiden avulla jälleen uuden ominaisuuden, nyt koskien Lucas’n lukuja. Lopuksi esittelemme matriisien lambda-funktion, jota sovel- lamme Q-matriisin lisäksi matriisiin P. Tämä luku seuraa soveltuvin osin Thomas Koshyn teoksen Fibonacci and Lucas numbers with applications lu- kua 32.

4.1 Q-matriisi

Esitellään ensinQ-matriisi, jota Charles H. King tutki 1960-luvulla San Jose State Collegessa Californiassa. Olkoon

Q=

"

1 1 1 0

#

.

Voimme laskea, että matriisin Q determinantti detQ= 1·0−1·1 =−1 ja että lisäksi

Q² =

"

1 1 1 0

# "

1 1 1 0

#

=

"

2 1 1 1

#

, Q³ =

"

1 1 1 0

# "

2 1 1 1

#

=

"

3 2 2 1

#

ja edelleen

Q⁴ =

"

5 3 3 2

#

.

Huomaamme Fibonaccin lukujen esiintyvän matriiseissa, järjestysluvultaan eksponenttia vastaavan kahdesti ja sitä seuraavan ja edeltävän diagonaalilla.

Osoitamme Q-matriisin toteuttavan aina seuraavan ominaisuuden.

Lause 4.1. Olkoon n ≥1 ja Q=

"

1 1 1 0

#

. Tällöin

Qⁿ=

"

F_n+1 F_n F_n Fn−1

#

.

Todistus (vrt. [3, s. 363]). Todistetaan lause induktiolla. Todetaan ensin väi- te todeksi, kun n= 1. Siis

Q¹ =

"

F₂ F₁ F₁ F₀

#

=

"

1 1 1 0

#

=Q.

Oletetaan sitten väite todeksi, kunn =k. Siis Q^k =

"

F_k+1 F_k F_k F_k−1

#

. Tällöin

Q^k+1 =Q^kQ¹ =

"

F_k+1 F_k F_k F_k−1

# "

1 1 1 0

#

=

"

Fk+1+Fk Fk+1

F_k+Fk−1 F_k

#

=

"

F_k+2 F_k+1 F_k+1 F_k

#

=

"

F_(k+1)+1 F_(k+1) F_(k+1) F(k+1)−1

#

.

Siis väite on tosi, kun n = k+ 1. Induktioperiaatteen mukaan väite on tosi aina, kun n≥1.

4.2 Cassinin lause

Käyttämällä Q-matriisia, matriisien laskusääntöjä ja lausetta 4.1, voimme todistaa Cassinin lauseen ja muita tuloksia Fibonaccin luvuille.

Lause 4.2 (Cassinin lause). Olkoon n ≥ 1. Tällöin Fibonaccin luvuilla on voimassa yhtälö Fn−1F_n+1−F_n² = (−1)ⁿ.

Todistus (vrt. [3, s. 363]). Koska |Q| = −1, niin |Qⁿ| = (−1)ⁿ. Toisaalta lauseen 4.1 perusteella

Qⁿ=

"

F_n+1 F_n F_n Fn−1

#

,

ja siis determinatti |Qⁿ| =Fn−1F_n+1 −F_n². Saamme näin Fn−1F_n+1−F_n² = (−1)ⁿ.

Lause 4.3. Seuraavat yhtälöt ovat voimassa aina, kun n≥1 ja m≥1:

F_m+n+1 =F_m+1F_n+1+F_mF_n, (4.1)

Fm+n =Fm+1Fn+FmFn−1, (4.2)

F_m+n =F_mF_n+1+Fm−1F_n, (4.3)

Fm+n−1 =F_mF_n+Fm−1Fn−1. (4.4)

Todistus (vrt. [3, s. 364]). Yhtälöstä Q^mQⁿ=Q^n+m saamme

"

F_m+1 F_m F_m Fm−1

# "

F_n+1 F_n F_n Fn−1

#

=

"

F_m+n+1 F_m+n F_m+n Fm+n−1

#

ja tästä matriisien kertolaskulla

"

F_m+1F_n+1+F_mF_n F_m+1F_n+F_mFn−1

F_mF_n+1+Fm−1F_n F_mF_n+Fm−1Fn−1

#

=

"

F_m+n+1 F_m+n F_m+n Fm+n−1

#

. Edelleen matriisien yhtäsuuruuden perusteella voimme kirjoittaa alkioittain

F_m+1F_n+1+F_mF_n =F_m+n+1, F_m+1F_n+F_mF_n−1 =F_m+n, FmFn+1+Fm−1Fn =Fm+n, F_mF_n+Fm−1Fn−1 =Fm+n−1.

Voimme johtaa lauseen 4.3 yhtälöistä lisää hyödyllisiä ominaisuuksia.

Seuraavia yhtälöitä käytämme myöhemmin matriisin Pⁿ lambda-funktiota λ(Pⁿ) laskiessamme.

Lause 4.4. Olkoon n ≥ 1. Tällöin Fibonaccin ja Lucas’n luvut toteuttavat seuraavat yhtälöt:

F_2n+1 =F_n²+F_n+1² , (4.5)

F_2n =F_nL_n. (4.6)

Todistus (vrt. [3, s. 364]). Sijoittamalla m = n yhtälöön (4.1) saamme sen suoraan muotoonF_2n+1 =F_n²+F_n+1² . Yhtälön (4.2) erikoistapauksena, kun m=n, saamme lauseen 3.3 perusteella

F_2n=F_n+1F_n+F_nF_n−1 =F_n(F_n+1+F_n−1) = F_nL_n.

Lause 4.5. Olkoon n ≥ 1 ja m ≥ 1. Tällöin Fibonaccin ja Lucas’n luvut toteuttavat seuraavan yhtälön:

L_m+n=F_m+1L_n+F_mLn−1. (4.7)

Todistus (vrt. [3, s. 364]). Korvataan n seuraajallaan n+ 1 yhtälössä (4.1), ja lasketaan saatu yhtälö

F_m+n+2 =F_m+1F_n+2+F_mF_n+1,

yhteen yhtälön (4.2),

F_m+n =F_m+1F_n+F_mFn−1

kanssa, jolloin saamme

Fm+n+2+Fm+n =Fm+1(Fn+2+Fn) +Fm(Fn+1+Fn−1).

Lauseen 3.3 perusteella saamme yhtälön muotoon L_m+n+1 = F_m+1L_n+1 + F_mL_n. Nyt korvataann edeltäjälläänn−1, jolloin saadaan edellinen Lucas’n luku Lm+n=Fm+1Ln+FmLn−1.

Yhtälöistä (4.2) ja (4.3) voimme muotoilla myös seuraavan Fibonaccin ja Lucas’n lukuja koskevan ominaisuuden.

Lause 4.6. Olkoon n ≥1 ja m ≥1. Tällöin 2Fm+n=FmLn+FnLm. (4.8)

Todistus. (Vrt. [3, s. 364].) Laskemalla yhtälöt (4.2), F_m+n = F_m+1F_n + F_mFn−1, ja (4.3), F_m+n=F_mF_n+1+Fm−1F_n, puolittain yhteen, saamme

2F_m+n =Fm(F_n+1+Fn−1) +Fn(F_m+1+Fm−1).

Lauseen 3.3 perusteella F_n+1+Fn−1 =L_n ja F_m+1+Fm−1 =L_m. Siis 2F_m+n=F_mL_n+F_nL_m.

Lucas’n luvuille on olemassa vastaava tulos (vrt. [3, s. 364]). Todistamme sen seuraavaksi käyttäen luvussa 3.4 esitettyjä Binet’n kaavoja, F_n= ^αn_α−β^−βn ja L_n=αⁿ+βⁿ. Lähdeteoksessa todistus on jätetty harjoitustehtäväksi.

Lause 4.7. Olkoon n ≥1 ja m ≥1. Tällöin 2L_m+n=L_mL_n+ 5F_mF_n. (4.9)

Todistus. Binet’n kaavojen avulla kirjoitamme yhtälön oikean puolen muo- toon

L_mL_n+ 5F_mF_n = (α^m+β^m)(αⁿ+βⁿ) + 5 α^m−β^m α−β

! αⁿ−βⁿ α−β

!

. Koska α−β =√

5, saadaan kertolaskuja järjestelemällä (α^m+β^m)(αⁿ+βⁿ) + 5 α^m−β^m

α−β

! αⁿ−βⁿ α−β

!

=α^mαⁿ+α^mβⁿ+β^mαⁿ+β^mβⁿ+ (α^m−β^m)(αⁿ−βⁿ)

=α^m+n+α^mβⁿ+β^mαⁿ+β^m+n+α^mαⁿ−α^mβⁿ−β^mαⁿ+β^mβⁿ

= 2(α^m+n+β^m+n)

= 2L_m+n.

Seuraava ominaisuus, joka saadaan lauseen 4.7 erikoistapauksena, on läh- dekirjassa todettu R-matriisin esittelyn yhteydessä (ks. [3, s. 367]).

Seurauslause 4.8. Olkoon n ≥1. Tällöin 5F_n = 2L_n+1−L_n.

Todistus. Yhtälö saadaan suoraan lauseen 4.7 erikoistapauksena, kunm = 1.

Tällöin 2L_n+1 =L₁L_n+ 5F₁F_n=L_n+ 5F_n, ja 5F_n = 2L_n+1−L_n.

4.3 M-matriisi

Esittelemme lauseessa 4.9 matriisin M = [^{1 1}_{1 2}], jota Sam Moore tutki Com- munity College of Allegheny Countyssa Pennsylvaniassa vuonna 1983.

Lause 4.9. Olkoon n ≥1 ja M =

"

1 1 1 2

#

. Tällöin

Mⁿ =

"

F2n−1 F_2n F_2n F_2n+1

#

.

Todistus (vrt. [3, s. 618]). Todistamme lauseen induktiolla. Väite on tosi, kun n = 1, sillä

M¹ =

"

F2−1 F₂ F₂ F₂₊₁

#

=

"

1 1 1 2

#

=M. Oletetaan sitten, että

M^k =

"

F2k−1 F_2k F_2k F_2k+1

#

.

Matriisien laskusääntöjen ja huomautuksessa 3.1 esitettyjen yhtälöiden avul- la saamme

M^k+1 =M^kM¹ =

"

F_2k−1 F_2k F_2k F_2k+1

# "

1 1 1 2

#

=

"

F2k−1+F_2k F2k−1+ 2F_2k F_2k+F_2k+1 F_2k+ 2F_2k+1

#

=

"

F_2k+1 F_2k+2 F_2k+2 F_2k+3

#

=

"

F2(k+1)−1 F_2(k+1) F2(k+1) F2(k+1)+1

#

.

Esimerkki 4.1.

M⁵ =

"

F2·5−1 F2·5

F2·5 F2·5+1

#

=

"

F9 F10

F₁₀ F₁₁

#

=

"

34 55 55 89

#

.

Lause 4.10. Olkoon n ≥1,M = [^{1 1}_{1 2}] ja α= ¹⁺

√ 5

2 . Tällöin

n→∞lim Mⁿ F2n−1

=

"

1 α

α α+ 1

#

.

Todistus (vrt. [3, s. 365]). Suorittamalla jakolaskun saamme Mⁿ

F2n−1

=

"

F2n−1/F2n−1 F2n/F2n−1

F_2n/F2n−1 F_2n+1/F2n−1

#

. Koska huomautuksen 3.2 mukaan raja-arvo limk→∞ Fk

Fk−1 =α, kun k ≥1, ja lisäksi

F_2n+1 F2n−1

= F2n−1+F_2n F2n−1

= 1 + F_2n F2n−1

, saamme alkioittain raja-arvot

n→∞lim F_2n F2n−1

=α ja lim

n→∞

F_2n+1 F2n−1

= 1 +α.

Lisäksi selvästi F_2n−1/F_2n−1 = 1 aina, kun n ≥ 1. Näin saamme matriisin raja-arvon muotoon

n→∞lim Mⁿ F_2n−1 =

"

1 α

α α+ 1

#

.

Vastaavasti matriisijono {Qⁿ/F2n−1} suppenee kohti matriisia [^{1+α α}_{α 1}] (ks. [3, s. 365])

4.4 Karakteristinen yhtälö ja ominaisarvot

Jatkamme Q-matriisin tarkastelua tutkimalla matriisin Qⁿ karakteristista yhtälöä|Qⁿ−xI|= 0, missä n≥1,I = [^{1 0}_{0 1}] (vrt. [3, s. 365–366]). Yhtälön ratkaisut ovat matriisin Qⁿ ominaisarvot. Lauseen 3.3 ja Cassinin lauseen 4.2 perusteella saamme determinantin muotoon

|Qⁿ−xI|=

F_n+1−x F_n F_n Fn−1 −x

= (F_n+1−x)(Fn−1−x)−F_nF_n

=x²−(F_n+1+Fn−1)x+ (F_n+1Fn−1 −F_n²)

=x²−L_nx+ (−1)ⁿ.

Ratkaisukaavalla saamme karakteristisen yhtälönx²−Lnx+(−1)ⁿ= 0 juuret

x₁ = L_n+^qL²_n−4(−1)²

2 ja x₂ = L_n−^qL²_n−4(−1)²

2 .

Lauseen 3.6 mukaan L_n = αⁿ +βⁿ, ja apulauseen 3.7 perusteella 5F_n² = (αⁿ−βⁿ)². Koska lisäksi αβ =−1, saamme neliöjuurilausekkeen muotoon

q

L²_n−4(−1)ⁿ=^q(αⁿ+βⁿ)²−4(αβ)ⁿ

=^q(αⁿ−βⁿ)² =^q5F_n²

=√ 5F_n. Siis

x₁ = Ln+√ 5F_n

2 ja x₂ = Ln−√ 5F_n

2 .

Toisaalta, koska αⁿ+βⁿ =L_n ja αⁿ−βⁿ =√

5F_n, saamme 2αⁿ =αⁿ+βⁿ+αⁿ−βⁿ =L_n+√

5F_n ja αⁿ = L_n+√

5F_n

2 ,

ja samoin

2βⁿ=αⁿ+βⁿ−αⁿ+βⁿ=L_n−√

5F_n ja βⁿ= L_n−√

5F_n

2 .

Olemme siis johtaneet seuraavan lauseen.

Lause 4.11. Matriisin Qⁿ ominaisarvot ovat αⁿ ja βⁿ.

Tutkimme vielä erikoistapausta, kun n = 1. Kirjoitamme lauseen 4.11 muotoon:

Seurauslause 4.12. Matriisin Q ominaisarvot ovat α ja β.

Saamme karakteristisesta yhtälöstä x² − L_nx + (−1)ⁿ = 0 kultaisesta leikkauksestakin tutun yhtälön x²−x−1 = 0. Toisaalta

"

2 1 1 1

#

−

"

1 1 1 0

#

−

"

1 0 0 1

#

=

"

0 0 0 0

#

, siisQ²−Q−I =

"

0 0 0 0

#

. Huomaamme, että Qtoteuttaa karakteristisen yhtälönsä. Tämä on siis yksi Cayley-Hamiltonin lauseen 2.1 ilmenemä.

4.5 R-matriisi

Seuraavaksi tutustumme matriisiinR= [^{1 2}₂₋₁]. Sen esittelivät ensimmäisenä, vuonna 1963, V. E. Hoggatt ja I. D. Ruggles.

Lause 4.13. Olkoon R= [^{1 2}₂₋₁]. Tällöin RQⁿ=

"

L_n+1 L_n L_n L_n−1

#

.

Todistus (vrt. [3, s. 367]). Lauseen 4.1 mukaanQⁿ=^hF_Fⁿ⁺¹_{n F}^F_n−1^{n i}, missän ≥ 1. Matriisien kertolaskulla saamme

RQⁿ =

"

1 2 2 −1

# "

F_n+1 F_n F_n Fn−1

#

=

"

F_n+1+ 2F_n F_n+ 2Fn−1

2F_n+1−F_n 2F_n−Fn−1

#

.

Tarkastellaan matriisia alkioittain, Fibonaccin lukujen määritelmää ja lauset- ta 3.3 apuna käyttäen. Saamme

F_n+1+ 2F_n=F_n+1+F_n+F_n =F_n+2+F_n =L_n+1. Vastaavasti edellinen Lucas’n luku L_n =F_n+ 2Fn−1.Toisaalta

2F_n+1−F_n=F_n+1+Fn−1+F_n−F_n =F_n+1+Fn−1 =L_n, ja sitä edellinen Lucas’n luku Ln−1 = 2F_n−Fn−1. Voimme siis kirjoittaa

"

Fn+1+ 2Fn Fn+ 2Fn−1

2F_n+1−F_n 2F_n−Fn−1

#

=

"

Ln+1 Ln

L_n Ln−1

#

.

Lause 4.14. Olkoon n ≥1. Tällöin

Ln+1Ln−1−L²_n= 5(−1)ⁿ⁺¹.

Todistus (vrt. [3, s. 367]). Determinantin tulosäännön mukaan|RQⁿ|=|R||Qⁿ|.

Lauseen 4.13 perusteella

L_n+1 L_n L_n Ln−1

=

1 2 2 −1

F_n+1 F_n F_n Fn−1

.

Laskemalla determinantit saamme L_n+1L_n−1 −L²_n = −5(F_n+1F_n−1 −F_n²).

Koska Cassinin lauseen mukaan F_n+1Fn−1−F_n² = (−1)ⁿ, voimme kirjoittaa L_n+1Ln−1−L²_n = 5(−1)ⁿ⁺¹.

4.6 Cramerin lause

Seuraavaksi muistutamme mieleen Cramerin lauseen, ja tutkimme, kuinka sen avulla voi johtaa aikaisemmin esitetyn Cassinin lauseen. Tähän tarkas- teluun olemme tehneet pohjatyötä lähdeteoksesta poiketen jo luvussa 3.1, kun todistimme, että kahden peräkkäisen Fibonaccin luvun suurin yhteinen tekijä, syt(F_k, F_k+1) = 1.

Lause 4.15 (Cramerin lause). Olkoon ax+by =e cx+dy=f.

Jos ad−bc6= 0, niin yhtälöparin ainoa ratkaisu on

x=

e b f d

a b c d

ja y =

a e c f

a b c d

.

Johtaaksemme Cassinin lauseen 4.2, sovellamme Cramerin lausetta yhtä- löpariin jossa esiintyy Fibonaccin lukuja. Tutkimme yhtälöparia

F_nx+Fn−1y =F_n+1 F_n+1x+F_ny =F_n+2.

Lauseen 3.2 mukaan kahden peräkkäisen Fibonaccin luvun suurin yhteinen tekijä, syt(F_k, F_k+1) = 1. Siis determinantti

F_n Fn−1

F_n+1 F_n

=F_n² −Fn−1F_n+1 6= 0,

joten voimme käyttää Cramerin lausetta. Fibonaccin lukujen rekursiokaavan mukaan yksi ratkaisu on selvästi x = y = 1. Cramerin lauseen perusteella tämä on ainoa ratkaisu, ja voimme kirjoittaa

x=

F_n+1 Fn−1

Fn+2 Fn

F_n Fn−1

Fn+1 Fn

= 1, y=

F_n F_n+1 Fn+1 Fn+2

F_n Fn−1

Fn+1 Fn

= 1.

Jälkimmäisestä saamme

F_n F_n+1 F_n+1 F_n+2

=

F_n Fn−1

F_n+1 F_n

.

Laskemalla determinantit saamme FnFn+2 − F_n+1² = F_n² − Fn−1Fn+1, siis F_nF_n+2 −F_n+1² = −(Fn−1F_n+1−F_n²). Merkitään nyt p_n = Fn−1F_n+1−F_n², jolloin edellinen yhtälö saadaan rekursiokaavaksi p_n+1 = −p_n, missä p₁ = F0F2 −F₁² = −1. Todistamme induktiolla, että pn = (−1)ⁿ: Alkuaskel on voimassa, sillä p₁ =−1. Oletamme, että p_k = (−1)^k. Tällöin p_k+1 =−p_k =

−(−1)^k = (−1)^k+1, ja induktioperiaatteen mukaan p_n = (−1)ⁿ aina, kun n ≥1. Olemme näin johtaneet Cassinin lauseen, Fn−1Fn+1−F_n² = (−1)ⁿ.

4.7 Lambda-funktio

Muusikko Fenton S. Stancliff tutki laajasti matriisien lambda-funktiota λ.

Hänen julkaisemattomiin muistiinpanoihinsa viittaavat myös Marjorie Bick- nell ja V. E. Hoggatt, Jr. artikkelissaan aiheesta. Stancliff määrittelee matrii- sinAlambda-funktion,λ(A), determinatin detAmuutoksena, kun matriisin A jokaiseen alkioon lisätään luku yksi (ks.[2, s. 47]). Yhdistämällä lambda- funktion Fibonaccin matriiseihin, voimme johtaa jälleen lisää Fibonaccin lu- kujen ominaisuuksia (vrt. [3, s. 382–383]).

Määritelmä 4.1. Olkoon A= (a_ij)n×n ja A^∗ = (a_ij + 1)n×n. Tällöin λ(A) = |A^∗| − |A|.

Esimerkki 4.2. Olkoon A=

"

a b c d

#

. Tällöin A^∗ =

"

a+ 1 b+ 1 c+ 1 d+ 1

#

. Nyt

|A|=ad−bc ja

|A^∗|= (a+ 1)(d+ 1)−(b+ 1)(c+ 1)

=ad−bc+a+d−b−c, sekä λ(A) =|A| − |A^∗|=a+d−b−c.

Lisätään matriisin A jokaiseen alkioon vakio k. Näin määritellyn uuden matriisin A^∗ determinantti on

|A^∗|=

a+k b+k c+k d+k

= (ad−bc) +k(a+d−b−c),

joka voidaan edelleen kirjoittaa määritelmän 4.1 mukaistaλ-funktiota käyt- täen muodossa

|A^∗|=|A|+kλ(A).

Valitsemalla A = Qⁿ, saamme johdettua uuden ominaisuuden Fibonaccin luvuille.

Lause 4.16. Olkoon n >2. Tällöin

4F_n² =F_n+2F_n+1−F_nFn−3+ (−1)ⁿ⁺¹. Todistus (vrt. [3, s. 382]). Olkoon A=Qⁿ. Nyt

|(Qⁿ)^∗|=|Qⁿ|+kλ(Qⁿ).

Toisaalta, koska Qⁿ=^hF_F^{n−1 Fn}

n Fn+1

i, voimme kirjoittaa esimerkin 4.2 tapaan λ(Qⁿ) = Fn+1+Fn−1 −2Fn

=Fn−1+F_n+Fn−1−F_n−Fn−2−Fn−1

=Fn−3+Fn−2 −Fn−2 =Fn−3,