9.2 Figurtall og rekursive sammenhenger

Prikkene som ble til formler

For over to tusen år siden satt greske matematikere og la småstein i mønstre på bakken: trekanter, kvadrater, femkanter. De oppdaget at antall steiner i figurene fulgte vakre tallmønstre — og at mønstrene kunne bevises. Figurtall er positive heltall som kan fremstilles som geometriske figurer bygd opp av prikker, og studiet av dem er en klassisk vei til to av matematikkens kjerneferdigheter: å finne formler og å bevise dem.

Vi skal studere tre familier: trekantall, kvadrattall og pentagonaltall. For hver av dem følger vi samme oppskrift: beskriv det geometriske mønsteret, finn en rekursiv formel ut fra hvordan figuren vokser, utled en eksplisitt formel med summeteknikker — og til slutt: bevis formelen med matematisk induksjon, bevisteknikken som lar deg vise at noe gjelder for alle naturlige tall, uendelig mange på en gang.

Koblingen mellom figurtall og rekker gir en visuell tolkning av abstrakte algebraiske identiteter — du skal få se hvorfor $1 + 3 + 5 + \cdots + (2n-1) = n^2$. Finn frem penn og prikker.

Trekanter, kvadrater og femkanter av prikker

Det $n$-te trekantallet $T_n$ er antall prikker i en trekant med $n$ prikker langs hver side: $T_1 = 1$, $T_2 = 3$, $T_3 = 6$, $T_4 = 10$, $T_5 = 15, \ldots$ Hver ny trekant lages ved å legge en ekstra rad under den forrige — rad $k$ har $k$ prikker — så den rekursive formelen er $T_{n+1} = T_n + (n+1)$ med $T_1 = 1$. Eksplisitt er $T_n$ summen $\displaystyle 1 + 2 + \cdots + n = \frac{n(n+1)}{2}$ (Gauss' formel). Det finnes også et rent geometrisk bevis: legg to kopier av trekanten mot hverandre, så fyller de et rektangel med $n$ rader og $n+1$ kolonner — $n(n+1)$ prikker — og trekanten er halvparten.

Det $n$-te kvadrattallet er selvsagt $K_n = n^2$: $1, 4, 9, 16, 25, \ldots$ Men hvordan vokser kvadratet? Fra $K_n$ til $K_{n+1}$ legger du en L-formet vinkel (en gnomon) med $2n + 1$ prikker langs to sider: $K_{n+1} = K_n + (2n+1)$. Dermed er $n^2$ summen av de $n$ første oddetallene: $1 + 3 + 5 + \cdots + (2n-1) = n^2$ — en berømt identitet, synlig for det blotte øye i prikkmønsteret. Og deler du kvadratet langs diagonalen, får du to trekanter: $K_n = T_n + T_{n-1}$, som du kan sjekke algebraisk: $\displaystyle \frac{n(n+1)}{2} + \frac{(n-1)n}{2} = n^2$.

Det $n$-te pentagonaltallet bygger femkanter lagvis: $P_1 = 1$, $P_2 = 5$, $P_3 = 12$, $P_4 = 22$, $P_5 = 35, \ldots$ Differansene $P_{n+1} - P_n = 3n + 1$ vokser aritmetisk med $d = 3$, og den eksplisitte formelen er $\displaystyle P_n = \frac{n(3n-1)}{2}$. Alle disse er spesialtilfeller av polygonaltall for en regulær $s$-kant: $\displaystyle p_s(n) = \frac{n[(s-2)n - (s-4)]}{2}$ — sett inn $s = 3, 4, 5, 6$ og få trekant ($\displaystyle \frac{n(n+1)}{2}$), kvadrat ($n^2$), pentagon ($\displaystyle \frac{n(3n-1)}{2}$) og heksagon ($n(2n-1)$).

Detektivmetoden: fra mønster til formel

Hva gjør du når du møter en ukjent tallfølge — si $1, 6, 15, 28, 45$? Detektivmetoden har tre steg.

Steg 1: Differansene. $6-1 = 5$, $15-6 = 9$, $28-15 = 13$, $45-28 = 17$. Differansene $5, 9, 13, 17$ er ikke konstante — men deres differanser er: $4, 4, 4$. Når andredifferansene er konstante, er følgen et andregradsuttrykk $a_n = An^2 + Bn + C$, med $\displaystyle A = \frac{\text{andredifferansen}}{2}$. (Konstante førstedifferanser gir tilsvarende en lineær formel.)

Steg 2: Rekursiv formel. Den $k$-te differansen er $5 + (k-1) \cdot 4 = 4k + 1$, så $a_{n+1} = a_n + (4n + 1)$ med $a_1 = 1$.

Steg 3: Eksplisitt formel via summeformler. Leddet $a_n$ er startverdien pluss alle differansene:

$$a_n = 1 + \sum_{k=1}^{n-1}(4k + 1) = 1 + 4 \cdot \frac{(n-1)n}{2} + (n-1) = 1 + (n-1)(2n+1) = 2n^2 - n = n(2n-1)$$

Verifikasjon: $a_5 = 5 \cdot 9 = 45$. ✓ (Dette er faktisk heksagonaltallene $p_6(n)$.) Underveis brukte vi summene som er verdt å kunne utenat: $\displaystyle \sum_{k=1}^{n} k = \frac{n(n+1)}{2}$, $\displaystyle \sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}$ og $\sum_{k=1}^{n}(2k-1) = n^2$.

