Kettingbreuken Fr´ed´eric Guffens 20 april 2010
1
K+
1
E+
1
T+
1
T+
1
I+
1
N+
1
G+
1
B+
1
R+
1
E+
1
U+ K+
1 E+
1
2+
1
0+
1
A+
1
P+
1
R+
1
I+
1
L+
1
2+ 0+
1 1+
1
1 0
1 N
1
Wat zijn Kettingbreuken? • Een kettingbreuk is een wiskundige uitdrukking van de vorm: 1
a0 +
1
a1 +
1
a2 +
a3 +
1 ...
waarbij a0 ∈ Z, en alle andere elementen natuurlijke getallen zijn. • Kettingbreuken kunnen zowel eindig als oneindig zijn. Een eindige kettingbreuk stelt een rationaal getal voor, en elk rationaal getal kan op precies 2 manieren geschreven worden als een kettingbreuk, waarover later meer. Elke oneindige kettingbreuk stelt een irrationaal getal voor, en elk irrationaal getal kan precies op 1 manier geschreven worden als een kettingbreuk. • Een voorbeeld van een eindige kettingbreuk is: 1
−3 +
1
6+
13 +
1 4
Een voorbeeld van een oneindige kettingbreuk is: 1
−3 +
1
6+ 13 +
1 4+
1 ...
• Er zijn verschillende notatiemogelijkheden om kettingbreuken verkort weer te geven: 1. x =< a0 ; a1 , a2 , a3 , . . . > 1 1 1 1 1 2. x = a0 + a1 +a2 +a2 +a3 + . . .
2
3. x = a0 +
1| 1| 1| 1| + + + |a1 |a2 |a3 . . .
Dit noemt men de notatie van Pringsheim, een invloedrijke Duitse wiskundige uit de 19de -20ste eeuw. 4. x = [a0 ; a1 , a2 , a3 , . . .] Deze notatie is ingevoerd door Oskar Perron. Perron was een Duits wiskundige die vele bijdragen heeft geleverd aan differentiaalvergelijkingen. Deze notatie zal in de rest van het verslag gebruikt worden.
2
Kettingbreuken bepalen
2.1
Kettingbreuken van rationale getallen
We gaan nu proberen een rationaal getal te schrijven als een kettingbreuk. De makkelijkste manier om te tonen hoe je dit het best doet, is aan de hand van een voorbeeld: 0, 345 = 0 +
1 1 1 345 =0+ =0+ =0+ 1000 310 1 1000 2+ 2+ 345 345 345 310 1
=0+ 2+
1+
35 310
1
= 0+
1+
2+ 1+
1
1 8+ 35 30 0, 345 = [0; 2, 1, 8, 1, 6]
1
=0+
1
8+
8+
1 1
2+
1
1+
30 35
= 0+
1
1
1+
1 1+
3
1
1+
1 2+
1
2+
1 310 35
= 0+
1
2+
1
=0+
1
5 30
8+
1 1+
1 6
We kunnen dit ook korter noteren: 345 = 0 · 1000 + 345 1000 = 2 · 345 + 310 345 = 1 · 310 + 35 310 = 8 · 35 + 30 35 = 1 · 30 + 5 30 = 6 · 5 + 0
De getallen in het rood zijn juist die getallen die de kettingbreuk van 0, 345 bepalen.
2.2
Kettingbreuken van tweedegraadswortels
Ook hier is het het simpelste om het uit te leggen aan de hand van een voorbeeld. √ √ 1 3=1+ 3−1=1+ 1 √ 3−1 √ Nu vermenigvuldigen we de onderste breuk boven en onder met 3 + 1: 1 1 √ =1+ √ =1+ 3+1 1+1+ 3−1 2 2
=1+
1 1 √ =1+ 1 3−1 1+ 1+ 2 2 √ 3−1
We vermenigvuldigen de onderste breuk boven en onder met √
1
3=1+ 1+
1 √ 2+2 3 2 4
1
=1+ 1+
1 √ 1+ 3
√ 3 + 1:
Nu kunnen we de vergelijking in zichzelf invullen. Op de plaats van dan de tot nu geconstrueerde kettingbreuk, zodat: √ 3=1+
1
1
1+
1
1+1+
1
=1+
1
1+
1 √ 1+ 3 √ 3 = [1; 1, 2, 1, 2, 1, 2, 1, 2, . . .] 1+
√ 3 komt
1
2+ 1+
1 √ 1+ 3
Alle tweedegraadswortels hebben periodieke kettingbreuken. Dit is bewezen door Leonard Euler in 1737. Het bewijs hiervan valt buiten het bestek van dit verslag wegens te lang en te moeilijk.
3 3.1
Eindige kettingbreuken Voorstelling rationaal getal
Elke kettingbreuk stelt een rationaal getal voor, en elk rationaal getal kan geschreven worden op precies 2 verschillende manieren als een kettingbreuk. Deze 2 voorstellingen zijn dezelfde, buiten hun laatste term. Voorbeeld: −4, 2 =
4 1 1 − 21 = −5 + = −5 + = −5 + = [−5; 1, 4] 5 5 5 1 1+ 4 4 1 = −5 + = [−5; 1, 3, 1] 1 1+ 1 3+ 1
Om de korte manier te bepalen, laten we de laatste 1 vallen, maar vermeerderen we de voorlaatste term met 1. In symbolen: [a0 ; a1 , a2 , . . . , an , 1, ] = [a0 ; a1 , a2 , . . . , an + 1] 5
Op deze manier is elke breuk uniek als een eindige kettingbreuk. Dat de kettingbreuk uniek is, blijkt wel uit de methode. Het eindige is niet zo moeilijk in te zien. Je houdt immers steeds een rest pq over die tussen 0 en 1 ligt, oftewel 0 ≤ p < q. Als p = 0 of p = 1 ben je klaar en is de kettingbreuk zeker eindig. Als p > 1 schrijf je pq als 1q . Dan neem je de entier1 van pq en hou je p
q0 p
0
over met q < p < q. Je ziet dat zowel teller als noemer van de een rest rest in de volgende stap strikt kleiner zijn dan in de huidige stap. Aangezien teller en noemer natuurlijke getallen zijn kom je in een eindig aantal stappen in de situatie dat p = 0 of p = 1 terecht.
3.2
Kettingbreuken van omgekeerde evenredige getallen
De voorstelling van een kettingbreuk ([a0 ; a1 , a2 , a3 , . . .]) van een positief rationaal getal p en de voorstelling van het omgekeerde evenredige getal ( p1 ) zijn gelijk, buiten dat alle ai ’s ´e´en plaats naar rechts of links verschoven zijn, afhankelijk of p groter of kleiner is dan ´e´en. Voorbeeld: 27 =6+ 4
1
= [6; 3, 3] 1 3+ 3 1 4 1 = = = [0; 6, 3, 3] 6, 75 27 1 6+ 1 3+ 3
6, 75 =
1
De entier van een re¨eel getal x is het grootste gehele getal kleiner of gelijk aan x.
6
Bewijs: ? x > 1: x = a0 +
1
= [a0 ; a1 , . . .] 1 a1 + ... 1 1 =0+ = [0; a0 , a1 , . . .] x 1 a0 + 1 a1 + ...
? x < 1: 1
x=0+ a1 +
a2 + 1 = a1 + x
4
= [0; a1 , a2 , . . .]
1
1 1 a2 + ...
1 ... = [a1 ; a2 , . . .]
Oneindige kettingbreuken en convergenten
4.1
Oneindige ketingbreuken
Elke oneindige kettingbreuk stelt precies ´e´en irrationaal getal voor, en elk irrationaal getal kan op precies 1 manier geschreven worden als een kettingbreuk. De oneindige kettingbreuken laten zich nog opdelen in periodieke en aperiodieke kettingbreuken.
4.2
Convergenten
• Als we slechts een deel beschouwen van een oneindige kettingbreuk (of een eindige kettingbreuk voor het einde afbreken), hebben we te maken met een benadering van de gehele kettingbreuk. Een dergelijk voortijdig afgebroken deel noemen we een convergent. De n-de convergent is opgebouwd uit de getallen a0 , a1 , a2 , . . . , an .
7
• De opeenvolgende convergenten vormen een rij breuken die steeds beter de originele kettingbreuk zullen gaan benaderen. De convergenten met een even index zijn kleiner dan het rationaal getal dat ze benaderen, deze met een oneven index groter. Zie stelling 5.3 voor het bewijs hiervan.
• Voor elke kettingbreuk zijn de eerste 3 opeenvolgende convergenten: ?
a0 1
a1 a0 + 1 1 = a1 a1 1 1 a2 a0 a1 a2 + a0 + a2 = ? a0 + = a0 + = a0 + a2 a1 + 1 a2 a1 + 1 1 a2 a1 + 1 a1 + a2 a2 a2 (a0 a1 + 1) + a0 = a2 a1 + 1 ? a0 +
De noemer van de vierde convergent wordt gevormd door de noemer van derde convergent te vermenigvuldigen met a3 en dit te vermeerderen met de noemer van de tweede convergent. De teller wordt op dezelfde wijze gevormd. De opeenvolgende convergenten worden gevormd door de formule: pk ak pk−1 + pk−2 = qk ak pk−1 + qk−2 Hierbij is pk de noemer van de n-de convergent, en qk de teller van de n-de convergent. Zie stelling 5.1 voor het bewijs hiervan. 8
4.3
Enkele verbazende eigenschappen:
De meeste oneindige kettingbreuken hebben geen periodieke kettingbreukontwikkeling en zijn dus volstrekt willekeurig. Wel zijn er enkele verbazende eigenschappen: • Constante van Khinchin: Aleksandr Khinchin bewees dat voor bijna elk getal x geldt dat het meetkundige gemiddelde2 van de getallen ai van een welbepaalde kettingbreuk gelijk is aan een constante, de constante van Khinchin. Het is ongeveer gelijk aan 2,68545. n Y 1 In symbolen: K0 = lim ( ai ) n n→∞
i=1
Voorbeeld: 1
π =3+
1
7+
1
15 +
1
1+
1 1 + ... De meetkundige gemiddelden zijn: 3; 4, 58; 6, 8; 4, 2; 5, 7; 4, 2; 3, 47; 2, 97; 2, 84; 2, 56; . . . Deze rij nadert inderdaad de constante van Khinchin. 292 +
• Constante van L´evy: De n-de-machtswortels uit de noemers van de n-de convergent van bijna alle re¨eele getallen convergeren naar dezelfde limiet, de constante van L´evy. Deze constante bedraagt ongeveer 3,2759229. 1 π2 In symbolen: lim qnn = e 12 ln 2 = 3, 2759229 n→∞
• Soms treffen we patronen aan in aperiodieke oneindige kettingbreuken. Enkele voorbeelden: e = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, . . .] φ = [1; 1, 1, 1, 1, 1, . . .] tan(1) = [1; 1, 1, 1, 3, 1, 5, 1, 7, 1, 9, . . .]
2
Het meetkundig gemiddelde van n getallen wordt verkregen door deze getallen met elkaar te vermenigvuldigen en vervolgens van het product de n-de-machtwortel te nemen.
9
5
Stellingen
5.1
Stelling 1:
Als a0 , a1 , a2 , . . . een oneindige rij voorstelt, waarbij a0 een geheel getal is, en de rest natuurlijke getallen voorstellen, geldt: pk ak pk−1 + pk−2 p = 1 p−2 = 0 p0 = a0 = , en waarbij −1 q−1 = 0 q−2 = 1 q0 = 1 qk ak pk−1 + qk−2 Hierbij is pk de teller van de k-de convergent, en qk de noemer van de k-de convergent. Bewijs: We gaan dit bewijzen door middel van volledige inductie. ? k = 0: p0 a0 p−1 + p−2 p0 = a0 , en = a0 = , voor n = 0 klopt het. q0 a0 q−1 + q−2 q0 ? Neem aan: pk ak pk−1 + pk−2 = qk ak qk−1 + qk−2 ? Te bewijzen: pk+1 ak+1 pk + pk−1 = qk+1 ak+1 qk + qk−1 We weten dat we door ak +
pk+1 = qk+1
1 ak+1
(ak +
pk+1 pk uit kunnen vormen, door alle ak ’s vervangen qk+1 qk
, en teller en noemer te vermenigvuldigen met ak+1 . Dus: 1
)pk−1 + pk−2
ak+1 1 (ak + )qk−1 + qk−2 ak+1 ak+1 pk + pk−1 = ak+1 qk + qk−1
pk−1 pk−1 (pk + )ak+1 ak+1 ak+1 = = qk−1 qk−1 ak qk−1 + qk−2 + (qk + )ak+1 ak+1 ak+1 ak pk−1 + pk−2 +
10
5.2
Stelling 2:
Voor ieder afgekapte kettingbreuk geldt voor k ≥ 0 dat: pk−1 qk − pk qk−1 = (−1)k , en waarbij:
p−1 = 1 p−2 = 0 p0 = a0 q−1 = 0 q−2 = 1 q0 = 1
Bewijs: We gaan dit wederom bewijzen door volledige inductie. ? k=0: p−1 q0 − p0 q−1 = 1 ∗ 1 − a0 ∗ 0 = 1 − 0 = (−1)0 , voor k = 0 klopt het. ? Neem aan: pk−1 qk − pk qk−1 = (−1)k ? Te bewijzen: pk qk+1 − pk+1 qk = (−1)k+1 We gaan kijken naar: pk qk+1 − pk+1 qk pk pk+1 pk ak+1 pk + pk−1 = − = − qk qk+1 qk qk+1 qk ak+1 qk + qk−1 pk qk−1 − pk−1 qk (−1)(pk−1 qk − pk qk−1 ) = = qk (ak+1 qk + qk−1 ) qk qk+1 k k+1 (−1)(−1) (−1) = = qk qk+1 qk qk+1 Hiermee is het bewijs geleverd.
11
5.3
Stelling 3:
De convergenten met een even index zijn kleiner dan het rationaal getal dat ze benaderen, deze met een oneven index zijn groter dan het rationaal getal dat ze benaderen.
Bewijs: ? We zullen eerst bewijzen dat ck − ck−2 =
ck − ck−2 =
ak (−1)k : qk−2 qk
pk pk−2 pk qk−2 − pk−2 qk − = qk qk−2 qk−2 qk
=
(ak pk−1 + pk−2 )qk−2 − pk−2 (ak qk−1 + qk−2 ) ak (pk−1 qk−2 − pk−2 qk−1 ) = qk−2 qk qk−2 qk
=
ak (−1)k−2 ak (−1)k = qk−2 qk qk−2 qk
? Stel k is even: ck − ck−2 =
ak (−1)k , dus ck > ck−2 qk−2 qk
We zien dat even convergenten steeds groter worden. 12
? Stel k is oneven: ck − ck−2
ak (−1)k < 0, dus ck < ck−2 = qk−2 qk
We zien dat oneven convergenten steeds kleiner worden. Nu moeten we nog aantonen dat een willekeurige oneven convergent groter is dan een willekeurige even convergent. Laten we het eerst aantonen voor convergenten waarvan de index maar 1 verschilt: c2n+1 − c2n =
(−1)(2n+1)−1 > 0, dusc2n+1 > c2n qk−1 qk
Een oneven convergent is dus steeds groter dan de even convergent met een index lager. ? Laten we hierna het algemene geval doen. Stel dat c2n+1 een oneven convergent is, en dat c2m een even convergent is. Dan geldt: c2n+1 > c2n+2m+1 > c2n+2m > c2m De eerste ongelijkheid is juist, omdat oneven convergenten in waarde afnemen. De tweede ongelijkheid klopt, aangezien we dit hebben aangetoond. De laatste ongelijkheid is waar, omdat even convergenten in waarde toenemen. Hiermee is het bewijs geleverd.
6
Bronnen: ? http://www.math.ru.nl/ bosma/Students/ReneeBScriptie.pdf ? http://en.wikipedia.org/wiki/Continued-fraction ? http://www.wiskundemeisjes.nl/20060719/khinchin-en-kettingbreuken/ ? http://www-math.mit.edu/phase2/UJM/vol1/COLLIN 1.PDF ? http://archives.math.utk.edu/articles/atuyl/confrac/
13
