Säg att du är på en fest med nio andra personer och alla skakar alla andras hand exakt en gång. Hur många handslag sker?

Det här är "handskakningsproblemet" och det är en av mina favoriter. Som matematiklärare älskar jag det eftersom det finns så många olika sätt du kan komma fram till lösningen på, och mångfalden och sammanlänkningen av dessa strategier illustrerar på ett vackert sätt kraften i kreativt tänkande i matematik.

En lösning går så här: Börja med att varje person skakar varannan persons hand. Tio personer, med nio handslag vardera, producerar 9 × 10 = 90 totalt handslag. Men detta räknar varje handslag två gånger – en gång ur varje skakares perspektiv – så det faktiska antalet handslag är $latex frac{90}{2} = 45$. Ett enkelt och härligt räkneargument för vinsten!

Det finns också ett helt annat sätt att lösa problemet. Föreställ dig att gästerna kommer en i taget och när de kommer dit skakar de hand med alla närvarande. Den första personen har inga händer att skaka, så i en enmansfest finns det noll totalt handslag. Nu kommer den andra personen och skakar hand med den första. Detta lägger till ett handslag till det totala antalet, så i en två-personers fest finns det 0 + 1 = 1 totalt handslag. När den tredje personen kommer och skakar hand med de två första gästerna, lägger detta till två handslag till summan. Den fjärde personens ankomst lägger till tre handslag till summan, och så vidare.

Denna strategi modellerar sekvensen av handslag rekursivt, vilket innebär att varje term i sekvensen definieras i förhållande till de som kommer före den. Du är förmodligen bekant med Fibonacci-sekvensen, den mest kända rekursiva sekvensen av alla. Den börjar med 1, 1, 2, 3, 5, 8, 13, 21 och fortsätter med varje efterföljande term lika med summan av de två föregående.

Som vi kommer att se nedan är rekursion ett flexibelt och kraftfullt ramverk för att tänka på ett brett spektrum av matematiska idéer. Och även om forntida indiska forskare som Hemachandra är krediterade med att veta om dessa typer av sekvenser så långt tillbaka som 1150, erbjuder de fortfarande spännande utmaningar för matematiker idag.

Låt oss se hur rekursivt tänkande hjälper till med handskakningsproblemet. Om vi ​​låter $latex a_n$ lika med antalet handslag vid an n-person part kan vi representera detta rekursiva förhållande med följande formel:

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

Detta säger oss att antalet handslag vid en n-person party ($latex a_n$) är lika med antalet handslag vid en (n − 1)-person part ($latex a_{n-1}$) plus n − 1 handslag till, som fångar tanken att när en ny person anländer lägger de till ett visst antal nya handslag till de som redan har ägt rum.

I vår speciella version av handskakningsproblemet vill vi veta $latex a_{10}$, antalet handslag på en fest med 10 personer, så för att se att vi använder det rekursiva förhållandet

$latex a_{10} = a_9 + 9$

För att hitta värdet på $latex a_{10}$ behöver vi bara veta värdet på $latex a_9$ och lägga till 9 till det. Hur hittar vi värdet på $latex a_9$? Genom att använda rekursion, förstås!

$latex a_9 = a_8 + 8$

Nu, för att hitta värdet på $latex a_8$, måste vi hitta värdet på $latex a_7$, vilket kräver att vi känner till $latex a_6$ och så vidare. Vid det här laget kan du vara orolig för att det här kommer att fortsätta för evigt i en sorts oändlig nedstigning, men när vi når $latex a_1$ är vi klara, eftersom vi vet att det finns noll totala handslag på en enmansfest.

$latex a_1 = 0$

Detta initiala eller "frövärde" är en nyckelfunktion i en rekursiv sekvens. Det garanterar att denna process att backa genom sekvensen med hjälp av det rekursiva förhållandet kommer att sluta. När du väl har träffat startvärdet upphör backtracking, och du kan sedan arbeta dig fram genom listan för att få det värde du vill ha.

$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$

Genom att arbeta igenom listan ser vi att det är totalt 45 handslag på en 10-manna fest, vilket stämmer överens med vår initiala beräkning. Om du är något som mina elever, kanske du frågar varför vi behöver ett annat sätt att lösa detta problem när vi redan vet svaret, särskilt eftersom det här andra tillvägagångssättet verkar ta längre tid.

Det är en bra fråga. Ett svar är att det rekursiva tillvägagångssättet ger oss en helt annan syn på vad som händer i det här problemet, och olika perspektiv är användbara i matematik, som de är i allt. De ger oss olika möjligheter att förstå begrepp och låter oss använda olika verktyg, vilket kan hjälpa när vi kör fast.

Framför allt är rekursion användbart eftersom det finns överallt i matematik. Det uppstår till exempel i de linjära sambanden som alla lär sig om i mattelektionen - de som kännetecknas av en konstant förändringshastighet och representeras av linjer i planet. En linjär funktion som $latex f(x) = 3x + 5$ kan ses som en rekursiv formel:

$latex a_0 = 5$

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

