Wiskunde die verbindt waar we naartoe gaan en waar we zijn geweest | Quanta-tijdschrift

Stel dat je met negen andere mensen op een feestje bent en iedereen schudt iedereen precies één keer de hand. Hoeveel handdrukken vinden plaats?

Dit is het 'handdrukprobleem' en het is een van mijn favorieten. Als wiskundeleraar vind ik het geweldig omdat er zoveel verschillende manieren zijn waarop je tot de oplossing kunt komen, en de diversiteit en onderlinge verbondenheid van die strategieën illustreren prachtig de kracht van creatief denken in wiskunde.

Eén oplossing gaat als volgt: begin met het schudden van de hand van elke andere persoon. Tien mensen, met elk negen handdrukken, produceren in totaal 9 × 10 = 90 handdrukken. Maar hierbij wordt elke handdruk twee keer geteld (één keer vanuit het perspectief van elke schudder), dus het werkelijke aantal handdrukken is $latex frac{90}{2} = 45$. Een eenvoudig en mooi telargument voor de overwinning!

Er is ook een heel andere manier om het probleem op te lossen. Stel je voor dat de gasten één voor één arriveren, en als ze daar aankomen, schudden ze alle aanwezigen de hand. De eerste persoon heeft geen handen om te schudden, dus in een eenpersoonsfeest zijn er in totaal nul handdrukken. Nu arriveert de tweede persoon en schudt de hand van de eerste persoon. Dit voegt één handdruk toe aan het totaal, dus in een gezelschap van twee personen zijn er in totaal 0 + 1 = 1 handdrukken. Wanneer de derde persoon arriveert en de eerste twee gasten de hand schudt, worden er twee handdrukken opgeteld bij het totaal. De komst van de vierde persoon voegt drie handdrukken toe aan het totaal, enzovoort.

Deze strategie modelleert de reeks handdrukken recursief, wat betekent dat elke term in de reeks wordt gedefinieerd ten opzichte van de termen die eraan voorafgaan. Je bent waarschijnlijk bekend met de Fibonacci-reeks, de beroemdste recursieve reeks van allemaal. Het begint met 1, 1, 2, 3, 5, 8, 13, 21 en gaat verder met elke volgende term die gelijk is aan de som van de voorgaande twee.

Zoals we hieronder zullen zien, is recursie een flexibel en krachtig raamwerk voor het nadenken over een breed scala aan wiskundige ideeën. En ook al wordt aangenomen dat oude Indiase geleerden zoals Hemachandra al in 1150 op de hoogte waren van dit soort reeksen, ze bieden hedendaagse wiskundigen nog steeds intrigerende uitdagingen.

Laten we eens kijken hoe recursief denken helpt bij het handdrukprobleem. Als we $latex a_n$ gelijk laten zijn aan het aantal handdrukken bij an n-persoon partij, kunnen we deze recursieve relatie weergeven met de volgende formule:

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

Dit vertelt ons dat het aantal handdrukken bij een n-person party ($latex a_n$) is gelijk aan het aantal handdrukken bij een (n − 1)-persoonsfeestje ($latex a_{n-1}$) plus n − Nog 1 handdruk, waarbij het idee wordt vastgelegd dat wanneer een nieuwe persoon arriveert, hij of zij een bepaald aantal nieuwe handdrukken toevoegt aan de handdrukken die al hebben plaatsgevonden.

In onze specifieke versie van het handdrukprobleem willen we $latex a_{10}$ weten, het aantal handdrukken op een feestje met tien personen, om te ontdekken dat we de recursieve relatie gebruiken

$latex a_{10} = a_9 + 9$

Om de waarde van $latex a_{10}$ te vinden, hoeven we alleen maar de waarde van $latex a_9$ te kennen en er 9 bij op te tellen. Hoe vinden we de waarde van $latex a_9$? Door gebruik te maken van recursie natuurlijk!

$latex a_9 = a_8 + 8$

