Si at du er på en fest med ni andre mennesker og at alle trykker alle andres hånd nøyaktig én gang. Hvor mange håndtrykk finner sted?

Dette er "håndtrykkproblemet", og det er en av mine favoritter. Som matematikklærer elsker jeg det fordi det er så mange forskjellige måter du kan komme frem til løsningen på, og mangfoldet og sammenhengen mellom disse strategiene illustrerer på en vakker måte kraften til kreativ tenkning i matematikk.

En løsning går slik: Start med at hver person rister hver annen persons hånd. Ti personer, med ni håndtrykk hver, produserer 9 × 10 = 90 totale håndtrykk. Men dette teller hvert håndtrykk to ganger – én gang fra hver shakers perspektiv – så det faktiske antallet håndtrykk er $latex frac{90}{2} = 45$. Et enkelt og deilig telleargument for seier!

Det er også en helt annen måte å løse problemet på. Tenk deg at gjestene kommer en om gangen, og når de kommer dit håndhilser de alle tilstedeværende. Den første personen har ingen hender å riste på, så i en enmannsfest er det null totalt håndtrykk. Nå kommer den andre personen og håndhilser på den første personen. Dette legger til ett håndtrykk til totalen, så i et parti med to personer er det 0 + 1 = 1 totalt håndtrykk. Når den tredje personen kommer og håndhilser på de to første gjestene, legger dette til to håndtrykk til totalen. Den fjerde personens ankomst legger til tre håndtrykk til totalen, og så videre.

Denne strategien modellerer sekvensen av håndtrykk rekursivt, noe som betyr at hvert begrep i sekvensen er definert i forhold til de som kommer før det. Du er sannsynligvis kjent med Fibonacci-sekvensen, den mest kjente rekursive sekvensen av alle. Den starter 1, 1, 2, 3, 5, 8, 13, 21, og fortsetter med hvert påfølgende ledd lik summen av de to foregående.

Som vi vil se nedenfor, er rekursjon et fleksibelt og kraftig rammeverk for å tenke på et bredt spekter av matematiske ideer. Og selv om eldgamle indiske lærde som Hemachandra er kreditert med å vite om denne typen sekvenser så langt tilbake som 1150, tilbyr de fortsatt spennende utfordringer for matematikere i dag.

La oss se hvordan rekursiv tenkning hjelper med håndtrykkproblemet. Hvis vi lar $latex a_n$ lik antall håndtrykk ved an n-person part, kan vi representere dette rekursive forholdet med følgende formel:

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

Dette forteller oss at antall håndtrykk på en n-person part ($latex a_n$) er lik antall håndtrykk ved en (n − 1)-person parti ($latex a_{n-1}$) pluss n − 1 håndtrykk til, som fanger ideen om at når en ny person kommer, legger de til et visst antall nye håndtrykk til de som allerede har funnet sted.

I vår spesielle versjon av håndtrykkproblemet ønsker vi å vite $latex a_{10}$, antall håndtrykk på en fest med 10 personer, så for å finne ut at vi bruker det rekursive forholdet

$latex a_{10} = a_9 + 9$

For å finne verdien av $latex a_{10}$ trenger vi bare å vite verdien av $latex a_9$ og legge til 9 til den. Hvordan finner vi verdien av $latex a_9$? Ved å bruke rekursjon, selvfølgelig!

$latex a_9 = a_8 + 8$

Nå, for å finne verdien av $latex a_8$, må vi finne verdien av $latex a_7$, som krever å kjenne til $latex a_6$, og så videre. På dette tidspunktet er du kanskje bekymret for at dette vil fortsette for alltid i en slags uendelig nedstigning, men når vi når $latex a_1$ er vi ferdige, fordi vi vet at det er null totalt håndtrykk på en enmannsfest.

$latex a_1 = 0$

Denne innledende eller "seed"-verdien er en nøkkelfunksjon i en rekursiv sekvens. Det garanterer at denne prosessen med å gå tilbake gjennom sekvensen ved å bruke det rekursive forholdet vil ende. Når du treffer startverdien stopper tilbakesporingen, og du kan deretter jobbe deg frem gjennom listen for å få verdien 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 å jobbe gjennom listen ser vi at det er totalt 45 håndtrykk på en 10-manns fest, noe som stemmer med vår første beregning. Hvis du er noe som elevene mine, kan du spørre hvorfor vi trenger en annen måte å løse dette problemet på når vi allerede vet svaret, spesielt siden denne andre tilnærmingen ser ut til å ta lengre tid.

Det er et godt spørsmål. Ett svar er at den rekursive tilnærmingen gir oss et helt annet syn på hva som foregår i denne oppgaven, og forskjellige perspektiver er nyttige i matematikk, som de er i alle ting. De gir oss ulike muligheter til å forstå konsepter og lar oss bruke ulike verktøy, som kan hjelpe når vi står fast.

Spesielt er rekursjon nyttig fordi det er overalt i matematikk. Det oppstår for eksempel i de lineære relasjonene alle lærer om i mattetimen - de som er preget av en konstant endringshastighet og representert av linjer i planet. En lineær funksjon som $latex f(x) = 3x + 5$ kan tenkes på som en rekursiv formel:

