Matemaatika, mis ühendab selle, kus me läheme, ja kus me oleme olnud | Ajakiri Quanta

Oletame, et oled peol koos üheksa inimesega ja kõik suruvad kõigi teiste kätt täpselt ühe korra. Mitu käepigistust toimub?

See on "käepigistuse probleem" ja see on üks minu lemmikuid. Matemaatikaõpetajana meeldib see mulle, sest lahenduseni jõudmiseks on nii palju erinevaid viise ning nende strateegiate mitmekesisus ja omavaheline seotus illustreerivad kaunilt loova mõtlemise jõudu matemaatikas.

Üks lahendus on järgmine: alustage sellest, et iga inimene surub iga teise inimese kätt. Kümme inimest koos üheksa käepigistusega annavad kokku 9 × 10 = 90 käepigistust. Kuid see arvestab iga käepigistust kaks korda – üks kord iga raputaja vaatenurgast –, nii et tegelik käepigistuste arv on $lateksimurd{90}{2} = 45 $. Lihtne ja armas võiduargument!

Probleemi lahendamiseks on ka täiesti erinev viis. Kujutage ette, et külalised saabuvad ükshaaval ja kohale jõudes suruvad nad kõigi kohalviibijatega kätt. Esimesel inimesel pole kätt, mida suruda, nii et ühe inimese peol pole käepigistusi kokku null. Nüüd tuleb teine ​​inimene ja surub esimese inimesega kätt. See lisab kogusummale ühe käepigistuse, nii et kahe inimese peol on kokku 0 + 1 = 1 käepigistus. Kui saabub kolmas isik ja surub kahe esimese külalisega kätt, lisab see kogusummale kaks käepigistust. Neljanda inimese saabumine lisab kogusummale kolm käepigistust jne.

See strateegia modelleerib käepigistuste jada rekursiivselt, mis tähendab, et jada iga termin on määratletud võrreldes sellele eelnevatega. Tõenäoliselt olete tuttav Fibonacci jadaga, mis on kõige kuulsam rekursiivne jada. See algab 1, 1, 2, 3, 5, 8, 13, 21 ja jätkub iga järgmise liikmega, mis on võrdne kahe eelneva summaga.

Nagu allpool näeme, on rekursioon paindlik ja võimas raamistik paljude matemaatiliste ideede üle mõtlemiseks. Ja kuigi iidsetele India õpetlastele, nagu Hemachandrale, on omistatud teadmised seda tüüpi järjestuste kohta juba aastal 1150, pakuvad need matemaatikutele tänapäevalgi intrigeerivaid väljakutseid.

Vaatame, kuidas rekursiivne mõtlemine käepigistuse probleemi puhul aitab. Kui laseme $lateksil a_n$ võrduda käepigistuste arvuga punktis an n-isikpartei, saame seda rekursiivset suhet esindada järgmise valemiga:

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

See näitab meile, et käepigistuste arv kell n-person party ($latex a_n$) on võrdne käepigistuste arvuga (n − 1)-inimese pidu ($lateks a_{n-1}$) pluss n − Veel 1 käepigistus, mis tabab mõtet, et kui uus inimene saabub, lisab ta juba toimunud kätlemistele teatud arvu uusi käepigistusi.

Meie konkreetses käepigistuse probleemi versioonis tahame teada $latex a_{10}$, kätlemiste arvu 10-liikmelisel peol, et leida, et kasutame rekursiivset seost

$lateks a_{10} = a_9 + 9 $

$lateksi a_{10}$ väärtuse leidmiseks peame lihtsalt teadma $lateksi a_9$ väärtust ja lisama sellele 9. Kuidas leiame $lateksi a_9$ väärtuse? Muidugi rekursiooni kasutades!

$lateks a_9 = a_8 + 8 $

