Skillnad mellan versioner av "Eriks skumma talföljder"
Alex (diskussion | bidrag) (lite mer grejs) |
m (7 versioner) |
(Ingen skillnad)
| |
Versionen från 4 oktober 2010 kl. 23.23
|
Den här artikeln behöver mer slafs! |
Eriks skumma talföljder upptäcktes av Erik. De definieras av Eriks galna jävla formel.
Historia
Eriks skumma talföljder slafsades fram av Erik när han för en gångs skull inte sov under en matematiklektion med Ulf. Den första talföljden var 1, 2, 3, 4, 5... och dessa tal var differensen mellan talen i nästa följd, som var differensen mellan talen i nästa följd. Han visade dem för Joakim som märkte att den fjärde talföljden var samma som för antalet regioner i en cirkel där man har dragit alla möjliga kordor mellan ett n antal punkter på periferin. Han slafsade fram formeln, som klassen tidigare hade slafsat fram under en Paullektion, och visade den för Erik som slafsade fram liknande formler för de andra talföljderna. Sedan slafsade han fram en allmän formel för den n:te talföljden. Joakim testade den, och meddelade sedan häpet på MSN att den galna jävla formeln stämde. Detta är historiskt, eftersom det markerar första gången Erik gör rätt och Erik får göra så.
Joakim slafsade sedan fram en rekursionsformel och ett början till bevis för Eriks formel i sömnen. Han insåg samtidigt att allt de hade gjort var att slafsa fram en variant av Pascals Triangel. Senare slafsade han fram sambandet mellan talföljderna och inte lika skumma följder av tvåpotenser.
Kort därefter bestämde sig Erland för att vara gnällig och klagade på att icke heltal är otrevliga att ha som index. Ingen orkade bry sig, förrän Joakim en tid senare efter oerhörda mängder slafs löste problemet genom att inte ha heltal som index.
Definition
Eriks galna jävla (explicita) formel säger att [math]{}_na_k=\sum_{i=\frac{n}{2}-[ \frac{n}{2}]}^\frac{n}{2} {k \choose 2i}[/math] där [math]{}_na_k[/math] är den k:te termen i den n:te talföljden. Första termen i varje följd, 1, är [math]{}_na_1[/math], men första följden, {1, 1, 1...}, är [math]{}_0a_k[/math] - den räknas som den 0:te följden, och {1, 2, 3...} är den första.
Om man är en gnällig jävel och bestämmer sig för att klaga, kan denna, förbättrade formel användas: [math]{}_na_k=\sum_{i=0}^{[\frac{n}{2}]} {k \choose 2(i+\frac{n}{2}-[\frac{n}{2}])}[/math]
Eriks galna jävla formel kan skrivas som [math]{k \choose 0}+{k \choose 2}+...+{k \choose n}[/math] för jämna n, och [math]{k \choose 1}+{k \choose 3}+...+{k \choose n}[/math] för udda n. T.ex. den tredje talföljden är [math]{k \choose 1}+{k \choose 3}[/math] och den fjärde är [math]{k \choose 0}+{k \choose 2}+{k \choose 4}.[/math]
Den rekursiva formeln är [math]{}_na_1={}_0a_k=1, \quad {}_na_k={}_na_{k-1}+{}_{n-1}{}a_{k-1}.[/math]
Egenskaper
Av definitionen följer att om [math]\begin{matrix} a & b \\ c & d \end{matrix}[/math] är tal i Eriks skumma talföljder så gäller att [math]d-c=a[/math] eller [math]d=a+c[/math]. Jämför med Pascals Triangel (som man får om man vrider på den medsols så att a är överst och d är underst), där det i stället gäller att [math]d=b+c[/math].
I följd n gäller att de n+1 första termerna följer formeln [math]2^{k-1}[/math]. Avvikelsen från formeln för term n+m följer talföljden [math]{}_{m-1}a_k[/math]. Detta är följd av beviset för Eriks galna jävla formel.
Här följer en tabell över de tio första termerna i de tio första följderna:
[math]\begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 1 & 2 & 4 & 7 & 11 & 16 & 22 & 29 & 37 & 46 \\ 1 & 2 & 4 & 8 & 15 & 26 & 42 & 64 & 93 & 130 \\ 1 & 2 & 4 & 8 & 16 & 31 & 57 & 99 & 163 & 256 \\ 1 & 2 & 4 & 8 & 16 & 32 & 63 & 120 & 219 & 382 \\ 1 & 2 & 4 & 8 & 16 & 32 & 64 & 127 & 247 & 466 \\ 1 & 2 & 4 & 8 & 16 & 32 & 64 & 128 & 255 & 502 \\ 1 & 2 & 4 & 8 & 16 & 32 & 64 & 128 & 256 & 511 \\ 1 & 2 & 4 & 8 & 16 & 32 & 64 & 128 & 256 & 512 \end{matrix}[/math]
Bevis
Ett bevis för Eriks galna jävla formel kan troligen härledas genom att sätta in den i den rekursiva formeln, som endast är en följd av definitionen för Eriks skumma talföljder. Då måste man antagligen dela upp beviset i två fall - när n är jämn och när n är udda.
Här är ett förslag till bevis:
Låt [math] {n \choose k} [/math] vara [math] 0 [/math] om [math] k \lt 0 [/math] eller [math] k \gt n [/math]
Formeln stämmer uppenbart för rad 1, antag att den stämmer för alla rader [math]1\leq i \leq n-1 [/math] och antag att [math] 2|n [/math]. Formeln stämmer fortfarande för [math] {}_na_1 ={1 \choose 0} = 1[/math]. Sätt [math] k \gt 1 [/math] och antag [math]{}_na_j = {j \choose 0} + { j \choose 2} + \ldots + {j\choose n} [/math] för alla [math] j \lt k [/math]. Då blir [math]{}_na_k = {}_na_{k-1}+{}_{n-1}a_{k-1} = \sum_{2|i, i\lt n}{k-l\choose i} + \sum_{2 \not| i, i\lt n}{k-l\choose i} = \sum_{j, 2j\lt n}{k-l\choose 2j}+{k-1\choose 2j-1} = \sum_{j, 2j\lt n}{k \choose 2j}[/math] vilket vi skulle visa. Fallet [math] n [/math]-udda behandlas ungefär på samma sätt.
Fler samband
- För [math]k\lt n+1 [/math] gäller att [math]{}_na_{k} = 2^{k-1}[/math]
- [math]{}_na_{k} - {}_na_{k-1} = \sum_{i \equiv n (mod 2)} {k \choose i} - \sum_{i \equiv n (mod 2)} {k-1 \choose i} = [/math]
[math] = \sum_{i \equiv n (mod 2)} {k-1 \choose i} + {k-1 \choose i-1} - \sum_{i \equiv n (mod 2)} {k-1 \choose i} = \sum_{i \equiv n (mod 2)} {k-1 \choose i-1} = {}_{n-1}a_{k-1} [/math]
- [math]{}_na_{k} - {}_{n-1}a_{k} = {}_{n-1}a_{k-1} [/math]