Även om det mer uppenbara sättet att tänka på $latex f(2)$ kan vara att $latex f(2) = 3 gånger 2 + 5 = 11$, är ett annat sätt att $latex a_2 = a_1 + 3 = a_0 + 3 + 3 = 11$. Att rekursivt modellera de grundläggande egenskaperna hos linjära funktioner - den konstanta förändringshastigheten - ger oss ett annat sätt att tänka på detta förhållande. Detsamma kan göras med exponentialfunktioner som kännetecknas av konstant multiplikativ förändring.

Rekursivt tänkande fungerar också bortom sekvenser av tal. Om du någonsin har löst ett ekvationssystem har du förmodligen använt ett rekursivt tillvägagångssätt. För att lösa systemet

$latex 2x + y = 10$

$latex 3x – y = 5$

du kan först lägga ihop de två ekvationerna för att eliminera y variabel, vilket resulterar i ekvationen $latex 5x = 15$. Lös detta för att få $latex x =$ 3, ersätt för att hitta $latex y = 4$, och du är klar. Detta tillvägagångssätt använder en rekursiv algoritm, där lösningen till ett system byggs från lösningen till mindre, relaterade system. Till exempel, för att lösa ett 3 × 3-system, eliminerar du en variabel för att förvandla det till ett 2 × 2-system och sedan igen för att göra det till ett 1 × 1-system. Denna enkla ekvation som är lätt att lösa är som startvärdet för denna rekursiva process. Det signalerar slutet på backtracking, och därifrån arbetar du dig tillbaka upp i ekvationskedjan, precis som i en rekursiv sekvens.

Det finns till och med rekursiva bevistekniker. Till exempel, en känd formel inom geometri är polygonvinkelsummans formel, som säger att summan av måtten på de inre vinklarna i en n-sidig polygon är $latex (n-2) gånger 180^{circ}$. Ett sätt att bevisa detta resultat är att börja med en n-gå och föreställ dig vad som skulle hända om du tog bort en triangel.

Om du tar bort en triangel förvandlas n-gå in i en (n − 1)-gon, och den tar också bort 180 graders inre vinkelmått. Detta är ett rekursivt förhållande: Den inre vinkelsumman för en n-gon är 180 grader mer än den inre vinkelsumman för en (n − 1)-gon. För att fastställa det allmänna resultatet, fortsätt att ta bort trianglar tills du når frövärdet, vilket i den här situationen händer när du har tagit bort alla utom tre av n-gons hörn. Vid denna tidpunkt har den initiala polygonen reducerats till en triangel, vars inre vinkelsumma är känd för att vara 180 grader. Arbeta dig nu uppåt igen, lägg till 180 grader vid varje steg, så får du formeln.

För att återvända till vårt parti, så visar själva handskakningsproblemet oss vad som är möjligt när vi tänker kreativt och sedan kopplar samman de många olika perspektiven på ett problem. Om vi ​​leker med den rekursiva modellen för vår sekvens av handslag:

$latex a_1 = 0$

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

ett fint mönster kommer fram:

$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 ett nytt, och allmänt, sätt att tänka på problemet: Antalet handslag i en n-person part är lika med summan av den första n − 1 positivt heltal.

Tänk tillbaka på vårt ursprungliga tillvägagångssätt. I en n-person fest, varje person skakar hand med den andra n − 1 person. Produkten $latex n (n-1)$ räknar varje handslag två gånger, så det totala antalet handslag är $latex frac{n(n-1)}{2}$. Men eftersom våra olika metoder räknar samma sak måste de ge samma resultat. Detta betyder särskilt:

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

Genom att koppla ihop olika förhållningssätt till handskakningsproblemet får vi en sluten formel för summan av den första n − 1 positivt heltal. Men vi får ännu mer: uttrycket $latex frac{n(n-1)}{2}$ involverar ett bråk, men eftersom det är lika med en summa av heltal måste det också vara ett heltal. Detta bevisar ett enkelt faktum inom talteorin: För varje heltal n, $latex frac{n(n-1)}{2}$ är ett heltal.

Samma typ av argument fortsätter att driva den moderna matematiken. Som ett exempel, forskare i början av 2000-talet visade några överraskande resultat om rekursiva sekvenser som kallas Somos-sekvenser genom att visa att de också räknar något. Genom kraften i kreativa kopplingar upptäckte matematiker återigen vart de kunde gå genom att förstå var de har varit.

övningar

1. Hitta en sluten formel för sekvensen som definieras rekursivt som
$latex a_1 = 1$
$latex a_n = a_{n-1} + 2n – 1$

2. I slutet av kolumnen visades uttrycket $latex frac{n(n-1)}{2}$ vara ett heltal även om uttrycket involverar en bråkdel, eftersom $latexfrac{n(n-1 )}{2}$ är resultatet av att räkna något. Det finns också ett talteoretiskt argument som visar att detta uttryck måste vara ett heltal. Vad är det?

3. Hitta de första termerna i den rekursiva sekvensen
$latex a_1 = 1$
$latex a_n = frac{1}{1+a_{n-1}}$

4. Hitta de första termerna i den rekursiva sekvensen
$latex a_1 = 1$
$latex a_2 = 1$
$latex a_n = a_{n-1} – a_{n-2}$