Om nu de waarde van $latex a_8$ te vinden, moeten we de waarde van $latex a_7$ vinden, waarvoor we $latex a_6$ moeten kennen, enzovoort. Op dit punt ben je misschien bang dat dit voor altijd zal doorgaan in een soort oneindige afdaling, maar zodra we $latex a_1$ bereiken, zijn we klaar, omdat we weten dat er in totaal geen handdrukken zijn op een eenpersoonsfeestje.

$latex a_1 = 0$

Deze initiële of ‘zaad’-waarde is een belangrijk kenmerk van een recursieve reeks. Het garandeert dat dit proces van teruggaan door de reeks met behulp van de recursieve relatie zal eindigen. Zodra u de startwaarde bereikt, stopt het teruglopen en kunt u vervolgens door de lijst heen werken om de gewenste waarde te krijgen.

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

Als we de lijst doornemen, zien we dat er in totaal 45 handdrukken zijn op een feestje van 10 personen, wat overeenkomt met onze aanvankelijke berekening. Als je op mijn studenten lijkt, vraag je je misschien af ​​waarom we een andere manier nodig hebben om dit probleem op te lossen, terwijl we het antwoord al weten, vooral omdat deze tweede aanpak langer lijkt te duren.

Het is een goede vraag. Eén antwoord is dat de recursieve benadering ons een heel ander beeld geeft van wat er in dit probleem aan de hand is, en dat verschillende perspectieven nuttig zijn bij wiskunde, zoals bij alle dingen. Ze bieden ons verschillende mogelijkheden om concepten te begrijpen en stellen ons in staat verschillende hulpmiddelen te gebruiken die kunnen helpen als we vastlopen.

In het bijzonder is recursie nuttig omdat het overal in de wiskunde voorkomt. Het ontstaat bijvoorbeeld in de lineaire relaties waar iedereen in de wiskundeles over leert – de relaties die worden gekenmerkt door een constante snelheid van verandering en worden weergegeven door lijnen in het vlak. Een lineaire functie zoals $latex f(x) = 3x + 5$ kan worden gezien als een recursieve formule:

$latex a_0 = 5$

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

Hoewel de meer voor de hand liggende manier om over $latex f(2)$ te denken kan zijn dat $latex f(2) = 3 keer 2 + 5 = 11$, is een andere manier dat $latex a_2 = a_1 + 3 = a_0 + 3 + 3 = 11$. Het recursief modelleren van het fundamentele kenmerk van lineaire functies – de constante veranderingssnelheid – geeft ons een andere manier om over deze relatie na te denken. Hetzelfde kan worden gedaan met exponentiële functies die worden gekenmerkt door constante multiplicatieve verandering.

Recursief denken werkt ook buiten de reeks getallen. Als je ooit een stelsel vergelijkingen hebt opgelost, heb je waarschijnlijk een recursieve aanpak toegepast. Om het systeem op te lossen

$latex 2x + y = 10$

$latex 3x – y = 5$

je kunt eerst de twee vergelijkingen bij elkaar optellen om de vergelijkingen te elimineren y variabele, wat resulteert in de vergelijking $latex 5x = 15$. Los dit op om $latex x =$ 3 te krijgen, vervang dit om $latex y = 4$ te vinden, en je bent klaar. Deze aanpak maakt gebruik van een recursief algoritme, waarbij de oplossing voor een systeem wordt opgebouwd vanuit de oplossing naar kleinere, gerelateerde systemen. Om bijvoorbeeld een 3×3-systeem op te lossen, elimineert u één variabele om er een 2×2-systeem van te maken, en vervolgens weer om er een 1×1-systeem van te maken. Deze eenvoudig op te lossen enkele vergelijking is als de startwaarde van dit recursieve proces. Het geeft het einde aan van het teruggaan, en van daaruit werk je terug omhoog in de reeks vergelijkingen, net als in een recursieve reeks.

