Matematyka, która łączy dokąd zmierzamy z tym, gdzie byliśmy | Magazyn Quanta

Załóżmy, że jesteś na imprezie z dziewięcioma innymi osobami i każdy podaje każdemu rękę dokładnie raz. Ile uścisków dłoni ma miejsce?

To jest „problem uścisku dłoni” i jest jednym z moich ulubionych. Jako nauczyciel matematyki bardzo mi się to podoba, ponieważ rozwiązanie można znaleźć na wiele różnych sposobów, a różnorodność i wzajemne powiązania tych strategii pięknie ilustrują siłę twórczego myślenia w matematyce.

Jedno z rozwiązań wygląda następująco: zacznij od uściśnięcia dłoni każdej innej osoby. Dziesięć osób, każda po dziewięć uścisków dłoni, wykonuje 9 × 10 = 90 całkowitych uścisków dłoni. Ale to oznacza, że ​​każdy uścisk dłoni jest liczony dwukrotnie – raz z perspektywy każdego shakera – więc rzeczywista liczba uścisków dłoni wynosi $latex frac{90}{2} = 45 $. Prosty i piękny argument przemawiający za wygraną!

Istnieje również zupełnie inny sposób rozwiązania problemu. Wyobraź sobie, że goście przychodzą pojedynczo, a kiedy już tam dotrą, podają dłonie wszystkim obecnym. Pierwsza osoba nie ma rąk do uścisku, więc w grupie jednoosobowej nie ma całkowitej liczby uścisków dłoni. Teraz podchodzi druga osoba i podaje rękę pierwszej osobie. To dodaje jeden uścisk dłoni do całkowitej liczby uścisków dłoni, więc w grupie dwuosobowej jest 0 + 1 = 1 całkowitych uścisków dłoni. Kiedy trzecia osoba podchodzi i podaje rękę dwóm pierwszym gościom, dodaje to do sumy dwa uściski dłoni. Przybycie czwartej osoby dodaje do sumy trzy uściski dłoni i tak dalej.

Strategia ta modeluje sekwencję uścisków dłoni w sposób rekurencyjny, co oznacza, że ​​każdy termin w sekwencji jest definiowany w odniesieniu do terminów poprzedzających go. Prawdopodobnie znasz ciąg Fibonacciego, najsłynniejszą sekwencję rekurencyjną ze wszystkich. Zaczyna się od 1, 1, 2, 3, 5, 8, 13, 21 i trwa dalej, a każdy kolejny wyraz jest równy sumie dwóch poprzednich.

Jak zobaczymy poniżej, rekurencja jest elastyczną i potężną strukturą myślenia o szerokim zakresie idei matematycznych. I chociaż starożytnym indyjskim uczonym, takim jak Hemachandra, przypisuje się wiedzę o tego rodzaju ciągach już w roku 1150, nadal stanowią one intrygujące wyzwania dla współczesnych matematyków.

Zobaczmy, jak myślenie rekurencyjne pomaga w rozwiązaniu problemu uścisku dłoni. Jeśli pozwolimy, aby $latex a_n$ było równe liczbie uścisków dłoni przy an n-person, możemy przedstawić tę rekurencyjną relację za pomocą następującego wzoru:

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

To mówi nam, że liczba uścisków dłoni w n-person party ($latex a_n$) jest równa liczbie uścisków dłoni przy (n − 1)-osobowa impreza ($latex a_{n-1}$) plus n − Jeszcze 1 uścisk dłoni, co odzwierciedla ideę, że kiedy pojawia się nowa osoba, dodaje ona pewną liczbę nowych uścisków dłoni do tych, które już miały miejsce.

W naszej szczególnej wersji problemu uścisku dłoni chcemy poznać $latex a_{10}$, liczbę uścisków dłoni na 10-osobowej imprezie, aby stwierdzić, że użyjemy relacji rekurencyjnej

$lateks a_{10} = a_9 + 9$

Aby znaleźć wartość $latex a_{10}$, wystarczy znać wartość $latex a_9$ i dodać do niej 9. Jak znaleźć wartość $latex a_9$? Oczywiście używając rekurencji!

$lateks a_9 = a_8 + 8$

