\[ 1 \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad 1\]
Nu drar vi igång en process där det i princip kommer att hamna oändligt många tal på raden mellan ettorna. Man får hålla på tills man tröttnar eller det inte får plats fler. Regeln är att när det står två tal bredvid varandra, och med bredvid menas då att inga andra tal står mellan dem, så får man skriva deras summa någonstans i mellanrummet. Annorlunda uttryckt: Man får skriva in ett tal var man vill, och när man har bestämt sig för var det ska stå, så tittar man till höger och till vänster, och tar summan av de två talen.
Vi skriver alltså en tvåa mellan ettorna:
\[ 1 \qquad \qquad \qquad \qquad \qquad 2 \qquad \qquad \qquad \qquad \qquad 1\]
Och sedan två stycken treor i de nya mellanrummen:
\[ 1 \qquad \qquad \quad 3 \quad \qquad \qquad 2 \qquad \qquad \quad 3 \quad \qquad \qquad 1\]
I nästa steg blir det
\[ 1 \qquad \quad 4 \quad \qquad 3 \quad \qquad 5 \qquad \quad 2 \qquad \quad 5 \qquad \quad 3 \quad \qquad 4 \qquad \quad 1\]
Och sedan
\[ 1 \quad 5 \quad 4 \quad 7 \quad 3 \quad 8 \quad 5 \quad 7 \quad 2 \quad 7 \quad 5 \quad 8 \quad 3 \quad 7 \quad 4 \quad 5 \quad 1\]
och sedan
\[ 1 6 5 9 4 11 7 10 3 11 8 13 5 12 7 9 2 9 7 12 5 13 8 11 3 10 7 11 4 9 5 6 1\]
Efter ett tag verkar det som om vissa tal har en tendens att förekomma oftare än andra. Talen bildas ju genom att vi summerar två tal som vi redan har, men det är nästan som om de tal som inte uppkommer genom multiplikationer nu kompenserar det genom att uppstå i additioner. 7 och 11 finns redan med fyra gånger var, och fler blir det, medan 6 bara har kommit med så som alla tal till slut måste, bredvid de ursprungliga ettorna i sjätte steget.
Eftersom talen bara blir större och större, inser man att varje tal bara kommer att finnas med ett ändligt antal gånger. Om vi räknar de ursprungliga två ettorna som steg 1, kommer alla tal som bildas i steg $n$ att vara minst $n$ (bevisas med induktion!). Så efter $n$ steg kommer talet $n$ inte att bildas mer. Vi skulle därför kunna göra en tabell över hur många gånger varje tal förekommer:
| $n$ | Antal förekomster |
|---|---|
| 1 | 2 |
| 2 | 1 |
| 3 | 2 |
| 4 | 2 |
| 5 | 4 |
| 6 | 2 |
Om man bara är intresserad av att utöka den här tabellen något, kan man spara plats genom att i steg $n$ bara ta med talet $n$, och vänta med att fylla i alla större tal tills det blir deras tur. Då skulle vi få, efter 7 steg:
\[ 1 7 6 5 4 7 3 5 7 2 7 5 3 7 4 5 6 7 1 \]
Nu fyller vi i 8 på de fyra ställen där det blir 8: $1+7$, $3+5$, $5+3$, och $7+1$.
\[ 1 8 7 6 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 6 7 8 1 \]
Sedan fyller vi i 9 på de 6 ställen där det blir 9, och så håller vi på upp till 12, säg.
\[ 1 12 11 10 9 8 7 6 11 5 9 4 11 7 10 3 11 8 5 12 7 9 11 2\dots \] \[ \dots 11 9 7 12 5 8 11 3 10 7 11 4 9 5 11 6 7 8 9 10 11 12 1\]
Nu blev det en ganska lång rad, men vi kan ju bryta vid tvåan i mitten, för andra halvan är ju bara första baklänges. Nu kan vi utöka vår tabell:
| $n$ | Antal förekomster |
|---|---|
| 1 | 2 |
| 2 | 1 |
| 3 | 2 |
| 4 | 2 |
| 5 | 4 |
| 6 | 2 |
| 7 | 6 |
| 8 | 4 |
| 9 | 6 |
| 10 | 4 |
| 11 | 10 |
| 12 | 4 |
Vi ser att talet 11 förekom hela 10 gånger, och att faktiskt varje sätt att få 11 som en summa av två positiva heltal uppstod exakt en gång. Talet 12 däremot, uppstod bara fyra gånger, som $1+11$, $5+7$, $7+5$, och $11+1$.
Den som har övat på det här med Euklides algoritm och största gemensam delare, märker nu någonting skoj: Det verkar som om två tal bara kan hamna bredvid varandra någonsin i den här processen om deras största gemensamma delare är 1!
Har man väl gjort den observationen, är det inte svårt att bevisa den med induktion. Om vi någonstans i processen har talen $a$ och $b$, och skriver in summan $a+b$ i mellanrummet, så får vi \[\dots a \quad a+b \quad b \dots\]
Om $a$ och $a+b$ skulle ha en gemensam delare $d$, så skulle $d$ dela även $b$, eftersom $b=(a+b)-a$. På samma sätt måste varje gemensam delare till $a+b$ och $b$ också dela $a$. Om vi startar med en talrad där konsekutiva tal alltid har största gemensam delare 1, kommer den egenskapen alltså att bevaras. Och vi startade ju med bara två ettor, så enligt induktionsprincipen kommer intilliggande tal alltid att ha största gemensam delare 1.
Det betyder att talet 12 till exempel, bara kan uppstå som en av de fyra summorna $1+11$, $5+7$, $7+5$, och $11+1$. Alla andra sätt, till exempel $4+8$ eller $9+3$, har en gemensam delare 2 eller 3, och kan aldrig hamna bredvid varandra. Talet 11 däremot kan uppstå på alla 10 tänkbara sätt, $1+10, 2+9, \dots, 10+1$ . Men förklarar detta varför 11 och 12 förekommer exakt 10 respektive 4 gånger? Nja, det verkar ju som om varje talpar med största gemensam delare 1 förekommer exakt en gång, och i så fall skulle ju saken vara klar, men det återstår ju i så fall att bevisa.
Så hur bevisar man en sådan sak? Hint, det är samma svar på den här frågan som det har varit varje gång jag hittills har kastat den frågan ut i föreläsningssalen.
Induktion.
Om induktion har jag sagt att det är viktigt att ha klart för sig vad som är induktionsantagandet. Och för att veta vad som är induktionsantagandet måste man ha klart för sig vad det är man försöker bevisa. När vi nu pratar om att ett talpar $(a,b)$ förekommer intill varandra exakt en gång, menar vi alltså att talen $a$, $b$ kommer att stå intill varandra, i den ordningen, någon gång under processen, och att de kommer att fortsätta stå intill varandra tills vi skriver in deras summa mellan dem. Det är det som räknas som en gång. Om vi kör processen tills alla $a$ och $b$ har skrivits in, kan vi också säga att det finns exakt en förekomst av $a$ och exakt en förekomst av $b$ som någon gång har stått intill varandra (i den ordningen).
Anta att $a$ och $b$ är positiva heltal med största gemensam delare 1. Paret $a, b$ kan hamna intill varandra i den ordningen antingen genom att $b$ uppstår som summan av $a$ och ett annat tal, eller genom att $a$ uppstår som summan av $b$ och ett annat tal. Bara den ena varianten är tänkbar, för bara det större av $a$ och $b$ kan uppstå som en summa där det andra talet är inblandat. Om $a<b$, kan $a, b$ uppstå ur $a, b-a$, och om $a>b$, kan $a, b$ uppstå ur $a-b, b$. Om $a=b$ måste de vara lika med 1, för annars har de en gemensam delare. Men $1,1$ är basfallet i induktionen. Själva induktionssteget då? Ja, här använder vi så kallad "stark induktion", och induktionsantagandet får bli "alla par av positiva heltal med största gemensam delare 1, vars summa är högst $n$, förekommer exakt en gång i processen". Om $a, b$ är ett par vars summa är $n+1$, utnyttjar vi induktionsantagandet och drar slutsatsen att antingen $a, b-a$ eller $a-b, b$ förekommer exakt en gång (beroende på vilket av $a-b$ och $b-a$ som är positivt). Paret $a, b$ måste då också förekomma exakt en gång, och induktionssteget är klart.
Den som har läst om Eulers $\phi$-funktion känner igen talen i tabellen, och inser att vad vi har bevisat är att varje tal $n>1$ kommer att förekomma exakt $\phi(n)$ gånger. Det stämmer inte riktigt för $n=1$, eftersom vi startar med två ettor, men $\phi(1)=1$. Kanske borde vi tänka oss att talen står på en cirkel och att vi börjar med en enda etta, så att ettan till vänster egentligen är samma som ettan till höger.
Se också the Stern-Brocot tree! Och särskilt nämnarna i delen mellan 0 och 1.
No comments:
Post a Comment