Matematiikka, joka yhdistää sen, missä olemme menossa, ja missä olemme olleet | Quanta-lehti

Oletetaan, että olet juhlissa yhdeksän muun ihmisen kanssa ja jokainen puristaa toisten kättä täsmälleen kerran. Kuinka monta kädenpuristusta tapahtuu?

Tämä on "kättelyongelma", ja se on yksi suosikeistani. Matematiikan opettajana rakastan sitä, koska ratkaisuun voi päästä niin monilla eri tavoilla, ja näiden strategioiden monimuotoisuus ja keskinäiset yhteydet kuvaavat kauniisti luovan ajattelun voimaa matematiikassa.

Yksi ratkaisu menee näin: Aloita siten, että jokainen puristaa jokaisen toisen kättä. Kymmenen ihmistä, kukin yhdeksän kättelyä, tuottaa 9 × 10 = 90 kättelyä yhteensä. Mutta tämä laskee jokaisen kättelyn kahdesti - kerran jokaisen ravistajan näkökulmasta - joten todellinen kättelyjen määrä on $lateksimurto{90}{2} = 45 $. Yksinkertainen ja kaunis laskenta-argumentti voitolle!

On myös täysin erilainen tapa ratkaista ongelma. Kuvittele, että vieraat saapuvat yksi kerrallaan, ja kun he saapuvat paikalle, he kättelevät kaikkia läsnä olevia. Ensimmäisellä henkilöllä ei ole käsiä kättelyssä, joten yhden hengen juhlissa ei ole yhteensä nolla kättelyä. Nyt toinen henkilö saapuu ja kättelee ensimmäistä henkilöä. Tämä lisää yhden kättelyn kokonaismäärään, joten kahden hengen juhlissa on yhteensä 0 + 1 = 1 kättely. Kun kolmas henkilö saapuu ja kättelee kahden ensimmäisen vieraan kanssa, tämä lisää kaksi kädenpuristusta kokonaismäärään. Neljännen henkilön saapuminen lisää kokonaismäärään kolme kättelyä ja niin edelleen.

Tämä strategia mallintaa kättelyjen sarjaa rekursiivisesti, mikä tarkoittaa, että sekvenssin jokainen termi on määritelty suhteessa niitä edeltäviin termeihin. Tunnet luultavasti Fibonacci-sekvenssin, tunnetuimman rekursiivisen sekvenssin. Se alkaa 1, 1, 2, 3, 5, 8, 13, 21 ja jatkuu jokaisen seuraavan termin kanssa, joka on yhtä suuri kuin kahden edellisen summa.

Kuten alla nähdään, rekursio on joustava ja tehokas kehys monenlaisten matemaattisten ideoiden ajattelemiseen. Ja vaikka muinaisten intialaisten tutkijoiden, kuten Hemachandran, uskotaan tietävän tällaisista sekvensseistä jo vuonna 1150, he tarjoavat yhä kiehtovia haasteita matemaatikoille tänä päivänä.

Katsotaan kuinka rekursiivinen ajattelu auttaa kättelyongelmassa. Jos annamme $lateksin a_n$ yhtä suureksi kuin kättelyjen määrä kohdassa an n-henkilö osapuoli, voimme esittää tämän rekursiivisen suhteen seuraavalla kaavalla:

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

Tämä kertoo meille, että kädenpuristusten määrä on n-henkilöjuhla ($lateksi a_n$) on yhtä suuri kuin kättelyjen määrä (n − 1) hengen juhla ($lateksi a_{n-1}$) plus n − 1 kädenpuristus lisää, vangiten ajatus siitä, että kun uusi henkilö saapuu, he lisäävät tietyn määrän uusia kättelyjä jo tapahtuneisiin.

Erityisessä kättelyongelman versiossamme haluamme tietää $lateksi a_{10}$, kättelyjen lukumäärän 10 hengen juhlissa, jotta huomaamme, että käytämme rekursiivista suhdetta

$lateksi a_{10} = a_9 + 9 $

Löytääksemme $lateksin a_{10}$ arvon, meidän on vain tiedettävä $lateksi a_9$ arvo ja lisättävä siihen 9. Kuinka löydämme $lateksin a_9$ arvon? Tietenkin käyttämällä rekursiota!

$lateksi a_9 = a_8 + 8$