$latex a_0 = 5$

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

Selv om den mer åpenbare måten å tenke på $latex f(2)$ kan være at $latex f(2) = 3 ganger 2 + 5 = 11$, er en annen måte at $latex a_2 = a_1 + 3 = a_0 + 3 + 3 = 11$. Rekursiv modellering av de grunnleggende egenskapene til lineære funksjoner - den konstante endringshastigheten - gir oss en annen måte å tenke på dette forholdet. Det samme kan gjøres med eksponentielle funksjoner preget av konstant multiplikativ endring.

Rekursiv tenkning fungerer også utover tallsekvenser. Hvis du noen gang har løst et ligningssystem, har du sannsynligvis brukt en rekursiv tilnærming. For å løse systemet

$latex 2x + y = 10$

$latex 3x – y = 5$

du kan først legge de to ligningene sammen for å eliminere y variabel, som resulterer i ligningen $latex 5x = 15$. Løs dette for å få $latex x =$ 3, erstatt for å finne $latex y = 4$, og du er ferdig. Denne tilnærmingen bruker en rekursiv algoritme, der løsningen til et system bygges fra løsningen til mindre, relaterte systemer. For eksempel, for å løse et 3 × 3-system, eliminerer du én variabel for å gjøre det om til et 2 × 2-system, og deretter igjen for å gjøre det om til et 1 × 1-system. Denne enkle ligningen som er lett å løse, er som startverdien til denne rekursive prosessen. Det signaliserer slutten på tilbakesporingen, og derfra jobber du deg tilbake opp i likningskjeden, akkurat som i en rekursiv sekvens.

Det finnes til og med rekursive bevisteknikker. For eksempel er en kjent formel innen geometri polygonvinkelsumformelen, som sier at summen av målene til de indre vinklene til en n-sidet polygon er $latex (n-2) ganger 180^{circ}$. En måte å bevise dette resultatet på er å starte med en n-gå og forestill deg hva som ville skje hvis du fjernet en trekant.

Fjerning av en trekant snur n-gå inn i en (n − 1)-gon, og den fjerner også 180 grader av innvendig vinkelmål. Dette er et rekursivt forhold: Den indre vinkelsummen for en n-gon er 180 grader mer enn den indre vinkelsummen for en (n − 1)-gon. For å etablere det generelle resultatet, fortsett å fjerne trekanter til du når frøverdien, som i denne situasjonen skjer når du har fjernet alle unntatt tre av n-gons hjørner. På dette tidspunktet er den innledende polygonen redusert til en trekant, hvis indre vinkelsum er kjent for å være 180 grader. Arbeid deg nå opp igjen, legg til 180 grader ved hvert trinn, så får du formelen.

For å komme tilbake til partiet vårt, viser selve håndtrykksproblemet oss hva som er mulig når vi tenker kreativt og deretter kobler de mange forskjellige perspektivene til et problem sammen. Hvis vi leker med den rekursive modellen for sekvensen av håndtrykk:

$latex a_1 = 0$

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

et fint mønster dukker opp:

$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 nå en ny, og generell måte å tenke på problemet på: Antall håndtrykk i en n-person part er lik summen av den første n − 1 positivt heltall.

Tenk tilbake på vår opprinnelige tilnærming. I en n-person fest, hver person vil håndhilse på den andre n − 1 personer. Produktet $latex n (n-1)$ teller hvert håndtrykk to ganger, så det totale antallet håndtrykk er $latex frac{n(n-1)}{2}$. Men siden våre forskjellige metoder teller det samme, må de gi samme resultat. Spesielt betyr dette:

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

Ved å koble ulike tilnærminger til håndtrykkproblemet får vi en lukket formel for summen av den første n − 1 positivt heltall. Men vi får enda mer: uttrykket $latex frac{n(n-1)}{2}$ involverer en brøk, men fordi det er lik en sum av heltall, må det også være et heltall. Dette beviser et enkelt faktum innen tallteori: For hvert heltall n, $latex frac{n(n-1)}{2}$ er et heltall.

Denne samme typen argumentasjon fortsetter å drive moderne matematikk. Som et eksempel, forskere på begynnelsen av 2000-tallet viste noen overraskende resultater om rekursive sekvenser kjent som Somos-sekvenser ved å vise at de også teller noe. Gjennom kraften til kreative forbindelser oppdaget matematikere igjen hvor de kunne gå ved å forstå hvor de har vært.

Øvelser

1. Finn en lukket formel for sekvensen som er definert rekursivt som
$latex a_1 = 1$
$latex a_n = a_{n-1} + 2n – 1$

2. På slutten av kolonnen ble uttrykket $latex frac{n(n-1)}{2}$ vist å være et heltall selv om uttrykket involverer en brøk, fordi $latex frac{n(n-1 )}{2}$ er resultatet av å telle noe. Det er også et tallteoretisk argument som viser at dette uttrykket må være et heltall. Hva er det?

3. Finn de første leddene i den rekursive sekvensen
$latex a_1 = 1$
$latex a_n = frac{1}{1+a_{n-1}}$

4. Finn de første leddene i den rekursive sekvensen
$latex a_1 = 1$
$latex a_2 = 1$
$latex a_n = a_{n-1} – a_{n-2}$