Teraz, aby znaleźć wartość $latex a_8$, musimy znaleźć wartość $latex a_7$, co wymaga znajomości $latex a_6$ i tak dalej. W tym momencie możesz się martwić, że będzie to trwało wiecznie w swego rodzaju nieskończonym zejściu, ale kiedy osiągniemy $latex a_1$, to już koniec, ponieważ wiemy, że na jednoosobowej imprezie nie ma całkowitej liczby uścisków dłoni.

$lateks a_1 = 0 $

Ta wartość początkowa lub „zalążkowa” jest kluczową cechą sekwencji rekurencyjnej. Gwarantuje to, że proces cofania się po sekwencji przy użyciu relacji rekurencyjnej zakończy się. Gdy trafisz na wartość początkową, cofanie się zatrzyma i możesz dalej przeglądać listę, aby uzyskać żądaną wartość.

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

$lateksowe CDots$

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

Przeglądając listę, widzimy, że na 45-osobowym przyjęciu przypada łącznie 10 uścisków dłoni, co zgadza się z naszymi wstępnymi obliczeniami. Jeśli jesteś choć trochę podobny do moich uczniów, możesz zapytać, dlaczego potrzebujemy innego sposobu rozwiązania tego problemu, skoro znamy już odpowiedź, zwłaszcza że to drugie podejście wydaje się trwać dłużej.

To dobre pytanie. Jedna z odpowiedzi jest taka, że ​​podejście rekurencyjne daje nam zupełnie inny pogląd na to, co dzieje się w tym problemie, a różne perspektywy są przydatne w matematyce, tak jak we wszystkim. Dają nam różne możliwości zrozumienia koncepcji i pozwalają nam korzystać z różnych narzędzi, które mogą pomóc, gdy utkniemy.

W szczególności rekurencja jest przydatna, ponieważ występuje wszędzie w matematyce. Powstaje na przykład w zależnościach liniowych, o których uczy się każdy na lekcjach matematyki — tych charakteryzujących się stałą szybkością zmian i reprezentowanych przez linie na płaszczyźnie. Funkcję liniową, taką jak $latex f(x) = 3x + 5$, można traktować jako formułę rekurencyjną:

$lateks a_0 = 5 $

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

Chociaż bardziej oczywistym sposobem myślenia o $lateksie f(2)$ może być to, że $lateks f(2) = 3 razy 2 + 5 = 11$, innym sposobem jest to, że $lateks a_2 = a_1 + 3 = a_0 + 3 + 3 = 11 dolarów. Rekurencyjne modelowanie podstawowej cechy funkcji liniowych — stałej szybkości zmian — daje nam inny sposób myślenia o tej zależności. To samo można zrobić z funkcjami wykładniczymi charakteryzującymi się ciągłą zmianą multiplikatywną.

Myślenie rekurencyjne działa również poza ciągami liczb. Jeśli kiedykolwiek rozwiązałeś układ równań, prawdopodobnie zastosowałeś podejście rekurencyjne. Aby rozwiązać system

$lateks 2x + y = 10 $

$lateks 3x – y = 5$

możesz najpierw dodać do siebie oba równania, aby wyeliminować y zmienna, co daje równanie $lateks 5x = 15$. Rozwiąż to, aby otrzymać $lateks x = 3 USD, zamień, aby znaleźć $lateks y = 4 $ i gotowe. Podejście to wykorzystuje algorytm rekurencyjny, w którym rozwiązanie systemu jest budowane z rozwiązania na mniejsze, powiązane systemy. Na przykład, aby rozwiązać system 3 × 3, eliminujesz jedną zmienną, aby przekształcić ją w system 2 × 2, a następnie ponownie, aby przekształcić ją w system 1 × 1. To łatwe do rozwiązania pojedyncze równanie jest niczym wartość zalążkowa tego procesu rekurencyjnego. Sygnalizuje koniec wycofywania się i od tego momentu możesz wrócić w górę łańcucha równań, tak jak w sekwencji rekurencyjnej.

