Matematik, der forbinder, hvor vi skal hen, hvor vi har været | Quanta Magasinet

Lad os sige, at du er til en fest med ni andre mennesker, og at alle trykker alle andres hånd præcis én gang. Hvor mange håndtryk finder sted?

Dette er "håndtryksproblemet", og det er en af ​​mine favoritter. Som matematiklærer elsker jeg det, fordi der er så mange forskellige måder, du kan nå frem til løsningen på, og mangfoldigheden og sammenhængen mellem disse strategier illustrerer på smuk vis styrken af ​​kreativ tænkning i matematik.

En løsning lyder sådan her: Start med, at hver person ryster hver anden persons hånd. Ti personer, med ni håndtryk hver, producerer 9 × 10 = 90 håndtryk i alt. Men dette tæller hvert håndtryk to gange – én gang fra hver rysters perspektiv – så det faktiske antal håndtryk er $latex frac{90}{2} = 45$. Et enkelt og dejligt tælleargument for sejren!

Der er også en helt anden måde at løse problemet på. Forestil dig, at gæsterne kommer en ad gangen, og når de kommer dertil, giver de hånd til alle tilstedeværende. Den første person har ingen hænder at ryste, så i en enkeltmandsfest er der ingen håndtryk totalt. Nu kommer den anden person og giver hånd med den første. Dette føjer et håndtryk til det samlede antal, så i en to-personers fest er der 0 + 1 = 1 håndtryk i alt. Når den tredje person ankommer og giver hånd med de to første gæster, tilføjer dette to håndtryk til totalen. Den fjerde persons ankomst tilføjer tre håndtryk til det samlede antal, og så videre.

Denne strategi modellerer sekvensen af ​​håndtryk rekursivt, hvilket betyder, at hvert led i sekvensen er defineret i forhold til dem, der kommer før det. Du er sikkert bekendt med Fibonacci-sekvensen, den mest berømte rekursive sekvens af alle. Det starter med 1, 1, 2, 3, 5, 8, 13, 21 og fortsætter med hvert efterfølgende led svarende til summen af ​​de to foregående.

Som vi vil se nedenfor, er rekursion en fleksibel og kraftfuld ramme til at tænke på en bred vifte af matematiske ideer. Og selvom gamle indiske lærde som Hemachandra er krediteret med at kende til denne slags sekvenser så langt tilbage som 1150, tilbyder de stadig spændende udfordringer for matematikere i dag.

Lad os se, hvordan rekursiv tænkning hjælper med håndtryksproblemet. Hvis vi lader $latex a_n$ lig med antallet af håndtryk ved an n-person part, kan vi repræsentere dette rekursive forhold med følgende formel:

$latex a_n = a_{n-1} + n–1$

Dette fortæller os, at antallet af håndtryk ved en n-person part ($latex a_n$) er lig med antallet af håndtryk ved en (n − 1)-person part ($latex a_{n-1}$) plus n − 1 håndtryk mere, der fanger ideen om, at når en ny person ankommer, tilføjer de et vist antal nye håndtryk til dem, der allerede har fundet sted.

I vores særlige version af håndtryksproblemet vil vi gerne vide $latex a_{10}$, antallet af håndtryk ved en 10-personers fest, så vi kan finde ud af, at vi bruger det rekursive forhold

$latex a_{10} = a_9 + 9$

For at finde værdien af ​​$latex a_{10}$ skal vi blot kende værdien af ​​$latex a_9$ og tilføje 9 til den. Hvordan finder vi værdien af ​​$latex a_9$? Ved at bruge rekursion, selvfølgelig!

$latex a_9 = a_8 + 8$

Nu, for at finde værdien af ​​$latex a_8$, skal vi finde værdien af ​​$latex a_7$, hvilket kræver at kende $latex a_6$, og så videre. På dette tidspunkt er du måske bekymret for, at dette vil fortsætte for evigt i en slags uendelig afstamning, men når vi når $latex a_1$, er vi færdige, fordi vi ved, at der er nul samlede håndtryk ved en enkeltmandsfest.