Nyt löytääksemme $lateksi a_8$ arvon, meidän on löydettävä $lateksi a_7$ arvo, mikä edellyttää $lateksi a_6$ ja niin edelleen tuntemista. Tässä vaiheessa saatat olla huolissasi siitä, että tämä jatkuu ikuisesti eräänlaisena äärettömänä laskeutumisena, mutta kun saavutamme $latex a_1$, olemme valmiita, koska tiedämme, että yhden hengen juhlissa ei ole yhteensä nolla kädenpuristusta.

$lateksi a_1 = 0 $

Tämä alku- tai "siemen"-arvo on rekursiivisen sekvenssin keskeinen ominaisuus. Se takaa, että tämä rekursiivista suhdetta käyttävän sekvenssin paluuprosessi päättyy. Kun saavutat siemenarvon, paluu pysähtyy, ja voit jatkaa eteenpäin luettelossa saadaksesi haluamasi arvon.

$lateksi a_1 = 0 $

$lateksi a_2 = a_1 + 1 = 0 + 1 = 1 $

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

$lateksi a_4 = a_3 + 3 = 3 + 3 = 6 $

$lateksi cdots$

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

Käsittelemällä listaa näemme, että 45 hengen juhlissa on yhteensä 10 kättelyä, mikä on yhtäpitävä alkuperäisen laskelmamme kanssa. Jos olet oppilaideni kaltainen, saatat kysyä, miksi tarvitsemme toisen tavan ratkaista tämä ongelma, kun tiedämme jo vastauksen, varsinkin kun tämä toinen lähestymistapa näyttää kestävän kauemmin.

Se on hyvä kysymys. Yksi vastaus on, että rekursiivinen lähestymistapa antaa meille täysin erilaisen kuvan siitä, mitä tässä ongelmassa tapahtuu, ja erilaiset näkökulmat ovat hyödyllisiä matematiikassa, kuten kaikissa asioissa. Ne antavat meille erilaisia ​​mahdollisuuksia ymmärtää käsitteitä ja antavat meille mahdollisuuden käyttää erilaisia ​​työkaluja, jotka voivat auttaa, kun olemme jumissa.

Erityisesti rekursio on hyödyllinen, koska se on kaikkialla matematiikassa. Se syntyy esimerkiksi lineaarisissa suhteissa, joista kaikki oppivat matematiikan tunnilla - niissä, joille on ominaista jatkuva muutosnopeus ja joita edustavat tason viivat. Lineaarista funktiota, kuten $lateksi f(x) = 3x + 5$, voidaan pitää rekursiivisena kaavana:

$lateksi a_0 = 5 $

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

Vaikka ilmeisempi tapa ajatella $lateksi f(2)$ voi olla, että $lateksi f(2) = 3 kertaa 2 + 5 = 11$, toinen tapa on, että $lateksi a_2 = a_1 + 3 = a_0 + 3 + 3 = 11 dollaria. Lineaaristen funktioiden perusominaisuuden – vakiomuutosnopeuden – rekursiivinen mallintaminen antaa meille toisen tavan ajatella tätä suhdetta. Sama voidaan tehdä eksponentiaalisilla funktioilla, joille on ominaista jatkuva kertova muutos.

Rekursiivinen ajattelu toimii myös lukujonojen ulkopuolella. Jos olet joskus ratkaissut yhtälöjärjestelmän, olet todennäköisesti käyttänyt rekursiivista lähestymistapaa. Järjestelmän ratkaisemiseksi

$lateksi 2x + y = 10 $

$lateksi 3x – y = 5$

voit ensin lisätä kaksi yhtälöä yhteen poistaaksesi y muuttuja, joka johtaa yhtälöön $lateksi 5x = 15$. Ratkaise tämä saadaksesi $lateksi x = $ 3, korvaa se löytääksesi $lateksi y = 4 $, ja olet valmis. Tämä lähestymistapa hyödyntää rekursiivista algoritmia, jossa järjestelmän ratkaisu rakennetaan ratkaisusta pienempiin, toisiinsa liittyviin järjestelmiin. Esimerkiksi ratkaistaksesi 3 × 3 -järjestelmän, poistat yhden muuttujan muuttaaksesi sen 2 × 2 -järjestelmäksi ja sitten taas muuttaaksesi sen 1 × 1 -järjestelmäksi. Tämä helposti ratkaistava yksittäinen yhtälö on kuin tämän rekursiivisen prosessin alkuarvo. Se ilmaisee paluumatkan päättymisen, ja siitä eteenpäin palaat yhtälöketjua ylöspäin, aivan kuten rekursiivisessa sekvenssissä.