Istnieją nawet techniki dowodu rekurencyjnego. Na przykład znanym wzorem w geometrii jest wzór na sumę kątów wielokątnych, który mówi, że suma miar kątów wewnętrznych nwielokąt dwustronny to $lateks (n-2) razy 180^{circ}$. Jednym ze sposobów udowodnienia tego wyniku jest rozpoczęcie od n-i wyobraź sobie, co by się stało, gdyby usunąć trójkąt.

Usunięcie trójkąta powoduje zmianę n-wchodzę do (n − 1)-gon, a także usuwa miarę kąta wewnętrznego o 180 stopni. To jest relacja rekurencyjna: Suma kątów wewnętrznych dla an n-gon jest o 180 stopni większy niż suma kątów wewnętrznych dla (n − 1)-gon. Aby ustalić ogólny wynik, usuwaj trójkąty, aż osiągniesz wartość początkową, co w tej sytuacji ma miejsce, gdy usuniesz wszystkie oprócz trzech n-gona wierzchołki. W tym momencie początkowy wielokąt został zredukowany do trójkąta, którego suma kątów wewnętrznych wynosi 180 stopni. Teraz wróć do góry, dodając 180 stopni na każdym kroku, a otrzymasz formułę.

Wracając do naszej partii, sam problem uścisku dłoni pokazuje nam, co jest możliwe, gdy myślimy kreatywnie, a następnie łączymy w jedną całość wiele różnych perspektyw problemu. Jeśli pobawimy się modelem rekurencyjnym naszej sekwencji uścisków dłoni:

$lateks a_1 = 0 $

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

wyłania się ładny wzór:

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

$lateksowe CDots$

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

Mamy teraz nowy, ogólny sposób myślenia o problemie: liczba uścisków dłoni w trakcie rozmowy n-osobowa partia jest równa sumie pierwszej n − 1 dodatnia liczba całkowita.

Przypomnij sobie nasze pierwotne podejście. w n-osobowa impreza, każda osoba poda sobie rękę z drugą n − 1 osoba. Iloczyn $latex n (n-1)$ liczy każdy uścisk dłoni dwukrotnie, więc całkowita liczba uścisków dłoni wynosi $latex frac{n(n-1)}{2}$. Ponieważ jednak nasze różne metody liczą to samo, muszą dawać ten sam wynik. W szczególności oznacza to:

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

Łącząc różne podejścia do problemu uścisku dłoni, otrzymujemy zamknięty wzór na sumę pierwszego n − 1 dodatnia liczba całkowita. Ale dostajemy jeszcze więcej: wyrażenie $latex frac{n(n-1)}{2}$ dotyczy ułamka, ale ponieważ jest równe sumie liczb całkowitych, również musi być liczbą całkowitą. To dowodzi prostego faktu teorii liczb: dla każdej liczby całkowitej n, $lateks frac{n(n-1)}{2}$ jest liczbą całkowitą.

Ten sam rodzaj argumentacji w dalszym ciągu napędza współczesną matematykę. Na przykład badacze na początku XXI w przyniosły zaskakujące rezultaty o sekwencjach rekurencyjnych znanych jako sekwencje Somosa, pokazując, że one również coś liczą. Dzięki mocy twórczych połączeń matematycy po raz kolejny odkryli, dokąd mogą dojść, wiedząc, gdzie byli.

ćwiczenia

1. Znajdź zamknięty wzór na ciąg zdefiniowany rekurencyjnie jako
$lateks a_1 = 1 $
$lateks a_n = a_{n-1} + 2n – 1$

2. Na końcu kolumny pokazano, że wyrażenie $latex frac{n(n-1)}{2}$ jest liczbą całkowitą, mimo że wyrażenie zawiera ułamek, ponieważ $latex frac{n(n-1 )}{2}$ jest wynikiem zliczenia czegoś. Istnieje również argument z teorii liczb, który pokazuje, że to wyrażenie musi być liczbą całkowitą. Co to jest?

3. Znajdź kilka pierwszych wyrazów ciągu rekurencyjnego
$lateks a_1 = 1 $
$lateks a_n = frac{1}{1+a_{n-1}}$

4. Znajdź kilka pierwszych wyrazów ciągu rekurencyjnego
$lateks a_1 = 1 $
$lateks a_2 = 1 $
$lateks a_n = a_{n-1} – a_{n-2}$