ISSN 0351-6652 Letnik 31 (2003/2004) Številka 3 Strani 144-149 Sandi Klavžar: O LUCASOVIH ŠTEVILIH Ključne besede: matematika, teorija števil, Fibonaccijeva števila, Lu-casova števila. Elektronska verzija: http://www.presek.si/31/1559-Klavzar.pdf © 2003 Društvo matematikov, fizikov in astronomov Slovenije © 2010 DMFA - založništvo O LUCASOVIH ŠTEVILIH Ravna barvanja in Fibonaccijeva števila Recimo, da imamo zaporedje kvadratov, ki jih želimo pobarvati na naslednji način. Katerikoli posamezni kvadrat lahko pobarvamo z eno barvo (recimo svetlo sivo), dva sosednja kvadrata pa lahko pobarvamo le skupaj z neko drugo barvo (recimo temno sivo). Za taka sosednja kvadrata bomo rekli, da tvorita domino. Na koliko različnih načinov lahko ua ta način pobarvamo vrsto kvadratov predpisane dolžine? Ce je dolžina vrste ena, imamo en sam način, to je, da. edini kvadrat pobarvamo svetlo. Za dolžino dva imamo dva načina, bodisi vsakega izmed kvadratov pobarvamo svetlo bodisi naredimo domino. Za dolžini tri in štiri naj bralec sam prešteje vse možne načine, za dolžino pet. pa imamo osem načinov, ki so prikazani na sliki 1. Na primer, barvanje označeno s 3 je sestavljeno iz enega kvadrata in dveh domin. 5 6 Slika 1. Osem ravnih barvanj dolžine pet. Naj bo 71 naravno število, ki predstavlja, število kvadratov, in naj Fn označuje število vseh opisanih barvanj. Zgoraj smo videli, da je Fi — 1. F2 = 2 in F5 = 8. Naj bo sedaj n > 3 in poglejmo poljubno barvanje n kvadratov. Barvanje lahko končamo na dva načina: • bodisi je zadnji kvadrat pobarvan svetlo • bodisi zadnja dva kvadrata tvorita domino. V prvem primeru lahko preostalih n — 1 kvadratov pobarvamo na poljuben predpisan način in to lahko naredimo na T^-i načinov. Podobno lahko v drugem primeru pobarvamo preostalih n — 2 kvadratov na Fn_2 načinov. Ugotovili smo torej, da za rt > 3 velja Fn = Fn_! + . (1) Na primer, F3 = JP2 + = 2 + 1 a 3 in j?4 = Fz-f F2 = 3 + 2 = 5; Tb sta ravno vrednosti, za kateri smo bralcu že svetovali, da ju poišče tako, da pregleda vse možnosti. Nadalje je = f!i + F3 = 5 + 3 = 8, kar smo tudi videli na sliki 1. Opazimo lahko, da so tri barvanja na sliki 1 taka, da se zaključijo z domino, pet pa s svetlim kvadratom. Število načinov razporeditve ploščic torej tvori zaporedje števil 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... , kjer začnemo z 1 in 2. Vsako naslednje število dobimo kot vsoto prejšnjih dveh števil. Naleteli smo na znamenito zaporedje Fibonaccijevih števil, ki ima poleg opisane interpretacije še mnoge druge zanimive načine opisa. Fibonaccijeva števila so zelo zanimiva in pomembna v matematiki. Ker je Presek že nekajkrat pisal o njih. bomo sedaj malce skrenili s poti in si zastavili vprašanje, kaj dobimo, če se iz ravne vrste (kvadratov) preselimo na krog. Krožna barvanja in Lucasova števila Razdelimo krog na n enakih krožnih izsekov, na sliki 2 imamo narisan primer za n = 5. Na koliko načinov lahko sedaj pobarvamo krožne izseke, če jih barvamo tako, da lahko krožni izsek pobarvamo z eno barvo (svetlo sivo), ali dva sosednja izseka pobarvamo z drugo barvo (temno sivo)? Na sliki 2 imamo narisane vse možnosti za primer n = 5. Prva možnost je, da vse izseke pobarvamo svetlo. Nadalje lahko dva sosednja izseka pobarvamo temno, preostale izseke pa svetlo. Takih možnosti je pet, označene so s števili od 2 do 6. Nazadnje lahko pobarvamo dvakrat po dva sosednja izseka temno, preostali edini izsek pa svetlo. Tudi teh možnosti (označenih od 7 do 11) je pet, skupaj je torej enajst načinov. Označimo z Ln število vseh različnih zgoraj opisanih barvanj kroga razdeljenega na n krožnih izsekov. Premislili smo že, da je L5 — 11. Preden nadaljujemo, si poglejmo povezavo barvanj s slik 1 in 2. Barvanja na sliki 2 prerežimo med krožnima izsekoma 1 in 5. Tedaj tri barvanja izgubijo lastnost, ki smo jo zahtevah, namreč, da po dva temna izseka nastopata skupaj. To so barvanja označena s 6, 8 in 10, torej barvanja, ki imajo par izsekov 5 in 1 skupaj pobarvan s temno barvo. Preostalih osem barvanj pa ravno sovpada z barvanji s slike 1. Z drugimi besedami, s tem, ko smo namesto v ravni vrsti barvali v krogu, smo pridobili tri nove načine. Posplošimo ta premislek! 8 9 10 11 Slika 2. Enajst krožnih barvanj dol zine pet. Naj bo n vsaj 4. Vsako ravno barvanje dolžine n nam da tudi krožno barvanje dolžine n tako, da začetek in konec ravnega zaporedje zlepimo skupaj. Takih barvanj je Fn. Za vsako krožno barvanje, ki ga ne moremo dobiti na ta način, tvorita izseka. r> in l zaporedni temni par (torej tvorita "domino"), Vsako tako barvanje lahko dobimo iz ravnega barvanja dolžine n — 2 tako, da na začetek in konec dodamo en temen kvadrat ter ju zlepimo skupaj v temno domino. Ker je takih barvanj smo za ri > 4 ugotovili, da velja Ln = + Fn-2 • (2) Od tod in iz (2) sledi Ln = Fn + Fn^2 = + Fn_2) + (Fn„3 + Fn^i). Po drugi strani zaradi (2) dobimo V zgornjih dveh enakostih si no na desni strani dobili isti izraz, torej morata biti tudi izraza na levi enaka, zato za rt > 4 velja = + Ln-2 ■ (3) Iz (2) sledi, da je L 4 = F4 + F2 = 5 4- 2 = 7. Vsak bralec naj sam nariše vseh sedem barvanj kroga, razdeljenega na štiri krožne izseke. Pozor, z dvema "dominama" imamo dve različni barvanji. Da bo zveza (2) veljala tudi za L4 in L3, definirajmo še L 2 = 3 in Li = 1. Slednji vrednosti lahko utemeljimo tudi takole. Če imamo krog nerazdeljen (torej je cel krog en sam krožni izsek), ga lahko pobarvamo na en sam način. Ce pa imamo dva krožna izseka, če je torej krog razdeljen na polovico, lahko vsako izmed polovic pobarvamo svetlo. Skupaj tvorita domino. Pri tem je pomembno, kje je sredina Lake domine, zgoraj ali spodaj. Torej imamo dve različni domini in tako skupaj tri možna barvanja. Števila barvanj krožnih izsekov torej tvorijo zaporedje števil, ki se začne z 1 in 3, nato pa je vsako naslednje število vsota prejšnjih dveh števih l, 3, 4, 7, 11, 18, 29, 47, 76, 123, 189, Ta števila imenujemo Lucasova števila. Kot vidimo, so definirana skora j enako kot Fibonaccijeva števila, edina razlika, je, da pri Fibonaccijevih začnemo z 1 in 2, medtem ko pri Lucasovih z 1 in 3. Nekaj lastnosti Lucasovih števil Prvo lastnost Lucasovih števil, njihovo zvezo s Fibonaccijevimi števili, smo spoznali v povezavi (2). V nadaljevanju si oglejmo še nekaj lepih lastnosti Lucasovih števil. Najprej pokažimo, kje v Pascalovem trikotniku se skrivajo Lucasova števila. PascaJov trikotnik je trikotna shema števil, ki je zgrajena tako, da imamo v vrstici z oznako 0 euico. Vsaka naslednja vrstica se začne in konča z enico, števila pa podpisujemo tako, da število a v izbrani vrstici napišemo na sredini med števili b in c v prejšnji, pri čemer velja a — b + c.. Spodaj imamo izpisanih nekaj začetnih vrstic Pascalovega trikotnika. 0: J 1 : 1 1 2 : 1 ■2 1 3 : 1 3 3 S 4 : t 4 m 4 m 5 : i 0 10 m 5 i 6 : □ 6 GE 20 15 6 1 7 : i 0 21 35 35 21 7 1 8 : m § 28 56 70 56 28 8 1 Števila iz Pascalovega trikotnika imenujemo binomska. števila in jiii označujemo z binomskim simbolom (V). Pri tem nam Ti pove vrstico Pascalovega trikotnika, v kateri se nahaja dano binomsko število, k pa ustrezno diagonalo, kjer tudi diagonale štejemo od 0 dalje. Na primer, (?) = ^ in © = 56. Pokažimo, kje se v Pasealovem trikotniku skrivajo Lucasova števila. Število Ln lahko izračunamo na naslednji način. Začnemo pri enici v vrstici n in seštejemo tista števila, ki jih dobimo po naslednjem vzorcu: Natančneje, seštejemo vsa tista števila, ki se nahajajo znotraj večjih krožcev. V zgornjem Pasealovem trikotniku sta označeni dve taki izbiri števil. Prva izbira se začne v vrstici 3, ustrezna števila so podčrtana, medtem ko se druga izbira začne v vrstici 8, izbrana števila so v kvadratkih. V prvem primeru je vsota izbranih števil 4, kar je ravno £3, v drugem primeru je vsota 47, in to je Lg. Za Lucasova števila lahko izpeljemo še veliko drugih lepih lastnosti, za vzorec navedimo tri izmed njih. • Za vsak n > 1 velja L\ + Li + • • • + = LnLn+1 — 2 , Na primer, L\ + L2 + L2 + L\ + L2 - l2 + 32 + 42 + 72 + 112 = 1 + 9+ 16 + 494-121 = 196 - 11 ■ 18-2 — L$L§ — 2 . • Za vsak n > 2 velja Ln+i = - (L„ + 5/v,_i) . Na primer, ¿5 = 11 = i(L4 + 5i3). • Za vsak n > 1 velja L2 = L^n + 2(—1)" . Na primer, L2 = 49 = 47 + 2 = L3 + 2(-l)8 = Ls + 2, Naloge 1. Nariši vsa ravna barvanja kvadratov dolžine 6. 2. Izračunaj f^o in ¿203, Seštevaj vsako drugo Fibonaccijevo število, torej izračunaj vsote oblike F\ + F3 + Ali opaziš kako zakonitost? 4. Nariši vsa krožna barvanja dolžine 0. 5. Oglej si nekaj produktov oblike FnLn+1, na primer F^L^ = 3-7 = 21. Ali opaziš kako zakonitost? 6. Spoznali smo vzorec, ki nam iz Pascalovega trikotnika izlušči Luca-sova števila. Recimo, da sedaj zopet začnemo z enico v vrstici n ter nato v omenjenem vzorcu jemljemo le vsako drugo število z drugimi besedami, izbiramo števila spodnje diagonale. Na primer, za n = 8 so to števila 1, 7, 15, 10 in 1, Ali opaziš pravilo? Sandi Klavzar Rešitve so na str. 167.