Matematika, ki povezuje, kam gremo in kje smo že bili | Revija Quanta

Recimo, da ste na zabavi z devetimi drugimi ljudmi in se vsi rokujejo z vsemi natanko enkrat. Koliko stiskov rok se zgodi?

To je "problem rokovanja" in je eden mojih najljubših. Kot učitelju matematike mi je všeč, ker obstaja toliko različnih načinov, kako lahko prideš do rešitve, raznolikost in medsebojna povezanost teh strategij pa lepo ponazarjata moč kreativnega razmišljanja v matematiki.

Ena rešitev je takole: začnite tako, da vsaka oseba stisne roko vsaki drugi osebi. Deset ljudi, vsak z devetimi rokovanji, ustvari 9 × 10 = 90 rokovanj. Vendar to vsako rokovanje šteje dvakrat – enkrat z vidika vsakega stresalca – tako da je dejansko število rokovanja $latex frac{90}{2} = 45$. Preprost in ljubek argument za štetje za zmago!

Obstaja tudi povsem drugačen način za rešitev problema. Predstavljajte si, da gostje prihajajo eden za drugim in ko pridejo tja, se rokujejo z vsemi prisotnimi. Prva oseba se nima rokovati, tako da na zabavi za eno osebo ni vseh rokovanj. Zdaj pride druga oseba in se rokuje s prvo osebo. To skupnemu številu prišteje eno rokovanje, tako da je na zabavi za dve osebi skupno 0 + 1 = 1 rokovanje. Ko pride tretja oseba in se rokuje s prvima dvema gostoma, to k skupnemu seštevku doda dva stiska rok. Prihod četrte osebe k skupnemu seštevku doda tri stiske rok in tako naprej.

Ta strategija modelira zaporedje rokovanja rekurzivno, kar pomeni, da je vsak izraz v zaporedju definiran glede na tiste, ki so pred njim. Verjetno poznate Fibonaccijevo zaporedje, najbolj znano rekurzivno zaporedje vseh. Začne se z 1, 1, 2, 3, 5, 8, 13, 21 in se nadaljuje z vsakim naslednjim členom, ki je enak vsoti prejšnjih dveh.

Kot bomo videli v nadaljevanju, je rekurzija prilagodljiv in zmogljiv okvir za razmišljanje o širokem naboru matematičnih idej. In čeprav so stari indijski učenjaki, kot je Hemachandra, zaslužni, da so poznali tovrstna zaporedja že leta 1150, še vedno ponujajo zanimive izzive za matematike danes.

Poglejmo, kako rekurzivno razmišljanje pomaga pri težavi z rokovanjem. Če pustimo, da je $latex a_n$ enako številu rokovanja pri an n-oseba stranka, lahko to rekurzivno razmerje predstavimo z naslednjo formulo:

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

To nam pove, da je število rokovanj pri an n-osebna zabava ($latex a_n$) je enako številu rokovanj na (n − 1)-osebna zabava ($latex a_{n-1}$) plus n − Še 1 rokovanje, ki zajame idejo, da ko pride nova oseba, doda določeno število novih rokovanj tistim, ki so se že zgodila.

V naši posebni različici problema rokovanja želimo vedeti $latex a_{10}$, število rokovanj na zabavi za 10 oseb, tako da ugotovimo, da uporabljamo rekurzivno razmerje

$lateks a_{10} = a_9 + 9$

Da bi našli vrednost $latex a_{10}$, moramo vedeti samo vrednost $latex a_9$ in ji dodati 9. Kako najdemo vrednost $latex a_9$? Z uporabo rekurzije, seveda!

$lateks a_9 = a_8 + 8$

Zdaj, da bi našli vrednost $latex a_8$, moramo najti vrednost $latex a_7$, kar zahteva poznavanje $latex a_6$ in tako naprej. Na tej točki vas morda skrbi, da bo to trajalo večno v nekakšnem neskončnem padanju, a ko dosežemo $latex a_1$, smo končali, saj vemo, da na zabavi za eno osebo ni rokovanja nič.

$lateks a_1 = 0$

Ta začetna ali "semenska" vrednost je ključna lastnost rekurzivnega zaporedja. Zagotavlja, da se bo ta proces vračanja skozi zaporedje z uporabo rekurzivnega odnosa končal. Ko dosežete začetno vrednost, se vračanje ustavi in ​​nato se lahko pomikate naprej po seznamu, da dobite želeno vrednost.

$lateks a_1 = 0$

$lateks a_2 = a_1 + 1 = 0 + 1 = 1$

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

$lateks a_4 = a_3 + 3 = 3 + 3 = 6$

$latex cdots$

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

Če pregledamo seznam, vidimo, da je na zabavi za 45 oseb skupno 10 rokovanj, kar se ujema z našim začetnim izračunom. Če ste kakorkoli podobni mojim učencem, se boste morda vprašali, zakaj potrebujemo drug način za rešitev tega problema, ko že poznamo odgovor, zlasti ker se zdi, da ta drugi pristop traja dlje.

To je dobro vprašanje. Eden od odgovorov je, da nam rekurzivni pristop daje povsem drugačen pogled na dogajanje v tej težavi in ​​da so različne perspektive uporabne v matematiki, kot so v vseh stvareh. Dajejo nam različne priložnosti za razumevanje konceptov in nam omogočajo uporabo različnih orodij, ki nam lahko pomagajo, ko smo obtičali.

Zlasti rekurzija je uporabna, ker je povsod v matematiki. Pojavi se na primer v linearnih razmerjih, ki se jih vsi učijo pri pouku matematike - tistih, za katere je značilna stalna stopnja spreminjanja in jih predstavljajo črte v ravnini. Linearno funkcijo, kot je $latex f(x) = 3x + 5$, si lahko predstavljamo kot rekurzivno formulo:

$lateks a_0 = 5$

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

Čeprav je bolj očiten način razmišljanja o $latex f(2)$ ta, da je $latex f(2) = 3 krat 2 + 5 = 11$, je drug način ta, da je $latex a_2 = a_1 + 3 = a_0 + 3 + 3 = 11 dolarjev. Rekurzivno modeliranje temeljne značilnosti linearnih funkcij – stalne stopnje spreminjanja – nam daje drugačen način razmišljanja o tem odnosu. Enako lahko storimo z eksponentnimi funkcijami, za katere je značilna stalna multiplikativna sprememba.

Rekurzivno razmišljanje deluje tudi onkraj zaporedij številk. Če ste kdaj rešili sistem enačb, ste verjetno uporabili rekurziven pristop. Za rešitev sistema

$lateks 2x + y = 10$

$lateks 3x – y = 5$

lahko najprej seštejete obe enačbi, da odpravite y spremenljivko, kar ima za posledico enačbo $latex 5x = 15$. Rešite to, da dobite $latex x =$3, zamenjajte, da najdete $latex y = 4$, in končali ste. Ta pristop uporablja rekurzivni algoritem, kjer je rešitev za sistem zgrajena iz rešitve za manjše, povezane sisteme. Če želite na primer rešiti sistem 3 × 3, izločite eno spremenljivko, da jo spremenite v sistem 2 × 2, in nato znova, da jo spremenite v sistem 1 × 1. Ta enostavna enačba, ki jo je enostavno rešiti, je kot začetna vrednost tega rekurzivnega procesa. Označuje konec vračanja nazaj, od tam pa se vrnete po verigi enačb, tako kot v rekurzivnem zaporedju.

Obstajajo celo rekurzivne dokazne tehnike. Znana formula v geometriji je na primer formula vsote kotov mnogokotnika, ki pravi, da je vsota mer notranjih kotov n-stranski poligon je $lateks (n-2) krat 180^{circ}$. Eden od načinov za dokaz tega rezultata je, da začnete z an n-gon in si predstavljajte, kaj bi se zgodilo, če bi odstranili trikotnik.

Odstranitev trikotnika obrne n-zašel v (n − 1)-kotnik, odstrani pa tudi 180 stopinj notranje mere kota. To je rekurzivno razmerje: vsota notranjih kotov za an n-gon je 180 stopinj večji od vsote notranjih kotov za (n − 1)-kotnik. Če želite določiti splošni rezultat, odstranjujte trikotnike, dokler ne dosežete semenske vrednosti, kar se v tej situaciji zgodi, ko ste odstranili vse trikotnike razen treh n-gonova oglišča. Na tej točki je bil začetni mnogokotnik zmanjšan na trikotnik, katerega vsota notranjih kotov je 180 stopinj. Zdaj se vrnite navzgor in pri vsakem koraku dodajte 180 stopinj in dobili boste formulo.

Če se vrnemo k naši zabavi, nam sama težava rokovanja pokaže, kaj je mogoče, če kreativno razmišljamo in nato skupaj povežemo več različnih perspektiv problema. Če se poigramo z rekurzivnim modelom za naše zaporedje rokovanja:

$lateks a_1 = 0$

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

nastane lep vzorec:

$lateks a_2 = a_1 + 1 = 0 + 1$

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

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

$latex cdots$

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

Zdaj imamo nov in splošen način razmišljanja o problemu: število rokovanj v n-oseba stranka je enaka vsoti prve n − 1 pozitivna cela števila.

Pomislite nazaj na naš prvotni pristop. V an n-osebna zabava, vsaka oseba se bo rokovala z drugo n − 1 oseba. Produkt $latex n (n-1)$ šteje vsako rokovanje dvakrat, tako da je skupno število rokovanja $latex frac{n(n-1)}{2}$. Ker pa naše različne metode štejejo isto stvar, morajo dati enak rezultat. To zlasti pomeni:

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

S povezovanjem različnih pristopov k problemu rokovanja dobimo zaprto formulo za vsoto prvega n − 1 pozitivna cela števila. Dobimo pa še več: izraz $latex frac{n(n-1)}{2}$ vključuje ulomek, a ker je enak vsoti celih števil, mora biti tudi celo število. To dokazuje preprosto dejstvo teorije števil: Za vsako celo število n, $latex frac{n(n-1)}{2}$ je celo število.

Ta ista vrsta argumentov še naprej poganja sodobno matematiko. Na primer, raziskovalci v začetku leta 2000 dokazal nekaj presenetljivih rezultatov o rekurzivnih zaporedjih, znanih kot zaporedja Somos, tako da pokažejo, da tudi ta nekaj štejejo. Z močjo ustvarjalnih povezav so matematiki znova odkrili, kam bi lahko prišli, če bi razumeli, kje so bili.

vaje

1. Poiščite zaprto formulo za zaporedje, ki je rekurzivno definirano kot
$lateks a_1 = 1$
$lateks a_n = a_{n-1} + 2n – 1$

2. Na koncu stolpca je bilo prikazano, da je izraz $latex frac{n(n-1)}{2}$ celo število, čeprav izraz vključuje ulomek, ker $latex frac{n(n-1 )}{2}$ je rezultat štetja nečesa. Obstaja tudi argument teorije števil, ki kaže, da mora biti ta izraz celo število. Kaj je to?

3. Poiščite prvih nekaj členov rekurzivnega zaporedja
$lateks a_1 = 1$
$lateks a_n = frac{1}{1+a_{n-1}}$

4. Poiščite prvih nekaj členov rekurzivnega zaporedja
$lateks a_1 = 1$
$lateks a_2 = 1$
$lateks a_n = a_{n-1} – a_{n-2}$