On jopa rekursiivisia todistustekniikoita. Esimerkiksi kuuluisa geometrian kaava on monikulmion kulmien summakaava, joka sanoo, että sisäkulmien mittojen summa n-sivuinen polygoni on $lateksi (n-2) kertaa 180^{circ}$. Yksi tapa todistaa tämä tulos on aloittaa a n-Kuvittele, mitä tapahtuisi, jos poistaisit kolmion.

Kolmion poistaminen kääntää n-menee (n − 1)-gon, ja se poistaa myös 180 astetta sisäkulmamittauksen. Tämä on rekursiivinen suhde: Sisäkulman summa an n-gon on 180 astetta suurempi kuin sisäkulman summa (n − 1)-gon. Yleisen tuloksen määrittämiseksi jatka kolmioiden poistamista, kunnes saavutat siemenarvon, mikä tässä tilanteessa tapahtuu, kun olet poistanut kaikki kolmea lukuun ottamatta. n-gonin kärjet. Tässä vaiheessa alkuperäinen monikulmio on pienennetty kolmioksi, jonka sisäkulman summan tiedetään olevan 180 astetta. Palaa nyt ylös ja lisää 180 astetta jokaiseen vaiheeseen, niin saat kaavan.

Palatakseni puolueeseemme, itse kädenpuristusongelma näyttää meille, mikä on mahdollista, kun ajattelemme luovasti ja sitten yhdistämme ongelman useat erilaiset näkökulmat. Jos leikitään kädenpuristussarjamme rekursiivisen mallin kanssa:

$lateksi a_1 = 0 $

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

hieno kuvio syntyy:

$lateksi a_2 = a_1 + 1 = 0 + 1 $

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

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

$lateksi cdots$

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

Meillä on nyt uusi ja yleinen tapa ajatella ongelmaa: kättelyjen määrä n-henkilö osapuoli on yhtä suuri kuin ensimmäisen summa n − 1 positiivinen kokonaisluku.

Ajattele alkuperäistä lähestymistapaamme. Vuonna an n-henkilöjuhlat, jokainen kättelee toisiaan n − 1 henkilöä. Tuote $lateksi n (n-1)$ laskee jokaisen kättelyn kahdesti, joten kättelyjen kokonaismäärä on $lateksi frac{n(n-1)}{2}$. Mutta koska erilaiset menetelmämme laskevat saman asian, niiden on tuotettava sama tulos. Tämä tarkoittaa erityisesti:

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

Yhdistämällä erilaisia ​​lähestymistapoja kättelyongelmaan, saamme suljetun kaavan ensimmäisen summalle n − 1 positiivinen kokonaisluku. Mutta saamme vielä enemmän: lauseke $lateksi frac{n(n-1)}{2}$ sisältää murto-osan, mutta koska se on yhtä suuri kuin kokonaislukujen summa, myös sen on oltava kokonaisluku. Tämä todistaa yksinkertaisen lukuteorian tosiasian: Jokaiselle kokonaisluvulle n, $lateksi frac{n(n-1)}{2}$ on kokonaisluku.

Samanlainen argumentti jatkaa nykyaikaista matematiikkaa. Yhtenä esimerkkinä tutkijat 2000-luvun alussa sai yllättäviä tuloksia Somos-sekvensseinä tunnetuista rekursiivisista sekvensseistä osoittamalla, että nekin laskevat jotain. Luovien yhteyksien avulla matemaatikot löysivät jälleen, minne he voisivat mennä ymmärtämällä, missä he ovat olleet.

Harjoitukset

1. Etsi suljettu kaava sekvenssille, joka määritellään rekursiivisesti
$lateksi a_1 = 1 $
$lateksi a_n = a_{n-1} + 2n – 1$

2. Sarakkeen lopussa lauseke $lateksi frac{n(n-1)}{2}$ on kokonaisluku, vaikka lauseke sisältää murtoluvun, koska $lateksi frac{n(n-1 )}{2}$ on tulos laskemalla jotain. On myös lukuteoria-argumentti, joka osoittaa, että tämän lausekkeen on oltava kokonaisluku. Mikä se on?

3. Etsi rekursiivisen sekvenssin muutama ensimmäinen termi
$lateksi a_1 = 1 $
$lateksi a_n = frac{1}{1+a_{n-1}}$

4. Etsi rekursiivisen sekvenssin muutama ensimmäinen termi
$lateksi a_1 = 1 $
$lateksi a_2 = 1 $
$lateksi a_n = a_{n-1} – a_{n-2}$