Nüüd, et leida $lateksi a_8$ väärtuse, peame leidma $lateksi a_7$ väärtuse, mis eeldab $lateksi a_6$ teadmist jne. Siinkohal võite olla mures, et see kestab lõputu laskumise teel igavesti, kuid kui jõuame tasemele $latex a_1$, oleme sellega valmis, sest teame, et ühe inimese peol pole käepigistust kokku.

$lateks a_1 = 0 $

See algväärtus ehk "seemne" väärtus on rekursiivse jada põhiomadus. See garanteerib, et see rekursiivset seost kasutades läbi jada tagasi liikumise protsess lõpeb. Kui olete saavutanud algväärtuse, peatub tagasiminek ja seejärel saate soovitud väärtuse saamiseks loendis edasi liikuda.

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

$lateksi cdots$

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

Nimekirja läbi töötades näeme, et 45-liikmelisel peol on kokku 10 käepigistust, mis ühtib meie esialgse arvutusega. Kui olete midagi minu õpilaste moodi, võite küsida, miks meil on vaja teist viisi selle probleemi lahendamiseks, kui me juba vastust teame, eriti kuna see teine ​​​​lähenemine näib võtab kauem aega.

See on hea küsimus. Üks vastus on, et rekursiivne lähenemine annab meile täiesti erineva ülevaate sellest, mis selles probleemis toimub, ja erinevad vaatenurgad on kasulikud matemaatikas, nagu ka kõigis asjades. Need annavad meile erinevad võimalused mõistete mõistmiseks ja võimaldavad meil kasutada erinevaid tööriistu, mis võivad aidata, kui oleme ummikus.

Eelkõige on rekursioon kasulik, kuna see on matemaatikas kõikjal. See ilmneb näiteks lineaarsetes suhetes, mida kõik matemaatikatunnis õpivad – suhetes, mida iseloomustab konstantne muutumiskiirus ja mida esindavad tasapinnal olevad jooned. Lineaarset funktsiooni nagu $latex f(x) = 3x + 5$ võib pidada rekursiivseks valemiks:

$lateks a_0 = 5 $

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

Kuigi ilmsem viis mõelda $lateksi f(2)$ kohta võib olla see, et $lateks f(2) = 3 korda 2 + 5 = 11 $, on veel üks võimalus, et $lateks a_2 = a_1 + 3 = a_0 + 3 + 3 = 11 dollarit. Lineaarsete funktsioonide põhiomaduse – konstantse muutumiskiiruse – rekursiivne modelleerimine annab meile veel ühe võimaluse selle seose üle mõelda. Sama saab teha eksponentsiaalfunktsioonidega, mida iseloomustab pidev multiplikatiivne muutus.

Rekursiivne mõtlemine töötab ka väljaspool numbrijadasid. Kui olete kunagi võrrandisüsteemi lahendanud, olete tõenäoliselt kasutanud rekursiivset lähenemist. Süsteemi lahendamiseks

$lateks 2x + y = 10 $

$lateks 3x – y = 5$

saate esmalt need kaks võrrandit kokku liita, et kõrvaldada y muutuja, mille tulemuseks on võrrand $lateks 5x = 15$. Lahendage see, et saada $lateks x = $ 3, asendage see, et leida $lateks y = 4 $ ja oletegi valmis. See lähenemisviis kasutab rekursiivset algoritmi, kus süsteemi lahendus ehitatakse lahendusest väiksemateks seotud süsteemideks. Näiteks 3 × 3 süsteemi lahendamiseks eemaldate ühe muutuja, et muuta see 2 × 2 süsteemiks, ja seejärel uuesti, et muuta see 1 × 1 süsteemiks. See lihtsalt lahendatav üksikvõrrand on nagu selle rekursiivse protsessi algväärtus. See annab märku tagasikäigu lõpust ja sealt liigute võrrandiahelas tagasi ülespoole, nagu rekursiivses järjestuses.