$latex a_1 = 0$

Denne initiale eller "seed"-værdi er et nøgletræk ved en rekursiv sekvens. Det garanterer, at denne proces med at gå tilbage gennem sekvensen ved hjælp af det rekursive forhold vil ende. Når du har ramt startværdien, stopper tilbagesporingen, og du kan derefter arbejde dig frem gennem listen for at få den værdi, du ønsker.

$latex a_1 = 0$

$latex a_2 = a_1 + 1 = 0 + 1 = 1$

$latex a_3 = a_2 + 2 = 1 + 2 = 3$

$latex a_4 = a_3 + 3 = 3 + 3 = 6$

$latex cdots$

$latex a_{10} = a_9 + 9 = 36 + 9 = 45$

Ved at gennemgå listen ser vi, at der er 45 håndtryk i alt ved en 10-mands fest, hvilket stemmer overens med vores oprindelige beregning. Hvis du er noget som mine elever, kan du spørge, hvorfor vi har brug for en anden måde at løse dette problem på, når vi allerede kender svaret, især da denne anden tilgang ser ud til at tage længere tid.

Det er et godt spørgsmål. Et svar er, at den rekursive tilgang giver os et helt andet syn på, hvad der foregår i dette problem, og forskellige perspektiver er nyttige i matematik, som de er i alle ting. De giver os forskellige muligheder for at forstå begreber og giver os mulighed for at bruge forskellige værktøjer, som kan hjælpe, når vi sidder fast.

Især rekursion er nyttig, fordi det er overalt i matematik. Det opstår for eksempel i de lineære sammenhænge, ​​som alle lærer om i matematiktimerne - dem, der er karakteriseret ved en konstant forandringshastighed og repræsenteret af linjer i planet. En lineær funktion som $latex f(x) = 3x + 5$ kan opfattes som en rekursiv formel:

$latex a_0 = 5$

$latex a_n = a_{n-1} + 3$

Selvom den mere oplagte måde at tænke $latex f(2)$ på kan være, at $latex f(2) = 3 gange 2 + 5 = 11$, er en anden måde, at $latex a_2 = a_1 + 3 = a_0 + 3 + 3 = 11$. Rekursiv modellering af de grundlæggende kendetegn ved lineære funktioner - den konstante ændringshastighed - giver os en anden måde at tænke på dette forhold. Det samme kan gøres med eksponentielle funktioner karakteriseret ved konstant multiplikativ ændring.

Rekursiv tænkning virker også ud over talsekvenser. Hvis du nogensinde har løst et ligningssystem, har du sandsynligvis anvendt en rekursiv tilgang. At løse systemet

$latex 2x + y = 10$

$latex 3x – y = 5$

du kan først lægge de to ligninger sammen for at eliminere y variabel, hvilket resulterer i ligningen $latex 5x = 15$. Løs dette for at få $latex x =$ 3, erstat for at finde $latex y = 4$, og du er færdig. Denne tilgang anvender en rekursiv algoritme, hvor løsningen til et system bygges fra løsningen til mindre, relaterede systemer. For eksempel, for at løse et 3 × 3-system, fjerner du en variabel for at gøre det til et 2 × 2-system og derefter igen for at gøre det til et 1 × 1-system. Denne enkle ligning, der er let at løse, er som startværdien af ​​denne rekursive proces. Det signalerer slutningen af ​​tilbagesporingen, og derfra arbejder du dig tilbage op i ligningskæden, ligesom i en rekursiv sekvens.

Der er endda rekursive bevisteknikker. For eksempel er en berømt formel inden for geometri polygonvinkelsumformlen, som siger, at summen af ​​målene for de indre vinkler af en n-sidet polygon er $latex (n-2) gange 180^{circ}$. En måde at bevise dette resultat på er at starte med en n-forestil dig, hvad der ville ske, hvis du fjernede en trekant.

