Nevezetes számok a matematikában SZAKDOLGOZAT
Készítette: Németh Regina
Matematika BSc - elemz® szakirány
Témavezet®: Ágoston István, egyetemi docens ELTE TTK, Algebra és Számelmélet Tanszék
Eötvös Loránd Tudományegyetem Természettudományi Kar
Budapest, 2013
A legtöbb tudományban mindegyik generáció lerombolja azt, amit el®dei építettek. A matematika az egyetlen, amelyben minden egyes generáció új értelmet illeszt a régi struktúrához." (H. Hankel)
1
Tartalomjegyzék
1. Bevezet®
3
2. Nevezetes konstansok
4
2.1. Liouville szám . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.6. Aranymetszés, avagy aranyarány . . . . . . . . . . . . . . . . . . . . . 8 2.9. Egyéb érdekes matematikai konstansok . . . . . . . . . . . . . . . . . 13
3. Nevezetes sorozatok
16
3.1. Fibonacci számok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.6. Catalan-számok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
Köszönetnyílvánítás
30
2
1. fejezet
Bevezet®
Általános iskolában megismerkedtünk a természetes számokkal, fels®tagozatban már találkoztunk a racionális számokkal, a tizedestörtekkel és a gyökökkel. Középiskolában el®kerültek a különlegesebb számokat mint, például a π és az e. Az egyetemen a különleges számok ismerete csak tovább b®vült, például megismertük az imagionárius számot. Akkoriban nem is gondoltam, hogy az eπ·i = −1-gyel, hiszen az e és a π nem egész számok. De, ha vesszük a (−1) és az i vagy az e és a −π kombinációját, (−1)i = e−π = 0, 0432139 . . . , akkor egy transzcendens számot kapunk. A dolgozatomban bemutatom az els® transzcendes számot, amely a Liouvilleszám. Ez a szám segítségével sikerült bebizonyítani azt a sejtést, hogy az e transzcendens. Vannak olyan nevezetes konstansok, amelyekr®l még nem eldöntött, hogy transzcendens szám-e, ilyen például a Catalan-állandó, Brun konstans vagy a Feigenbaum állandó. A dolgozatom els® részében bemutatom még a Catalan-állandót, az aranyarányt, a Brun konstanst és az Euler-Mascheroni konstanst. A nevezetes számok körébe a sorozatok is beletaroznak. Így az egyik legismertebb sorozatot is prezentálni fogom, a Fibonacci-sorozatot tulajdonságaival és az általánosításával. Írok még a kombinatorikában az egyik legfontosabb sorozatról a Catalan-számokról, bemutatom pár tulajdonságát és két alkalmazását.
3
2. fejezet
Nevezetes konstansok
2.1.
Liouville szám
2.2. De níció.
Egy
α
komplex szám algebrai szám, ha létezik olyan nem nulla,
racionális együtthatós polinom, amelynek az
2.3. De níció.
α
gyöke.
Egy komplex szám transzcendens, ha egyetlen racionális együtthatós
polinomnak sem gyöke a nullpolinomon kívül, azaz nem algebrai szám.
Egy konkrét számról általában nehéz eldönteni, hogy algebrai vagy transzcendes szám. Már Euler, Lambert és Legendre is felvetették, hogy a π nem algebrai. Ennek a transzcendenciájának bizonyításához az els® lépést Joseph Liouville tette meg 1844-ben aki megmutatta, hogy a Liouville-konstans:
10−1! + 10−2! + 10−3! + 10−4! + 10−5! + ...
transzcendens. Sok évvel kés®bb 1873-ban sikerült bebizonyítania Charles Hermitenek, hogy az Euler-féle szám, azaz az e szám transzcendens. Ennek a bizonyításnak az ismeretében 1882-ben Carl Louis Ferdinand von Lindemann az "Über die Zahl π " munkájában megmutatta, hogy a π szám transzcendens. Az e és a π szám transzcendenciájának a bizonyítását vélhet®en többen ismerik, mint az els® transzcendens számét. Így a dolgozatomnak ebben a fejezetében a Liouville-konstans transzcendenciáját szeretném bemutatni. Ehhez el®bb egy másik tételt kell el®ször belátni, amely megmutatja, hogy az algebrai számok általában rosszul approximálhatóak.
2.4. Tétel.
Legyen
α egy n-edfokú valós algebrai szám, ahol n≥2, ekkor létezik olyan
c=c(α)>0 valós konstans, hogy bármely rs racionális számra
4
c(α) r |α − | > n . s s
Bizonyítás. Indirekt tegyük fel, hogy bármely c>0-hoz létezik olyan rs , amelyre r c |α − | < n s s
Ebben az esetben létezik a racionális számoknak olyan (1)
lim
i→∞
ri si
sorozata, hogy (si > 0)
ri α− =0 si
sni
Ez azt jelenti, hogy ri ri lim α − = 0, azaz lim =α i→∞ i→∞ si si
(2)
Vegyük az α minimálpolinomját (jelölje mα ), melynek komplex gyökei α1 = α, α2 , α3 , ..., αn . Ekkor n Y mα = a0 + a1 x + ... + an x = an (x − αj ), j=2
ahol a0 , a1 , ..., an egészek és an 6= 0. Az mα minimálpolinomnak nincs többszörös gyöke, mert irreducibilis a racionális számok felett. Ezért az αj számok mind különböz®ek. A minimálpolinomba x helyére srii -t helyettesítve, a következ®t kapjuk: Y n n ri ri ri ri a0 + a1 + ... + an = an −α − αj si si si s i j=2
A bal oldali kifejezés közösnevez®je az sni , ami nem lehet 0, mert a mα -nak nincs racionális gyöke. Így a bal oldal abszolútértékét alulról tudjuk becsülni s1n -nel. i
Y n 1 r 1 r i i ≤ sni an α − − αj n si si j=2 si sni sni -nel beszorozva a következ® becslést kapjuk: n ri Y ri n − αj 1 ≤ s i an α − si si j=2
Az (1)-es (2)-esb®l a következ® egyenlet adódik lim
i→∞
n Y ri j=2
si
− αj
n Y = (α − αj )-vel. j=2
A bal oldalon álló határérték i → ∞ esetén 0-hoz tart, ez azonban ellentmond a becslésnek. 5
Ennek a tételnek a segítségével már könnyebben lehet transzcendens számot konstruálni, hiszen egy α valós szám, ha "nagyon jól" közelíthet®, akkor transzcendens. Egy ilyen számot egy racionális számokból képzett végtelen sor összegeként kaphatunk meg. Ennek a sornak a részletösszegei gyorsan konvergálnak a végtelen sor összegéhez. Például Liouville-konstans is egy ilyen szám, amelyet a következ®kben ismertetek és a transzcendenciáját is bebizonyítom.
2.5. Tétel.
A Liouville-konstans transzcendens, azaz ∞ X 1 α= = 0, 110001000000000000000001... k! 10 k=1
szám transzcendens.
Megjegyzés 1. α valóban egy valós szám, ez legjobban a tizedestört alakjából látszik. 2. Ez a sor konvergens, hiszen a
∞ X
10−k végtelen mértani sorral majorálható
k=1
Bizonyítás. Azt kell bizonyítani, hogy a Liouville-konstans részletösszegei "nagyon jól" approximálják α-t. Els® lépésként írjuk fel az m-edik részletösszeget srmm alakban (sm > 0), ahol rm és sm relatív prímek, azaz (rm , sm ) = 1. Közös nevez®re hozás után a következ®t kapjuk: m X 1 10A + 1 = 10k! 10m! k=1
Ebb®l látszik, hogy az sm = 10m! -sal. Ekkor ∞ X rm 1 0<α− < = sm k=m+1 10k!
∞ X j=(m+1)!
1 10 10 = = m+1 . j (m+1)! 10 9 · 10 9sm
Vegyük a két oldal abszolútértékét, így a következ®t kapjuk: (1)
r m α − < 10 sm 9sm+1 m
A jobb oldal értéke pozitív az abszolútérték jel nélkül is, így elhagyható. Indirekt tegyük fel, hogy valamely n-re α egy n-edfokú algebrai szám. Az αnak a tizedestört alakjából látszik, hogy nem egy szakaszos tizedes tört, hanem egy irracionális szám, tehát n≥ 2. Ekkor az el®z® tétel szerint létezik olyan c(α) > 0, hogy bármely rs racionális számra 6
α −
teljesül. Speciálisan az
rm sm
r c(α) > n . s s
esetén: α − rm > c(α) . sm snm
Ezt az (1)-essel összevetve a következ®ket kapom: c(α) 10 10 < m+1 , azaz c(α) < n−m+1 n sm 9sm 9sm
Vegyük mint a két oldal határértékét végtelenben. c(α) = lim c(α) < lim m→∞
m→∞
10 9sn−m+1 m
= 0,
ami ellentmondás, hiszen c(α) > 0.
7
2.6.
Aranymetszés, avagy aranyarány
Az aranymetszés régóta ismert az emberiség számára. Felismerték, hogy egy szobor, épület vagy akár egy rajz esztétikai szépségét növeli, ha érvényesülnek rajta az aranymetszés arányai. Több neves m¶vész vagy m¶alkotás épít az aranymetszés szabályaira, például a magyar Szent korona is eszerint készült vagy Dante Isteni színjátéka. Bizonyíthatóan az ókorban is ismerték, hiszen az i. e. 2600 körül épült Gízai Nagy-piramisban is megtalálható ez az arány. Mégpedig úgy, hogy a piramis alapélének a fele (kb 186,42 m) és az oldallapjainak a magassága (kb 115,18 m) úgy aránylik egymáshoz, mint az aranyarány. Matematikailag a következ®képpen közelíthetjük meg. Legyen adott egy távolság, melynek a kisebbik része a és a nagyobbik része b.
2.7. De níció.
Ha kisebbik része (a) úgy aránylik a nagyobbik részhez (b), mint a
nagyobbik rész a (b) az egészhez (a+b), azaz
b a = b a+b ezt az arányt aranyaránynak nevezzük.
2.8. De níció.
Ha egy szakaszt egy S pont úgy oszt két részre, hogy a kisebbik sza-
kasz úgy aránylik a nagyobbikhoz, mint a nagyobbik az egészhez, akkor az S az aranymetsz® pontja.
Teljesen nyílvánvaló, hogy két olyan pont létezik, amelyik az AB szakasznak az aranymetsz® pontja lehet, mert az S pont lehet az A ponthoz vagy a B ponthoz közelebb. (Én a következ®kben azt fogom használni, amikor az A-hoz van közelebb az S, tehát az AS szakasz a rövidebb.) A következ® pár sorban ismertetem, hogy lehet kiszámolni az aranymetszés pontos értékét. Induljunk ki a de nícióból: a b = b a+b
8
Ezt beszorzva b-vel és a+b-vel a következ® egyenletet kapom: a2 + ab = b2
Osztva a2 -tel és jobb oldalra rendezve: 0=
b2 b − −1 2 a a
A továbbiakban jelölje ϕ= ab . Ezt beírva az egyenletbe az alábbi másodfokú egyenletet kapom: ϕ2 − ϕ − 1 = 0
Az egyenlet két megoldása: √ √ 1+ 5 1− 5 ϕ1 = ≈ 1, 6180339887... és ϕ2 = ≈ −0, 618033988... 2 2
Az aranymetszést a pozitív gyökkel szokták jellemezni, tehát ϕ=1, 61803.
Az aranymetszés Euklidészi szerkesztése: 1. Vegyünk fel egy tetsz®leges szakaszt, melynek egyik vége legyen A, a másik vége legyen B és a szakasz hosszát jelöljük b-vel, amely az aranymetszés szabályai szerint a nagyobbik rész. 2. A B végére állítsunk egy mer®leges félegyenest a b-re, amelyre felmérjük a távolságot, ennek a metszési pontnak a neve legyen O.
b 2
3. Szerkesszük meg az O középpontú OB sugarú kört. 4. Az A-ból húzzunk szel®t az O-n keresztül. Az A-hoz közelebbi metszéspont legyen C a távolabbi pedig D. Vegyük észre, hogy itt a CD = b. 5. Az AC = a távolság lesz az arány kisebbik része, ugyanis a küls® pontból húzott érint® és szel®szakaszok tétele alapján: a b = b a+b
Az alábbi kép ábrázolja az aranyarányt:
9
Az aranymetszés használatára példaként állíthatjuk a pentagrammát, amelyet az ókorban az eltér® népeknél eltér® jelentése volt, például Babilóniában az öt irányt jelképezte: elöl, hátul, balra, jobbra és fent. Ezeknek az irányoknak asztrológiai jelentést is tulajdonítottak, felülr®l kezdve az óramutatás irányában Mars, Jupiter, Szaturnusz, Merkúr és a Vénusz jelei vannak. A középkorban az öt ®selemet jelölték vele a szellemet, leveg®t, tüzet, vizet és a földet.
A dolgozatomban szeretném bemutatni a pentagramma szerkesztését, melyet az alábbiakban lépésenként ismertetek. 1. El®ször egy ötszöget kell szerkeszteni. (a) Vegyünk fel egy tetsz®leges O pontot és húzzunk bel®le egy tetsz®leges r sugárú kört. (b) Jelöljük be egy tetsz®leges A pontot a körvonalon, ez legyen az ötszög egy pontja. (c) Kössük össze az A pontot az O ponttal. (d) Állítsunk egy mer®legest az AO szakaszra, amely a B pontban fogja metszeni a körvonalat. (e) Az OB szakasz felez®pontja legyen C. A C pontból AC sugarral húzzunk egy kört, amely elmetszi az OB egyenest a D pontban. 10
(f) Felvesszük az AD távolságot és körz®zünk vele A-ból, így keletkezik az E és az F metszéspont, amely az ötszögnek két pontja lesz. (g) Körz®nyílásba vesszük az AE távolságot és elmetszük vele a kört az E pontból, így megkapjuk a G pontot. Ezt megismételjük az F pontból is és így kialakul az ötszög utolsó pontja is H. (h) Az AFHGE pontokat összekötve egy szabályos ötszöget kapunk.
2. Miután megszerkesztettük az ötszöget már csak az átlóit kell behúzni és kész is a pentagramma.
A fenti a szerkesztést alátámasztja Hajós György: Bevezetés a geometriába 163-164. oldala.
Joggal kérdezhetnénk, hogy a pentagrammban hol jelenik meg az aranymetszés. Tekintsük az ABHE húrnégyszöget, jelölje az oldalakat a és az átlókat b. Ekkor meg gyelhet®, hogy ez egy húrtrapéz, amely kiegészíthet® egy háromszöggé. Legyen a háromszög csúcsa K. 11
A DAF és a HFA az ötszögnek egy-egy szöge, amelyekr®l tudjuk, hogy 108 fokosak. A KAF szög éppen a DAF kiegészít® szöge, így ez 72 fokos. A HFA kiegészít® szöge az AFK szög. Tehát az AFK háromszög egy egyenl® szárú háromszög, amelynek a harmadik szöge 36 fokos. Meg gyelhet®, hogy az AHD háromszög hasonló az AKF háromszöghöz. Ezért az AKF oldalai pontosan b-k lesznek. Ekkor a párhuzamos szel®k tétele alapján, az AF úgy aránylik a DH-hoz, mint az AK, a DK-hoz, azaz: a b = b a+b
12
2.9.
Egyéb érdekes matematikai konstansok
1. Euler-Mascheroni konstans. A harmadik legfontosabb szám az Euler-Mascheroni konstans, melyet néha csak Euler számnak nevezünk. Eldöntetlen kérdés, hogy algebrai szám vagy transzcendens, ráadásul azt sem tudjuk bizonyítani, hogy racionális vagy irracionális szám-e.
2.10. Tétel. n→∞ lim
n X 1 k=1
k
! határérték létezik és véges.
− log(n)
Bizonyítás. Alakítsuk át a szummás kifejezést n X 1 k=1
k
− log(n) =
n X 1 k=1
n
Z −
k
1
n−1
X 1 dx = x k=1
Z
k+1
k
1 1 − k x
dx +
1 n
Észrevehet®, hogy ha k ≤ x ≤ k + 1 teljesül, akkor az alábbi egyenl®tlenséget kapjuk: 0≤
1 1 1 1 1 1 − ≤ − = < 2 k x k k+1 k(k + 1) k
Tehát 1 1 − < 1 k x k2 ∀k ≤ x ≤ k + 1, ekkor n X 1 k=1
ahol |ak | < n X k=1
1 k2
. Mivel a
k
P
− log(n) =
1 k2
n X
ak +
k=1
konvergens és
1 n
1 n
→ 0, ha n → ∞, ezért a
1 − log(n) határértéke létezik és véges. k
2.11. De níció. γ = lim
n→∞
n X 1 k=1
k
Az Euler-Mascheroni konstans:
! − log(n)
Z
∞
= 1
13
1 1 − [x] x
dx ≈ 0.57721566490153286.
Megyjegyzés. A bizonyításból nyilvánvaló, hogy n→∞ lim Z
és
1
∞
1 1 − [x] x
n X 1 k=1
k
! − log(n)
dx egyenl®.
Számos helyen el®fordul az Euler-Mascheroni konstans, például • A számelméletben felírható a prímszámok sorozata: ! X log(p) , ahol p prím. γ = lim log(n) − n→∞ p−1 p≤n • A számelméletben egy fontos konstans az eγ . A következ® sorozattal
írható fel: n
Y pi 1 e = lim , ahol pn az n-edik prímszám. n→∞ log(pn ) p −1 i=1 i γ
• A válószín¶ségszámításban a kupongy¶jt® problémánál merül fel. Rövi-
den ismertetem a problémát. Tegyük fel, hogy n darab kuponból véletlenszer¶en visszatevéssel húzunk. Mennyi a várható értéke annak, hogy megszerezzük mind az n kupont? Legyen ti az i-edik kupon megszerzésének az ideje, miután már megszereztük az (i-1)-ediket, ennek a várható értéke E(ti ), és legyen T az az id®, amennyi ahhoz kell, hogy minden kupont kihúzzunk egyszer, ennek a várható értéke E(T ). Ekkor világos, hogy 1 1 1 E(T ) = E(t1 ) + E(t2 ) + E(t3 ) + · · · + E(tn ) = + + ··· + p 1 p2 pn n n n 1 1 1 = + + ··· + = n + + ··· + = n · Hn n n−1 1 1 2 n
A Hn jelölje a harmonikus sort. Használjuk az asszimptotikus becslést E(T ) = n · Hn = n log(n) + γn +
1 + o(1), n → ∞ 2
2. Catalan-állandó. Eugéne Charles Catalan belga matematikusról kapta a nevet ez az állandó, amely leggyakrabban a kombinatorikai becslésekben fordul el®. Jelenleg 31 026 000 000 2009 tizedesjegye ismert, amelyet április 16-án Alexander J. Yee és Raymond Chan tették közzé. Még nem sikerült bizonyítani, hogy algebrai szám vagy transzcendes, s®t azt sem tudjuk, hogy irracionális-e.
2.12. Tétel.
A
∞ X (−1)n (2n + 1)2 n=0
konvergens.
14
∞ X (−1)n A egy Leibniz-sor, mert 2 (2n + 1) n=0
Bizonyítás.
(a) váltakozó el®jel¶, 1 =0 n→∞ (2n + 1)2
(b) tagjai nullsorozatot alkotnak: lim
(c) a sorozat tagjai abszolút értékben mononton csökken®: 1; 19 ≈ 0, 111; 251 = 1 ≈ 0, 0204 . . . 0, 04; 49
Tehát a fenti sor Leibniz-sor, így konvergens.
2.13. De níció.
Catalan-állandó:
∞ X (−1)n 1 1 1 1 G= = 2 − 2 + 2 − 2 + · · · ≈ 0, 9159655911177 . . . 2 (2n + 1) 1 3 5 7 n=0
Integrálok, melyeknek az értéke éppen a Catalan-állandó: Z
1
Z
1
1 dxdy 2 2 0 0 1+x y Z 1 ln(t) (b) G = − dt 2 0 1+t Z π 4 t dt (c) G = 0 sin(t)cos(t) Z ∞ arctan(e−t )dt (d) G =
(a) G =
0
3. Brun-konstans. A számelméletben ez a konstans nagyon fontos, hiszen megoldhatna egy nevezetes problémát, az ikerprím-sejtést. Ez a sejtés az, hogy végtelen sok olyan p prím van, amire p+2 is prím, például 3,5; 5,7; 17,19. Az ilyen prímpárokat, melyeknek a különbsége 2, ikerprímeknek nevezzük.
2.14. Tétel.
Brun-tétele:
1 1 + 3 5
+
1 1 + 5 7
+
1 1 + 11 13
+ ...
véges
értékhez konvergál.
2.15. De níció. B2 =
Brun-konstans:
1 1 + 3 5
+
1 1 + 5 7
+
1 1 + 11 13
+ · · · ≈ 1, 902160583104
Ha bebizonyítanánk, hogy a Brun-konstans irracionális, akkor abból azonnal következne, hogy az ikerprím-sejtés igaz volna. Viszont, ha a racionalitását sikerülne bebizonyítani az nem igazolná és nem is cáfolná ezt a kérdést.
15
3. fejezet
Nevezetes sorozatok
3.1.
Fibonacci számok
Az egyik legismertebb rekurzív összefüggés Leonardo Fibonacci nevéhez f¶zödik, amelyet 1202-ben megjelent Liber Abaci cím¶ könyvében fogalmazott meg: Egy nyúlpárnak havonta egyszer születik kölyke, egy hím és egy n®stény. A kölyköknek születésük után két hónap múlva lesz el®ször kölykük. Feltételezzük, hogy a nyúlpárok örökké élnek és minden termékeny nyúlpár minden hónapban szül egy újabb nyúlpárt. Hány pár nyúl lesz n hónap múlva? Kis n-ekre könnyen ki lehet számolni, csak gyelni kell, hogy éppen hány nyúlpár válik ivaréretté. Az els® hónapban 1 pár nyulunk van és ez a helyezet a második hónapban sem fog változni. A harmadik hónapban viszont már 2 nyúlpárunk van, hiszen az els® nyúlpárunk ivarérett lett. A negyedik hónapban már 3 nyúlpárnk van és az ötödik hónapban a harmadik hónapban született nyúlpár is ivarérett lett, így 5 nyúlpárt számolhatunk és így tovább. Az egyszer¶ség kedvéért tegyük fel, hogy a nulladik hónapban lév® nyúlpárok száma 0. Így a következ® sorozatot kapjuk: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Ha jobban megnézzük ezt a sorozatot, akkor látható, hogy a következ® számot úgy kaphatjuk meg, hogy az el®z® kett®t összeadjuk. Más szavakkal az (n+1)-edik havi nyúlpárok számát úgy kaphatjuk meg, hogy az n-edik hónapban meglév® nyúlpárok számát és az újszületteket számát összeadjuk. Az újszülöttek száma éppen az (n-1)edik hónapban lév® nyúlpárok számával egyenl®, ugyanis pontosan azok és csak azok fognak az (n+1)-edik hónapban szülni, amelyek az (n-1)-edik hónapban már megvoltak. Jelöljük Fn -el az n-edik hónapban lév® nyúlpárok számát. Így a következ® de níciót írhatjuk fel:
3.2. De níció.
Fibonacci számok:
16
Fn+1 = Fn + Fn−1
és
F0 = 0, F1 = 1.
A képlet alapján már nagyobb n-re is könnyen kiszámíthatóak lesznek a sorozat tagjai. Viszont ezzel a képlettel ki kell számolni n el®tt az összes tagot mire megkapjuk a kivánt számot. Vajon létezik-e olyan képlet, amellyel csupán n ismeretében ki tudjuk számolni azt a tagot. A kérdésre a választ az alábbi tétel adja meg.
3.3. Tétel.
A Fibonacci-számokra fennáll az alábbi azonosság:
√ !n 1+ 5 − 2
1 Fn = √ 5
√ !n ! 1− 5 2
Erre a tételre három különböz® bizonyítást szeretnék adni, az els® egy egyszer¶ teljes indukciós bizonyítás, a második egy mértani sorozatos és a harmadik bizonyítás generátorfüggvényes. Ez is azt mutatja, hogy milyen sokan foglalkoztak a Fibonacciszámokkal. 1. Bizonyítás. Teljes indukcióval bizonyítsuk. n=0-ra √ !0 1 1+ 5 F0 = √ − 2 5
√ !0 1− 5 1 = √ (1 − 1) = 0 2 5
n=1-re √ !1 1 1+ 5 F1 = √ − 2 5
√ !1 1− 5 1 =√ 2 5 √ 1 2 5 √ · =1 2 5
1+
√
√ ! 5−1+ 5 = 2
Tehát n=0-ra és n=1-re igaz. Az Fn−1 -re és az Fn−2 -re igaz a képlet. A rekurzióból az n ≥ 2-ra a következ® adódik: Fn = Fn−1 + Fn−2 =
√ !n−1 √ !n−1 √ !n−2 √ !n−2 1 1+ 5 1− 5 1− 5 + √1 1 + 5 = √ − − 2 2 2 2 5 5 ! ! √ !n−2 √ √ !n−2 √ 1 1+ 5 1+ 5 1 1− 5 1− 5 √ +1 − √ +1 = 2 2 2 2 5 5
17
1 √ 5 1 √ 5
√ !n−2 √ ! 1+ 5 3+ 5 1 − √ 2 2 5 ! ! √ n−2 √ 2 1+ 5 1+ 5 1 − √ 2 2 5 √ !n 1+ 5 1 1 √ − √ 2 5 5
√ !n−2 1− 5 2 √ !n−2 1− 5 2 √ !n 1− 5 . 2
√ ! 3− 5 = 2 √ !2 1− 5 = 2
(∗)
A (*) egyenl®ség az alábbiak miatt igaz: 1.
√ √ √ 6+2 5 1+2 5+5 3+ 5 = = = 2 4 4
√ !2 1+ 5 2
2.
√ √ √ 3− 5 6−2 5 1−2 5+5 = = = 2 4 4
√ !2 1− 5 2
Ezzel beláttuk a tételt.
2. Bizonyítás. Induljunk ki az n+2-dik tag de níciójából. fn+2 = fn+1 + fn
Tegyük fel, hogy az fn = rn -el. Helyettesítsünk be az egyenletbe, és határozzuk meg a megoldásokat. rn+2 = rn+1 + rn
Átrendezés és rn -nel való egyszer¶sítés után a következ® egyenletet kapjuk: r2 − r − 1 = 0
Másodfokú megoldóképlettel megoldjuk és az alábbi két megoldást kapjuk: √ √ 1− 5 1+ 5 , r2 = r1 = 2 2 √ !n √ !n 1 − 1 + 5 5 Az r1n = , r2n = megoldásoknak a lineáris kombinációja 2 2 is megoldása az egyenletnek. Keressük Fn -t ilyen alakban: (Fn ) = a · (r1n ) + b · (r2n ).
A kezdeti feltételekb®l F0 = 0-ból és F1 = 1-b®l meghatározhatjuk az a-t és a b-t. Tehát
18
I. F0 = 0 = a + b
√ ! 1− 5 2
√ ! 1+ 5 +b 2
II. F1 = 1 = a
Az I. és a II. egyenletb®l azt kapjuk, hogy: 1 1 a = √ , b = −√ 5 5
Ezt visszahelyettesítve az Fn = a · r1n + b · r2n -be, éppen a tételt kapjuk meg.
3. Bizonyítás. Tekintsük a F (x) =
∞ X
Fk xk hatványsort. A Fibonacci-sorozat
k=0
de níciójából könnyen adódik teljes indukcióval, hogy Fn < 2n , emiatt az F (x) hatványsor abszolút konvergens |x| < 21 -re. Ekkor
F (x) = F0 + F1 x +
∞ X
F k xk =
k=2
= x+
∞ X
(Fk−1 xk + Fk−2 xk ) =
k=2 ∞ X
= x+x
Fk−1 xk−1 + x2
∞ X
k=2
Fk−2 xk−2 =
k=2 2
= x(F (x) + 1) + x F (x) = x + (x + x2 )F (x)
Ebb®l az alábbi egyenletet tudjuk felírni F(x)-re F (x) =
x 1 − x − x2
Az 1 − x − x2 polinomot alakítsuk át szorzattá, így a következ®t kapjuk:
F (x) =
x
(1 −
√ 1+ 5 x)(1 2
−
√ 1− 5 x) 2
Parciális törtekre bontjuk: 1 1 1 1 √ √ F (x) = √ −√ = 1+ 5 1− 51− 2 x 5 1 − 2 5x
19
√
Az (1 − 1+2 5 x)−1 függvény sorba fejtése után: √ √ ∞ ∞ X 1 h X 1 + 5 n n 1 − 5 n n i =√ x − x 2 2 5 n=0 n=0 √ ∞ 1 − √5 n i 1 h X 1 + 5 n √ − xn . 2 2 5 n=0
Tehát xn együtthatójára a tételben megadott értéket kapjuk.
A Fibonacci-sorozat tulajdonságai. A Fibonacci-sorozatnak rengeteg tulajdonsága van, így csak néhány érdekesebb tulajdonságot szeretnék kiemelni. 1. A Fibonacci-sorozat egymást követ® tagjainak a hányadosából kapott sorozat határértéke pontosan az aranymetszéshez ϕ ≈ 1, 618033988 . . . -hez tart. Fn+1 =ϕ n→∞ Fn lim
Bizonyítás. Fn+1 Fn + Fn−1 Fn−1 1 1 = lim = 1 + lim =1+ , = 1 + F n n→∞ Fn n→∞ n→∞ Fn Fn x lim Fn−1
x = lim
n→∞
azaz x = x + 1, amelynek a gyökei ϕ és 1 − ϕ. 2
2. A sorozat n-edik tagja eggyel nagyobb, mint az els® n-2 tag összege, azaz Fn = 1 +
n−2 X
Fi .
i=1
Bizonyítás. Alkalmazzuk a rekurzív de níciót többször egymás után: Fn = Fn−1 + Fn−2 = Fn−2 + Fn−3 + Fn−2 = Fn−3 + Fn−4 + Fn−3 + Fn−2 = · · · = Fn−(n−2) + Fn−(n−1) + Fn−(n−2) + Fn−(n−3) + · · · + Fn−3 + Fn−2
Amit egyszer¶bben így írhatjuk fel: Fn = F2 + F1 + F2 + F3 + F4 + · · · + Fn−3 + Fn−2
20
Mivel a jobb oldali összeg els® tagja F2 = 1, ezért Fn = 1 +
n−2 X
Fi .
i=1
Ezzel bebizonyítottuk ezt a tulajdonságok.
3. Az els® n tag négyzetösszege egyenl® az n-dik és (n+1)-dik tag szorzatával, azaz: n X
Fi2 = Fn Fn+1
i=1
Bizonyítás. Ennek a tulajdonságnak a bizonyításához a sorozat de níciójából induljunk ki. Fn+1 = Fn + Fn−1
Amit rendezzük úgy, hogy a bal oldalon Fn álljon Fn = Fn+1 − Fn−1
Ezt az egyenl®séget szorozzuk fel Fn -el, így az alábbi egyenl®séget kapom: Fn2 = Fn (Fn+1 − Fn−1 )
Most alkalmazzuk egymás után ezt a rekurziós feltevést: F12 +F22 +F32 +· · ·+Fn2 = F12 +F2 (F3 −F1 )+F3 (F4 −F2 )+· · ·+Fn (Fn+1 −Fn−1 ) = F12 + F2 F3 − F2 F1 + F3 F4 − F3 F2 + F4 F5 − F3 F4 + · · · + Fn Fn+1 − Fn Fn−1 .
Ha jobban megnézzük ezt az egyenl®séget, akkor látjuk, hogy sok tag kiesik és csak az els®, harmadik és az utolsó el®tti tag marad meg, így ezt kapjuk: n X
Fi2 = F12 − F2 F1 + Fn Fn+1 = 1 − 1 + Fn Fn+1 = Fn Fn+1
i=1
Ezzel beláttuk ezt a tulajdonságot.
21
Általánosított Fibonacci-sorozat A Fibonacci-sorozat általánosabb formájában adott egy olyan g sorozat, amely a gn+2 = gn + gn+1 rekurzív képletet kielégíti. Nyílvánvalóan minden ilyen sorozat átírható olyan alakra, hogy gn = aFn + bFn+1 . 1. Lucas-számok A Fibonacci-típusú sorozatok el®állításának egyik módja, amikor a rekurzivitási tulajdonságot változatlanul hagyva, az els® két elem értékét változtatjuk meg. A Lucas-számok is ilyen típusú számok.
3.4. De níció.
Lucas számok:
L0 = 2, L1 = 1
és
Ln+2 = Ln + Ln+1 ,
ha n>2.
Néhány összefüggés a Fibonacci és a Lucas számok között: (a) Ln = Fn−1 + Fn+1 Bizonyítás. Teljes indukcióval fogom bizonyítani. Ellen®rizzük az állítást, hogy n = 1-re igaz-e. L1 = 1 = F0 + F2 = 0 + 1
√
Tegyük fel, hogy k-ig igaz az állítás. Ekkor be kell látni, hogy k+1-re is igaz is. Lk+1 = Lk−1 + Lk = Fk−2 + Fk + Fk−1 + Fk+1 = (Fk−2 + Fk−1 ) + (Fk + Fk+1 ) = Fk + Fk+2
Ezzel beláttuk az állítást. 1
(b) Fn = (Ln−1 + Ln+1 ) 5 Bizonyítás. Teljes indukcióval fogom bizonyítani. Ellen®rizzük az állítást n=1-re. √ 1 1 F1 = 1 = (L0 + L2 ) = (2 + 3) = 1. 5 5
22
Tegyük fel, hogy az állítás k-ig igaz. Ekkor be kell látni k+1-re is.
Fk+1 = Fk + Fk−1 1 1 (Lk−1 + Lk+1 ) + (Lk−2 + Lk ) = 5 5 1 = (Lk−1 + Lk−2 + Lk+1 + Lk ) 5 1 = (Lk + Lk+2 ) 5
Ezzel beláttuk ezt az állítást.
A következ® tulajdonságokat érdekességként, bizonyítás nélkül írom le: 1 2 (d) F2n = Fn Ln 1 (e) Fm+n = (Fm Ln + Fn Lm ) 2 1 (f) Fm−n = (−1)n (Fm Ln − Fn Lm ) 2
(c) Fn+1 = (Fn + Ln )
2. Polibonacci-számok Hasonlóan számoljuk a Fibonacci számokhoz, csak kett® helyett három, négy vagy több elemet adunk össze. Amikor három elemet adunk össze, azt tribonacci-számoknak nevezzük és a tagjai 1, 1, 2, 4, 7, 13, 24, 44, 81, . . . .
3.5. De níció. ··· =
k-ad rend¶ Fibonacci-sorozatnak nevezzük az
(k)
F0
(k) Fk−1 kezd®értékkel az alábbi sorozatot.
Fn(k)
=
(k) Fn−1
+
(k) Fn−2
+ ··· +
(k) Fn−k
=
k X i=1
23
(k)
Fn−i ,
ahol
(n ≥ k)
(k)
= F1
=
3.6.
Catalan-számok
A leggyakrabban úgy szokták bevezetni a Catalan számokat, hogy hányféleképpen zárójelezhet® egy (n+1) tényez®s szorzat (n-1) zárójelpár felhasználásával. Jelöljük ezeket a számokat Cn -nel. Nézzünk rá pár példát, hogy mit is jelent ez tulajdonképpen. Legyen n=1, ezt egyféleképpen lehet zárójelezni (a · b). Legyen n = 2 ekkor két lehet®ség van (a · b) · c és a · (b · c), azaz C2 = 2. Ha n=3, akkor ((a · b) · c) · d, (a · (b · c)) · d, a · ((b · c) · d), a · (b · (c · d)) és (a · b) · (c · d), azaz C3 = 5. Így a Catalan számok sorozata a következ®: C0 = 1, C1 = 1, C2 = 2, C3 = 5, C4 = 14, C5 = 42, C6 = 132, ...
3.7. Tétel. C1 = 1 és n ≥ 2 egész szám, akkor Cn =
n−1 X
Ck Cn−k−1
k=0
Bizonyítás. Meg gyelhet®, hogy egy szorzásjel mindig a zárójelen kívül esik. Ha ez a szorzásjel a k-adik és a (k+1)-dik tag közé esik, akkor az el®tte lév® változók pontosan Ck -féleképpen zárójelezhet®ek még az utána lév® (n-k) tag pedig Cn−k−1 féleképpen. Így a lehet®ségek száma k-ra összegezve
n−1 X
Ck Cn−k−1
k=0
3.8. Tétel.
A Catalan számokat a következ®képpen írhatjuk fel:
1 2n Cn = n+1 n
Bizonyítás. Legyen a c(x) =
∞ X
C n xn .
n=1
Ezt a kifejezést négyzetre emelve (c(x))2 = C1 C1 x2 + (C2 C1 + C1 C2 )x3 + ... = c(x) − x. Ebb®l c(x)-et kifejezve, gyelembe véve, hogy c(x)-ben konstans tag nem szerepel. c(x) =
1−
√ 1 − 4x 2
Newton általánosított binomiális tétele alapján felírható, hogy ∞ X √ 1 1 − 4x = (1 − 4x) 2 =
1 2 (−4x)k k k=0
24
Ezt visszahelyettesítve c(x)-be: " # ∞ 1 X 1 2 (−4x)k c(x) = 1− 2x k k=0 ∞ 1 X 1 2 (−4)k (x)k = − 2x k=1 k ∞ 1 X 12 = − (−4)k (x)k−1 2 k=1 k
Az n = k − 1 helyettesítéssel az alábbi képletet kapjuk c(x)-re: c(x) = 2
∞ X n=0
1 2
n+1
(−4)n xn
Alakítsuk át a binomiális együtthatót
1 2
n+1
1 1 = (n + 1)! 2
1 3 2n − 1 1 · 3 · 5 . . . (2n − 1) − − ... − = (−1)n 2 2 2 (n + 1)! · 2n+1
Ahhoz, hogy a számlálóban (2n)! állhasson, ahhoz el kell osztani 2 · 4 . . . (2n)-el, mert így nem változtatunk a tört értékén. (−1)n
2n+1 (n
(2n)! = + 1)! · 2 · 4 · 6 . . . (2n)
Emeljük ki a 2 · 4 · 6 · 8 . . . 2n mindegyik tagjából a 2-t. (−1)n
2n+1 (n
(2n)! (2n)! = (−1)n 2n+1 = n + 1)!2 (1 · 2 · 3 · 4 . . . n) 2 (n + 1)!n!
Alakítsuk szorzattá a törtet és az (n + 1)! helyett írjunk (n + 1) ∗ n!-t (−1)n
1 22n+1 (n
2n! + 1) n! · n!
Ebb®l az alábbi egyenl®ség adódik:
1 2
n+1
1 2n = n 2 · (−4) (n + 1) n
Ezt visszahelyettesítve c(x)-be c(x) = 2
∞ X n=0
∞ X 1 2n 1 2n n n n (−4) x = x n 2 · (−4) (n + 1) n n+1 n n=0
Tehát az xn -nek az együtthatója pontasan a Cn képlete.
Tulajdonságok. 1. Állítás. Cn kiszámításának alternatív módja: 25
2n 2n Cn = − , ahol n ≥ 1. n n−1
Bizonyítás. A binomiális eggyüttható faktorizációs alakjából induljunk ki. 2n 2n (2n)! (2n)! − = − n n−1 n! · n! (n − 1)! · (n + 1)!
Hozzuk közös nevez®re és emeljük ki a számlálóban a (2n)!. (n + 1) · (2n)! − n · (2n)! (n + 1 − n) · (2n)! 1 (2n)! 1 2n = = · = n! · (n + 1)! (n + 1) · n! · n! n + 1 n! · n! n+1 n
Ez a de níció alapján éppen a Cn .
2. Állítás.
n 2 1 X n Felírható a következ® rekurzív sorozattal: Cn = n + 1 i=0 i
Bizonyítás. A bizonyítást két részre fogom bontani, az els® részben bebizonyítom a Vandermonde-azonosságot, a második részben pedig megmutatom, hogy következik bel®le az állítás. (a) Vandermonde-azonosság. 0 ≤ r, r ≤ m és r ≤ n m n m n m n m n m+n + + +· · ·+ = . 0 r 1 r−1 2 r−2 r 0 r
Vandermonde-azonosság bizonyítása. Vegyünk egy A és egy B halmazt, amelyeknek az elemszáma m és n. Legyen az A∩B = ∅. Számoljuk meg, hogy hány r elem¶ részhalmaza van A ∪ B -nek? Egyrészt az A ∪ B elemszáma m + n, melyb®l kiválasztunk r elem¶ részhalmazt, ami m+n . r Másrészt, minden r elem¶ részhalmazt megkapunk úgy, hogy vegyük az A-nak az összes lehetséges módon a k elem¶ részhalmazát, B-nek egy r-k elem¶ részhalmazát és képezzük ezek unióját, ahol 0 ≤ k ≤ r. A lehet®ségek száma éppen a bal oldali összeg. (b) A Vandermonde-azonosságban legyen m=n, r=n és használjuk a binomi ). ális együtthatók szimmetria-tulajdonságát( nk = m−k n Így azt kaptuk, hogy
n 2 X n i=0
i
Ezzel a helyettesítéssel Cn =
2n = . n n 2 1 X n
n+1
26
i=0
i
2n 1 = . n+1 n
3. Állítás. A Catalan-számok egy kiszámítási módja: C0 = 1 és Cn+1 =
2(2n + 1) Cn . n+2
Bizonyítás. Induljunk ki a Catalan-számok de níciójából. Cn+1
1 2n + 2 1 (2n + 2) · (2n + 1) · (2n)! = = n+2 n+1 n + 2 (n + 1) · n! · (n + 1) · n!
Egyszer¶títés után már könnyen látható, hogy az állítás igaz. Cn+1 =
1 2 · (2n + 1) · (2n)! 2 · (2n + 1) 1 (2n)! 2(2n + 1) = = Cn . n + 2 (n + 1) · n! · n! n + 2 n + 1 n! · n! n+2
4. Azok a Catalan-számok páratlanok, ahol igaz, hogy n = 2k − 1, a többi páros. 5. A Catalan-számoknak egy integrálos reprezentációja: Z Cn = 0
4
1 x 2π n
r
4−x dx. x
A Catalan számokat leginkább a kombinatorikában használják. Az alábbi feladatokban megmutatom két lehetséges felhasználását.
1.Feladat. Egy n oldalú konvex sokszöget, hányféleképpen lehet felbontani háromszögekre az átlóival úgy, hogy az átlók nem metszik egymást? Megoldás. A keresett számot jelölje En és megállapodás szerint az E2 legyen 1. A háromszögnek nincs átlója így 1-féleképpen lehet háromszögekre bontani, tehát E3 = 1. A négyszögeknek két átlójuk van és ezeket behúzva 2-féleképpen lehetséges háromszögekre bontani, azaz E4 = 2. Tekintsünk egy n oldalú sokszöget,melynek csúcsai legyenek A1 , A2 , A3 , . . . , An . Húzzuk be az A1 Ak és Ak An átlókat, ekkor az átlók az n-szöget három részre bontják, egy A1 , A2 , . . . , Ak k-szögre, egy A1 Ak An háromszögre és egy Ak Ak+1 . . . An (n-k+1)-szögre.
27
Mivel a k-szöget Ek -féleképpen, az (n-k+1) szöget En−k+1 -féleképpen bonthatjuk fel háromszögekre, ezért az A1 Ak An háromszöget tartalmazó háromszögekre bontások száma Ek En−k+1 , ahol 2 ≤ k ≤ n − 1. Tekintsük az összes lehetséges háromszögekre bontást:
n−1 X
Ek En−k+1 , ahol n ≥ 3.
k=2
Ha feladatban n oldalú sokszög helyett (n+2) oldalú sokszöget tekintünk, akkor azt kapjuk, hogy En+2 =
n+1 X
Ek En−k+3 . Legyen En0 = En+2 , ebben az esetben a
k=2
következ®képpen alakul a szumma: En0
=
n+1 X
0 0 Ek−2 En−k+1 ,azaz
k=2
En0
=
n+1 X
0 Ej0 En−j−1
j=0
ami nem más mint a Catalan számok de níciója. Tudjuk, hogy a kezdeti érték E10 = 1 = E3 = C1 ebb®l következik, hogy az En0 = Cn -el ∀ n ≥ 1-re. Tehát az n oldalú sokszög háromszögekre bontására a következ® képletet kapjuk: En = Cn−2
2n − 4 1 ,n ≥ 3 = n−1 n−2
2.Feladat Egy nxn-es sakktáblán, hányféleképpen juthatunk el a bal alsó sarokból a jobb fels® sarokba úgy, hogy egyszerre egyet léphetünk jobbra vagy felfelé és a mellékátló (a bal alsó sarkot és a jobb fels® sarkot összeköt® vonal) fölé nem léphetünk? Megoldás. Jelölje an az összes lehetséges utak számát és bn a mellékátló alatt maradó utak számát. Kicsi n-ekre könnyen látszik,hogy a1 = 1, a2 = 2, a3 = 6, a4 = 10, . . . és a b1 = 1, b2 = 1, b3 = 2, b4 = 5, . . . . Legyen a bal alsó sarok A és a jobb fels® sarok B. Számoljuk meg an -t, azaz az összes olyan út számát, amely A-ból B-be megy. Ez pontosan an = 2n−2 , mert n−1 2n−2 lépésre van szükség ahhoz, hogy eljussunk A-ból B-be, és ebb®l n−1-et jobbra és n−1-et felfelé teszünk meg. A 2n−2-b®l ki kell választani n−1-et, amikor jobbra lépünk. A jó utak megszámolása egyszer¶bb, ha úgy számoljuk, hogy az összes utak száma mínusz a rossz utak száma. Minden rossz út a mellékátló fölé kerül, tehát az ábrán látható e egyenest metszi. Egy rossz út els® metszéspontja legyen P, így egy rossz út az A-P és a P-B részekb®l áll. Tükrözzük az A-P törött vonalat az e egyenesre, melynek a tükörképe A0 -P. Ekkora az A0 -B utat az A0 -P és a P-B alkotja. Bijektív megfeleltetés van az A-B rossz utak és az A0 -B utak között. Az A0 -b®l B-be 28
men® utak száma lépünk.
2n−2 n
, mert 2n-2 lépésb®l megadjuk azt az n-et, amikor jobbra
2n − 2 2n − 2 Így a jó utak száma: bn = − = Cn−1 n−1 n
Ez az els® tulajdonság alapján pontosan megeggyezik a (n-1)-edik Catalanszámmal.
29
Köszönetnyilvánítás
Ezúton szeretnék köszönetet mondani témavezet®mnek, Ágoston Istvánnak, aki szakértelmével és hasznos tanácsaival segítette a szakdolgozatom elkészülését. Hálával tartozom továbbá családomnak és barátaimnak, hogy megértéssel és türelemmel segítettek az egyetemi éveim alatt, minden helyzetben mellettem álltak és tartották bennem a lelket a legnehezebb helyeztekben. Köszönöm mindenkinek!
30
Irodalomjegyzék
[1] Steven R. Finch: Mathematical Constans, Cambridge University Press, 2003. [2] Freud Róbert, Gyarmati Edit: Számelmélet, Nemzeti Tankönyvkiadó, 2006. [3] Sain Márton: Nincs királyi út!, Gondolat Budapest, 1986 [4] Szakács Erzsébet: Arany arány, elektronikus jegyzet, amely megtekinthet®: http://szrg.hu/wp-content/uploads/ les/aranymetszes.pdf [5] http://hu.wikipedia.org/wiki/Aranymetszés [6] Buzás Ferenc: Az aranymetszés vizuális világa, 2010. (letölthet® könyv) [7] Ger®cs László: A Fibonacci-sorozat általánosítása, Scolar Kiadó, 1998. [8] Katona Gy. - Recski A. - Szabó Cs. : A számítástudomány alapjai, Typotex Kiadó, 2006. [9] http://en.wikipedia.org/wiki/Catalan_number [10] Király Balázs, Tóth László: Kombinatorika jegyzet és feladatgy¶jtemény, elektronikus jegyzet, amely megtekinthet®: http://tamop412a.ttk.pte.hu/ les/Kombinatorika_kesz_jav3_ nal.pdf [11] Pelikán József 2006. november 23-ai el®adása nyomán készített jegyzet Török Lajos és Hraskó András által. Megtalálható: http://matek.fazekas.hu/portal/eloadas/2006/eloadas_2006_11_21_pelikan.pdf [12] http://hu.wikipedia.org/wiki/Catalan-állandó [13] http://en.wikipedia.org/wiki/Euler-Mascheroni_constant [14] http://hu.wikipedia.org/wiki/Brun-konstans [15] http://asgarli.wordpress.com/2012/07/02/existence-of-euler-mascheroniconstant/ 31
[16] http://hu.wikipedia.org/wiki/Fibonacci-számok [17] http://en.wikipedia.org/wiki/Coupon_collector's_problem [18] Hajós György: Bevezetés a geometriába, Tankönyvkiadó, 1972.
32
