Matematika, amely összeköti, hol tartunk, ahol voltunk | Quanta Magazin

Tegyük fel, hogy kilenc másik emberrel veszel részt egy partin, és mindenki pontosan egyszer fog kezet a többiekkel. Hány kézfogás történik?

Ez a „kézfogás probléma”, és ez az egyik kedvencem. Matematikatanárként azért szeretem, mert nagyon sokféleképpen lehet eljutni a megoldáshoz, és ezeknek a stratégiáknak a sokfélesége és összekapcsolódása gyönyörűen szemlélteti a kreatív gondolkodás erejét a matematikában.

Az egyik megoldás így hangzik: Kezdje azzal, hogy mindenki kezet fog a többiekkel. Tíz ember kilenc kézfogással összesen 9 × 10 = 90 kézfogást produkál. De ez minden kézfogást kétszer számol – minden rázó szemszögéből egyszer –, így a kézfogások tényleges száma $latex frac{90}{2} = 45 $. Egy egyszerű és kedves érv a győzelem mellett!

Van egy teljesen más módszer is a probléma megoldására. Képzeld el, hogy a vendégek egyenként érkeznek, és amikor odaérnek, kezet fognak minden jelenlévővel. Az első embernek nincs keze, amit meg kell fognia, így egy egyszemélyes buliban nulla a kézfogás. Most megérkezik a második személy, és kezet fog az elsővel. Ez egy kézfogást ad a végösszeghez, tehát egy kétszemélyes partiban összesen 0 + 1 = 1 kézfogás van. Amikor a harmadik személy megérkezik, és kezet fog az első két vendéggel, ez két kézfogást ad a végösszeghez. A negyedik személy érkezése három kézfogást ad a végösszeghez, és így tovább.

Ez a stratégia rekurzívan modellezi a kézfogások sorozatát, ami azt jelenti, hogy a sorozat minden egyes kifejezése az előtte lévőkhöz képest van definiálva. Valószínűleg ismeri a Fibonacci sorozatot, a leghíresebb rekurzív sorozatot. 1, 1, 2, 3, 5, 8, 13, 21-gyel kezdődik, és minden következő taggal folytatódik, amely megegyezik az előző kettő összegével.

Amint alább látni fogjuk, a rekurzió rugalmas és hatékony keretrendszer a matematikai ötletek széles skálájáról. És annak ellenére, hogy az ókori indiai tudósok, mint például Hemachandra, már 1150-re visszamenőleg ismerték az ilyen típusú sorozatokat, ma is érdekes kihívásokat kínálnak a matematikusok számára.

Lássuk, hogyan segít a rekurzív gondolkodás a kézfogási probléma megoldásában. Ha hagyjuk, hogy $latex a_n$ egyenlő legyen a kézfogások számával an n-személy fél, ezt a rekurzív kapcsolatot a következő képlettel ábrázolhatjuk:

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

Ez azt mutatja, hogy a kézfogások száma egy n-person party ($latex a_n$) egyenlő a kézfogások számával egy (n − 1) fős buli ($latex a_{n-1}$) plusz n − Még 1 kézfogás, megragadva azt a gondolatot, hogy amikor új ember érkezik, a már megtörténtekhez hozzáad egy bizonyos számú új kézfogást.

A kézfogási probléma sajátos verziójában szeretnénk tudni $latex a_{10}$, a kézfogások számát egy 10 fős partin, így a rekurzív összefüggést használjuk.

$latex a_{10} = a_9 + 9$

A $latex a_{10}$ értékének meghatározásához csak tudnunk kell $latex a_9$ értékét, és hozzá kell adnunk 9-et. Hogyan találjuk meg a $latex a_9$ értékét? Természetesen rekurzió használatával!

$latex a_9 = a_8 + 8$

Most, hogy megtaláljuk az $latex a_8$ értékét, meg kell találnunk az $latex a_7$ értékét, amihez ismerni kell az $latex a_6$ és így tovább. Ezen a ponton aggódhat, hogy ez egyfajta végtelen ereszkedésben örökké folytatódik, de ha elérjük a $latex a_1$-t, akkor készen vagyunk, mert tudjuk, hogy egy egyszemélyes bulin nulla a kézfogás.

$latex a_1 = 0$

Ez a kezdeti vagy „mag” érték a rekurzív sorozat kulcsfontosságú jellemzője. Garantálja, hogy ez a visszalépési folyamat a sorozaton a rekurzív kapcsolat használatával véget ér. Miután elérte a kezdőértéket, a visszalépés leáll, és továbbhaladhat a listán, hogy elérje a kívánt értéket.

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

A listát feldolgozva azt látjuk, hogy egy 45 fős partin összesen 10 kézfogás történik, ami megegyezik a kezdeti számításunkkal. Ha olyan, mint a tanítványaim, felteheti a kérdést, hogy miért van szükségünk más megoldásra a probléma megoldására, amikor már tudjuk a választ, különösen azért, mert ez a második megközelítés tovább tart.

Jó kérdés. Az egyik válasz az, hogy a rekurzív megközelítés teljesen más képet ad arról, hogy mi történik ebben a problémában, és a különböző szempontok hasznosak a matematikában, mint mindenben. Különböző lehetőségeket adnak a fogalmak megértésére, és lehetővé teszik különböző eszközök használatát, amelyek segíthetnek, ha elakadunk.

A rekurzió különösen hasznos, mert a matematikában mindenhol megtalálható. Felmerül például azokban a lineáris összefüggésekben, amelyekről mindenki a matematika órán tanul – amelyeket állandó változási sebesség jellemez, és amelyeket a síkban lévő vonalak ábrázolnak. Az olyan lineáris függvény, mint a $latex f(x) = 3x + 5$, rekurzív képletnek tekinthető:

$latex a_0 = 5$

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

Bár a $latex f(2)$-ról a legnyilvánvalóbb az lehet, hogy $latex f(2) = 3-szor 2 + 5 = 11$, egy másik módszer az, hogy $latex a_2 = a_1 + 3 = a_0 + 3 + 3 = 11 dollár. A lineáris függvények alapvető jellemzőjének – az állandó változási sebességnek – rekurzív modellezése újabb módot ad ennek a kapcsolatnak a gondolkodására. Ugyanez megtehető az állandó multiplikatív változással jellemezhető exponenciális függvényekkel.

A rekurzív gondolkodás a számsorozatokon túl is működik. Ha valaha is megoldott egy egyenletrendszert, akkor valószínűleg rekurzív megközelítést alkalmazott. A rendszer megoldására

$latex 2x + y = 10 $

$latex 3x – y = 5$

először összeadhatja a két egyenletet, hogy kiküszöbölje a y változó, ami a $latex 5x = 15$ egyenletet eredményezi. Oldja meg, hogy $latex x = $ 3, helyettesítse a $latex y = 4 $ értékét, és kész. Ez a megközelítés rekurzív algoritmust használ, ahol a rendszer megoldása a megoldásból kisebb, kapcsolódó rendszerekre épül. Például egy 3 × 3-as rendszer megoldásához ki kell hagynia egy változót, hogy 2 × 2-es rendszerré alakítsa, majd ismét 1 × 1-es rendszerré. Ez a könnyen megoldható egyetlen egyenlet olyan, mint ennek a rekurzív folyamatnak a kezdőértéke. Ez jelzi a visszalépés végét, és onnantól visszafelé haladsz az egyenletláncban, akárcsak egy rekurzív sorozatban.

Vannak még rekurzív bizonyítási technikák is. Például a geometriában egy híres képlet a sokszög szögösszeg képlete, amely azt mondja, hogy a belső szögek mértékeinek összege n-oldalas sokszög $latex (n-2) szor 180^{circ}$. Ennek az eredménynek az igazolásának egyik módja az, hogy egy-el kezdjük n-képzeld el, mi történne, ha eltávolítanál egy háromszöget.

A háromszög eltávolítása elfordítja a n-bemegy egy (n − 1)-gon, és eltávolítja a 180 fokos belső szögmérést is. Ez egy rekurzív összefüggés: A belső szög összege an n-gon 180 fokkal nagyobb, mint a belső szög összege egy (n − 1)-gon. Az általános eredmény megállapításához távolítsa el a háromszögeket, amíg el nem éri a magértéket, ami ebben a helyzetben akkor történik, ha három kivételével az összeset eltávolította. n-gon csúcsai. Ezen a ponton a kezdeti sokszöget háromszöggé redukáltuk, amelynek belső szögösszege 180 fok. Most haladjon felfelé, és minden lépésnél adjon hozzá 180 fokot, és megkapja a képletet.

Visszatérve a mi pártunkra, maga a kézfogás-probléma megmutatja, hogy mi lehetséges, ha kreatívan gondolkodunk, majd összekapcsoljuk a probléma több különböző perspektíváját. Ha a kézfogásunk sorozatának rekurzív modelljével játszunk:

$latex a_1 = 0$

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

szép minta rajzolódik ki:

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

Most egy új és általános módszerünk van a problémára: A kézfogások száma egy n-személy párt egyenlő az első összegével n − 1 pozitív egész szám.

Gondoljon vissza eredeti megközelítésünkre. Egy n-személyes buli, mindegyik ember kezet fog a másikkal n − 1 fő. A $latex n (n-1)$ szorzat kétszer számol minden kézfogást, így a kézfogások teljes száma $latex frac{n(n-1)}{2}$. De mivel a különböző módszereink ugyanazt számítják, ugyanazt az eredményt kell hozniuk. Ez különösen azt jelenti:

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

A kézfogási probléma különböző megközelítéseit összekapcsolva egy zárt képletet kapunk az első összegére n − 1 pozitív egész szám. De még ennél is többet kapunk: a $latex frac{n(n-1)}{2}$ kifejezés egy törtet foglal magában, de mivel egyenlő egész számok összegével, ennek is egész számnak kell lennie. Ez bizonyítja a számelmélet egyszerű tényét: Minden egész számra n, $latex frac{n(n-1)}{2}$ egy egész szám.

Ez a fajta érvelés továbbra is hatalmat ad a modern matematikában. Példaként a kutatók a 2000-es évek elején meglepő eredményeket hozott Somos-szekvenciákként ismert rekurzív sorozatokról, megmutatva, hogy azok is számítanak valamit. A kreatív kapcsolatok erején keresztül a matematikusok ismét felfedezték, hová juthatnak, ha megértik, hol jártak.

Ünnepély

1. Keressen egy zárt képletet a rekurzív módon definiált sorozathoz
$latex a_1 = 1$
$latex a_n = a_{n-1} + 2n – 1$

2. Az oszlop végén a $latex frac{n(n-1)}{2}$ kifejezés egész számot mutatott, még akkor is, ha a kifejezés törtet tartalmaz, mert $latex frac{n(n-1 )}{2}$ valami megszámlálás eredménye. Van egy számelméleti érv is, amely azt mutatja, hogy ennek a kifejezésnek egész számnak kell lennie. Mi az?

3. Keresse meg a rekurzív sorozat első néhány tagját
$latex a_1 = 1$
$latex a_n = frac{1}{1+a_{n-1}}$

4. Keresse meg a rekurzív sorozat első néhány tagját
$latex a_1 = 1$
$latex a_2 = 1$
$latex a_n = a_{n-1} – a_{n-2}$