Fjernelse af en trekant drejer n-gå ind i en (n − 1)-gon, og det fjerner også 180 graders indvendig vinkelmål. Dette er et rekursivt forhold: Den indre vinkelsum for en n-gon er 180 grader mere end den indvendige vinkelsum for en (n − 1)-gon. For at fastslå det generelle resultat skal du fortsætte med at fjerne trekanter, indtil du når startværdien, hvilket i denne situation sker, når du har fjernet alle på nær tre n-gons hjørner. På dette tidspunkt er den indledende polygon blevet reduceret til en trekant, hvis indre vinkelsum vides at være 180 grader. Arbejd dig nu op igen, tilføj 180 grader ved hvert trin, og du får formlen.

For at vende tilbage til vores parti, viser selve håndtryksproblemet os, hvad der er muligt, når vi tænker kreativt og derefter forbinder de mange forskellige perspektiver af et problem sammen. Hvis vi leger med den rekursive model for vores rækkefølge af håndtryk:

$latex a_1 = 0$

$latex a_n = a_{n-1} + n – 1$

et flot mønster dukker op:

$latex a_2 = a_1 + 1 = 0 + 1$

$latex a_3 = a_2 + 2 = 0 + 1 + 2$

$latex a_4 = a_3 + 3 = 0 + 1 + 2 + 3$

$latex cdots$

$latex a_n = a_{n-1} + (n-1) = 0 + 1 + 2 + 3 + cdots + (n-1)$

Vi har nu en ny og generel måde at tænke på problemet på: Antallet af håndtryk i en n-person part er lig med summen af ​​den første n − 1 positivt heltal.

Tænk tilbage på vores oprindelige tilgang. I en n-person fest, hver person vil give hånd med den anden n - 1 personer. Produktet $latex n (n-1)$ tæller hvert håndtryk to gange, så det samlede antal håndtryk er $latex frac{n(n-1)}{2}$. Men da vores forskellige metoder tæller det samme, skal de give det samme resultat. Dette betyder især:

$latex 1 + 2 + 3 + cdots + (n-1) = frac{n(n-1)}{2}$

Ved at forbinde forskellige tilgange til håndtryksproblemet får vi en lukket formel for summen af ​​den første n − 1 positivt heltal. Men vi får endnu mere: Udtrykket $latexfrac{n(n-1)}{2}$ involverer en brøk, men fordi den er lig med en sum af heltal, skal den også være et heltal. Dette beviser et simpelt faktum i talteorien: For hvert heltal n, $latex frac{n(n-1)}{2}$ er et heltal.

Den samme slags argumenter fortsætter med at drive moderne matematik. Som et eksempel, forskere i begyndelsen af ​​2000'erne viste nogle overraskende resultater om rekursive sekvenser kendt som Somos-sekvenser ved at vise, at de også tæller noget. Gennem kraften af ​​kreative forbindelser opdagede matematikere igen, hvor de kunne gå hen ved at forstå, hvor de har været.

Øvelser

1. Find en lukket formel for sekvensen, der er defineret rekursivt som
$latex a_1 = 1$
$latex a_n = a_{n-1} + 2n – 1$

2. I slutningen af ​​kolonnen blev udtrykket $latexfrac{n(n-1)}{2}$ vist at være et heltal, selvom udtrykket involverer en brøk, fordi $latexfrac{n(n-1 )}{2}$ er resultatet af at tælle noget. Der er også et talteoretisk argument, der viser, at dette udtryk skal være et heltal. Hvad er det?

3. Find de første par led i den rekursive sekvens
$latex a_1 = 1$
$latex a_n = frac{1}{1+a_{n-1}}$

4. Find de første par led i den rekursive sekvens
$latex a_1 = 1$
$latex a_2 = 1$
$latex a_n = a_{n-1} – a_{n-2}$