Metoden virker også baklengs, som en designøvelse: en stjernefigur med én sentral prikk og $n$ armer à $n$ prikker har $S_n = n^2 + 1$ prikker ($2, 5, 10, 17, \ldots$), og differansene $S_{n+1} - S_n = 2n + 1$ er oddetallene — kvadrattallenes signatur, pluss en konstant. Tegn gjerne figurene: visualisering er ikke pynt, det er ofte selve innsikten.

Induksjon — beviset som klatrer en uendelig stige

Detektivmetoden finner formler, men funn er ikke bevis: at $\displaystyle T_n = \frac{n(n+1)}{2}$ stemmer for de fem første leddene, garanterer ingenting om ledd nummer en million. Til det trenger vi matematisk induksjon — teknikken for å bevise at en påstand $P(n)$ gjelder for alle naturlige tall $n \geq 1$.

Tenk på en uendelig stige. Kan du nå første trinn? Og kan du, fra et hvilket som helst trinn, alltid nå det neste? Da når du alle trinnene. Formelt: Grunnsteg — vis at $P(1)$ er sann. Induksjonssteg — anta at $P(m)$ er sann for et vilkårlig $m \geq 1$ (induksjonsantagelsen), og vis at da er $P(m+1)$ også sann. Konklusjon: $P(n)$ gjelder for alle $n \geq 1$.

La oss bevise $\displaystyle 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$. Grunnsteg ($n = 1$): venstre side er $1$, høyre side er $\displaystyle \frac{1 \cdot 2}{2} = 1$. ✓ Induksjonssteg: anta formelen for $n = m$, altså $\displaystyle 1 + 2 + \cdots + m = \frac{m(m+1)}{2}$. Da er

$$1 + 2 + \cdots + m + (m+1) = \frac{m(m+1)}{2} + (m+1) = (m+1)\left(\frac{m}{2} + 1\right) = \frac{(m+1)(m+2)}{2}$$

— nøyaktig formelen med $n = m+1$. ✓ Stigen er klatret: formelen gjelder for alle $n \geq 1$. $\blacksquare$

Strategien i induksjonssteget er nesten alltid den samme for summeformler: skriv $S_{m+1} = S_m + (\text{ledd nummer } m+1)$, bytt ut $S_m$ med induksjonsantagelsen, og regn deg frem til målformelen. Det vanskelige er sjelden regningen — det er å holde tunga rett i munnen om hva som antas og hva som skal vises. Antagelsen gjelder ett vilkårlig $m$; det du viser, er implikasjonen $P(m) \Rightarrow P(m+1)$. Sammen med grunnsteget er det nok til å dekke uendelig mange tilfeller med endelig mye arbeid — induksjonens stille mirakel.

Oppsummering: fra småstein til strenge bevis

Grekernes prikkemønstre bærer fortsatt på pensum. Trekantallene $\displaystyle T_n = \frac{n(n+1)}{2}$, kvadrattallene $K_n = n^2$ og pentagonaltallene $\displaystyle P_n = \frac{n(3n-1)}{2}$ vokser hver med sin gnomon — rader, L-former og lag — og henger sammen på vakkert vis: $K_n = T_n + T_{n-1}$, og kvadratet er summen av oddetallene. Alle er polygonaltall $\displaystyle p_s(n) = \frac{n[(s-2)n - (s-4)]}{2}$.

Detektivmetoden gjorde ukjente følger kjente: konstante førstedifferanser betyr lineær formel, konstante andredifferanser betyr andregradsformel med $\displaystyle A = \frac{\Delta^2}{2}$ — og summeformlene $\displaystyle \sum k = \frac{n(n+1)}{2}$, $\displaystyle \sum k^2 = \frac{n(n+1)(2n+1)}{6}$ og $\sum(2k-1) = n^2$ bygger broen fra rekursiv til eksplisitt form, slik $1, 6, 15, 28, 45$ ble til $n(2n-1)$.

Og til slutt det som skiller matematikk fra mønstergjetting: induksjonen. Grunnsteg pluss induksjonssteg — $P(1)$ sann, og $P(m) \Rightarrow P(m+1)$ — beviser påstander for uendelig mange $n$ med endelig arbeid, som da Gauss-formelen ble klatret trinn for trinn. Mønstre kan sees, formler kan finnes — men fra nå av kan du også bevise dem.