On isegi rekursiivseid tõestustehnikaid. Näiteks kuulus geomeetria valem on hulknurga nurga summa valem, mis ütleb, et nurga sisenurkade mõõtmete summa. n-poolne hulknurk on $lateks (n-2) korda 180^{circ}$. Üks viis selle tulemuse tõestamiseks on alustada tähega n-Kujutage ette, mis juhtuks, kui eemaldaksite kolmnurga.

Kolmnurga eemaldamine muudab n- läheb sisse (n − 1)-gon ja see eemaldab ka 180 kraadi sisenurga mõõtmise. See on rekursiivne seos: sisenurga summa an n-gon on 180 kraadi suurem kui sisenurga summa (n − 1)-gon. Üldise tulemuse kindlakstegemiseks jätkake kolmnurkade eemaldamist, kuni jõuate algväärtuseni, mis antud olukorras juhtub siis, kui olete eemaldanud kõik peale kolme n-goni tipud. Siinkohal on esialgne hulknurk taandatud kolmnurgaks, mille sisenurkade summa on teadaolevalt 180 kraadi. Nüüd liikuge tagasi üles, lisades igal sammul 180 kraadi, ja saate valemi.

Naastes meie partei juurde, näitab käepigistuse probleem ise meile, mis on võimalik, kui mõtleme loovalt ja seejärel ühendame need probleemi mitmed erinevad vaatenurgad. Kui mängime oma käepigistuste jada rekursiivse mudeliga:

$lateks a_1 = 0 $

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

ilmub ilus muster:

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

$lateksi cdots$

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

Meil on nüüd uus ja üldine viis probleemist mõelda: käepigistuste arv aastas n-isik pool on võrdne esimese summaga n − 1 positiivne täisarv.

Mõelge tagasi meie algsele lähenemisele. Aastal an n-inimene pidu, iga inimene surub teisega kätt n − 1 inimest. Toode $latex n (n-1)$ arvestab iga käepigistuse kaks korda, seega on käepigistuste koguarv $latex frac{n(n-1)}{2}$. Kuid kuna meie erinevad meetodid loevad sama asja, peavad need andma sama tulemuse. Eelkõige tähendab see järgmist:

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

Ühendades käepigistuse probleemile erinevad lähenemised, saame suletud valemi esimese summa kohta n − 1 positiivne täisarv. Kuid me saame veelgi enamat: avaldis $latex frac{n(n-1)}{2}$ hõlmab murdosa, kuid kuna see on võrdne täisarvude summaga, peab ka see olema täisarv. See tõestab lihtsat arvuteooria fakti: iga täisarvu jaoks n, $lateksi frac{n(n-1)}{2}$ on täisarv.

Sarnane argument annab jätkuvalt jõudu kaasaegsele matemaatikale. Ühe näitena uurijad 2000. aastate alguses andis üllatavaid tulemusi rekursiivsete järjestuste kohta, mida tuntakse Somose jadadena, näidates, et ka nemad loevad midagi. Loominguliste ühenduste jõu kaudu avastasid matemaatikud taas, kuhu nad võiksid jõuda, mõistes, kus nad on olnud.

Harjutused

1. Leidke suletud valem jadale, mis on rekursiivselt defineeritud kui
$lateks a_1 = 1 $
$lateks a_n = a_{n-1} + 2n – 1$

2. Veeru lõpus näidati, et avaldis $latex frac{n(n-1)}{2}$ on täisarv, kuigi avaldis sisaldab murdosa, sest $latex frac{n(n-1 )}{2}$ on millegi loendamise tulemus. Samuti on arvuteooria argument, mis näitab, et see avaldis peab olema täisarv. Mis see on?

3. Leidke rekursiivse jada paar esimest liiget
$lateks a_1 = 1 $
$lateks a_n = murd{1}{1+a_{n-1}}$

4. Leidke rekursiivse jada paar esimest liiget
$lateks a_1 = 1 $
$lateks a_2 = 1 $
$lateks a_n = a_{n-1} – a_{n-2}$