Er zijn zelfs recursieve bewijstechnieken. Een bekende formule in de meetkunde is bijvoorbeeld de somformule van de polygoonhoek, die zegt dat de som van de afmetingen van de binnenhoeken van een n-zijdige veelhoek is $latex (n-2) maal 180^{circ}$. Een manier om dit resultaat te bewijzen is door te beginnen met a n-gon en stel je voor wat er zou gebeuren als je een driehoek zou verwijderen.

Als u een driehoek verwijdert, wordt de n-gaan in een (n − 1)-gon, en het verwijdert ook de binnenhoekmaat van 180 graden. Dit is een recursieve relatie: de som van de binnenhoek voor an n-gon is 180 graden meer dan de som van de binnenhoek voor een (n − 1)-hoek. Om het algemene resultaat vast te stellen, blijf je driehoeken verwijderen totdat je de beginwaarde bereikt, wat in deze situatie gebeurt als je op drie na alle driehoeken hebt verwijderd. n-gon's hoekpunten. Op dit punt is de initiële polygoon teruggebracht tot een driehoek, waarvan bekend is dat de som van de binnenhoek 180 graden is. Werk nu terug naar boven en voeg bij elke stap 180 graden toe, en je krijgt de formule.

Terugkerend naar onze partij: het handdrukprobleem zelf laat ons zien wat mogelijk is als we creatief denken en vervolgens die verschillende perspectieven op een probleem met elkaar verbinden. Als we spelen met het recursieve model voor onze reeks handdrukken:

$latex a_1 = 0$

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

er ontstaat een mooi patroon:

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

We hebben nu een nieuwe en algemene manier om over het probleem na te denken: het aantal handdrukken in een n-persoonpartij is gelijk aan de som van de eerste n − 1 positieve gehele getallen.

Denk eens terug aan onze oorspronkelijke aanpak. In een n-persoonlijk feest, iedereen zal de ander de hand schudden n − 1 personen. Het product $latex n (n-1)$ telt elke handdruk twee keer, dus het totale aantal handdrukken is $latex frac{n(n-1)}{2}$. Maar omdat onze verschillende methoden hetzelfde tellen, moeten ze hetzelfde resultaat opleveren. Dit betekent in het bijzonder:

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

Door verschillende benaderingen van het handdrukprobleem met elkaar te verbinden, krijgen we een gesloten formule voor de som van de eerste n − 1 positieve gehele getallen. Maar we krijgen nog meer: ​​de uitdrukking $latex frac{n(n-1)}{2}$ omvat een breuk, maar omdat deze gelijk is aan een som van gehele getallen, moet deze ook een geheel getal zijn. Dit bewijst een simpel feit uit de getaltheorie: voor elk geheel getal n, $latex frac{n(n-1)}{2}$ is een geheel getal.

Ditzelfde soort argument is nog steeds de drijvende kracht achter de moderne wiskunde. Een voorbeeld: onderzoekers begin jaren 2000 enkele verrassende resultaten opgeleverd over recursieve reeksen die bekend staan ​​als Somos-reeksen, door te laten zien dat ook zij iets tellen. Door de kracht van creatieve verbindingen ontdekten wiskundigen opnieuw waar ze heen konden gaan door te begrijpen waar ze zijn geweest.

Oefeningen

1. Zoek een gesloten formule voor de reeks die recursief is gedefinieerd als
$latex a_1 = 1$
$latex a_n = a_{n-1} + 2n – 1$

2. Aan het einde van de kolom bleek de uitdrukking $latex frac{n(n-1)}{2}$ een geheel getal te zijn, ook al bevat de uitdrukking een breuk, omdat $latex frac{n(n-1 )}{2}$ is het resultaat van het tellen van iets. Er is ook een getaltheorie-argument dat aantoont dat deze uitdrukking een geheel getal moet zijn. Wat is het?

3. Zoek de eerste paar termen van de recursieve reeks
$latex a_1 = 1$
$latex a_n = frac{1}{1+a_{n-1}}$

4. Zoek de eerste paar termen van de recursieve reeks
$latex a_1 = 1$
$latex a_2 = 1$
$latex a_n = a_{n-1} – a_{n-2}$