Aritmetisk følge

En aritmetisk følge er en følge der differansen mellom et tall og det neste er konstant. For eksempel er {4,7,10,13,16,…} en aritmetisk følge siden differansen mellom to etterfølgende tall alltid er 3. Hvis differansen ${\displaystyle d}$ er gitt, og man i tillegg kjenner verdien av det første tallet, ${\displaystyle a_{1}}$, er følgen entydig bestemt, og det ${\displaystyle n}$-te tallet er gitt ved

${\displaystyle a_{n}=a_{1}+(n-1)d.}$

Hvis man lar ${\displaystyle s_{n}}$ være summen av de ${\displaystyle n}$ første tallene i følgen, danner ${\displaystyle \{s_{1},s_{2},\ldots \}}$ en aritmetisk rekke. Gitt en aritmetisk følge hvor ${\displaystyle a_{1}}$ og ${\displaystyle d}$ er kjent, finnes det en enkel formel for summen av elementene, nemlig

${\displaystyle s_{n}={\frac {n(2a_{1}+(n-1)d)}{2}}.}$

En versjon av denne formelen forekommer i Liber Abaci (1202) av Leonardo av Pisa.

For å utlede denne formelen, legger vi merke til at ${\displaystyle s_{n}}$ kan uttrykkes på to forskjellige måter:

${\displaystyle s_{n}=a_{1}+(a_{1}+d)+(a_{1}+2d)+\cdots +(a_{1}+(n-2)d)+(a_{1}+(n-1)d)}$

${\displaystyle s_{n}=(a_{n}-(n-1)d)+(a_{n}-(n-2)d)+\cdots +(a_{n}-2d)+(a_{n}-d)+a_{n}}$

Summerer vi begge sidene av disse ligningene, vil alle summandene som inneholder ${\displaystyle d}$ kanselleres, og vi sitter igjen med

${\displaystyle 2s_{n}=n(a_{1}+a_{n}).}$

Bruker vi formelen for ${\displaystyle a_{n}}$, som er gitt ovenfor, følger formelen for ${\displaystyle s_{n}}$.

Flere problemer i Ramsey-teori handler om aritmetiske følger. En generell formulering er at en mengde ${\displaystyle A}$ med naturlige tall er gitt, og problemet er å finne ut hvor lange aritmetiske følger som er inneholdt i ${\displaystyle A}$.

La ${\displaystyle n}$ være et naturlig tall, og anta at man fargelegger alle tallene fra 1 til ${\displaystyle n}$ med ${\displaystyle r}$ farger, slik at hvert tall får én farge. Van der Waerdens teorem fra 1927 sier at hvis ${\displaystyle k}$ og ${\displaystyle r}$ er gitt, så kan ${\displaystyle n}$ alltid velges så stor at det helt sikkert finnes en aritmetisk følge med ${\displaystyle k}$ elementer, slik at alle elementene i følgen har samme farge. En slik følge kalles monokromatisk.

En ekvivalent formulering av dette teoremet sier at hvis man fargelegger alle de naturlige tallene med ${\displaystyle r}$ farger, så vil det finnes vilkårlig lange monokromatiske følger.

I 1975 beviste Szemerédi en generalisering av dette teoremet, som er kjent som Szemerédis teorem. Han viste at for enhver tetthet ${\displaystyle d}$, hvor ${\displaystyle 0<d<1}$, og ethvert naturlig tall ${\displaystyle k}$, så finnes et tall ${\displaystyle N}$ slik at hvis ${\displaystyle n\geq N}$, så vil enhver delmengde av ${\displaystyle \{1,\ldots ,n\}}$ med minst ${\displaystyle dn}$ elementer inneholde en aritmetisk følge av lengde ${\displaystyle k}$.

Mer generelt ${\displaystyle A}$ være en delmengde av de naturlige tallene. Et problem som har fått en del opperksomhet er spørsmålet om hvilke karakteristikker av ${\displaystyle A}$ som garanterer at ${\displaystyle A}$ inneholder vilkårlig lange aritmetiske følger. Szemerédis teorem garanterer at det er tilstrekkelig at ${\displaystyle A}$ har såkalt positiv øvre tetthet. En berømt formodning er Erdős’ formodning som sier at hvis summen av inversene til elementene i ${\displaystyle A}$ divergerer, så vil ${\displaystyle A}$ inneholde vilkårlig lange aritmetiske følger. Erdős har tilbudt 3000 dollar for løsningen av denne formodningen. Green–Taos teorem fra 2004 sier at primtallene inneholder vilkårlig lange aritmetiske følger. Siden summen av inversene til primtallene divergerer, er dette teoremet et spesialtilfelle av Erdős’ formodning.