Matematika yang Menghubungkan Kemana Kita Pergi ke Tempat yang Pernah Kita Kunjungi | Majalah Kuanta

Katakanlah Anda berada di sebuah pesta dengan sembilan orang lainnya dan semua orang berjabat tangan dengan orang lain tepat satu kali. Berapa banyak jabat tangan yang terjadi?

Ini adalah “masalah jabat tangan”, dan ini adalah salah satu favorit saya. Sebagai seorang guru matematika, saya menyukainya karena ada begitu banyak cara untuk mencapai solusi, dan keragaman serta keterhubungan strategi-strategi tersebut dengan indah menggambarkan kekuatan berpikir kreatif dalam matematika.

Salah satu solusinya seperti ini: Mulailah dengan setiap orang menjabat tangan orang lain. Sepuluh orang, dengan masing-masing sembilan jabat tangan, menghasilkan 9 × 10 = 90 total jabat tangan. Namun ini menghitung setiap jabat tangan dua kali — satu kali dari sudut pandang masing-masing pengocok — jadi jumlah jabat tangan sebenarnya adalah $latex frac{90}{2} = 45$. Argumen penghitungan yang sederhana dan indah untuk kemenangan!

Ada juga cara yang sangat berbeda untuk menyelesaikan masalah. Bayangkan para tamu datang satu per satu, dan sesampainya di sana, mereka berjabat tangan dengan semua yang hadir. Orang pertama tidak mempunyai tangan untuk berjabat tangan, jadi dalam pesta satu orang tidak ada jabat tangan total. Kini orang kedua datang dan berjabat tangan dengan orang pertama. Ini menambahkan satu jabat tangan ke total, jadi dalam pesta dua orang, ada total 0 + 1 = 1 jabat tangan. Ketika orang ketiga datang dan berjabat tangan dengan dua tamu pertama, jumlah totalnya adalah dua jabat tangan. Kedatangan orang keempat menambah total jabat tangan sebanyak tiga kali, dan seterusnya.

Strategi ini memodelkan rangkaian jabat tangan secara rekursif, yang berarti setiap istilah dalam rangkaian tersebut didefinisikan relatif terhadap istilah yang ada sebelumnya. Anda mungkin akrab dengan deret Fibonacci, deret rekursif yang paling terkenal. Suku tersebut dimulai dengan 1, 1, 2, 3, 5, 8, 13, 21, dan berlanjut dengan setiap suku berikutnya sama dengan jumlah dua suku sebelumnya.

Seperti yang akan kita lihat di bawah, rekursi adalah kerangka kerja yang fleksibel dan kuat untuk memikirkan berbagai ide matematika. Dan meskipun para sarjana India kuno seperti Hemachandra dianggap mengetahui tentang barisan semacam ini sejak tahun 1150, mereka masih menawarkan tantangan menarik bagi para matematikawan saat ini.

Mari kita lihat bagaimana berpikir secara rekursif membantu mengatasi masalah jabat tangan. Jika kita membiarkan $lateks a_n$ sama dengan jumlah jabat tangan pada sebuah n-pihak pihak, kita dapat merepresentasikan hubungan rekursif ini dengan rumus berikut:

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

Ini memberitahu kita bahwa jumlah jabat tangan pada suatu n-orang pihak ($lateks a_n$) sama dengan jumlah jabat tangan di (n − 1)-pesta orang ($lateks a_{n-1}$) plus n − 1 jabat tangan lagi, menangkap gagasan bahwa ketika ada orang baru yang datang, mereka menambahkan sejumlah jabat tangan baru ke jabat tangan yang sudah dilakukan.

Dalam masalah jabat tangan versi khusus kami, kami ingin mengetahui $latex a_{10}$, jumlah jabat tangan pada pesta yang terdiri dari 10 orang, sehingga untuk mengetahui bahwa kami menggunakan hubungan rekursif

$lateks a_{10} = a_9 + 9$

Untuk mencari nilai $latex a_{10}$, kita hanya perlu mengetahui nilai $latex a_9$ dan menambahkan 9 ke dalamnya. Bagaimana cara mencari nilai $lateks a_9$? Tentu saja dengan menggunakan rekursi!

$lateks a_9 = a_8 + 8$

Sekarang, untuk mencari nilai $latex a_8$, kita perlu mencari nilai $latex a_7$, yang perlu diketahui $latex a_6$, dan seterusnya. Pada titik ini, Anda mungkin khawatir bahwa ini akan berlangsung selamanya dalam bentuk penurunan tanpa batas, namun begitu kita mencapai $latex a_1$ kita selesai, karena kita tahu bahwa tidak ada total jabat tangan di pesta satu orang.

$lateks a_1 = 0$

Nilai awal atau “seed” ini adalah fitur kunci dari rangkaian rekursif. Ini menjamin bahwa proses penelusuran balik melalui urutan menggunakan hubungan rekursif akan berakhir. Setelah Anda mencapai nilai awal, kemunduran akan berhenti, dan Anda kemudian dapat meneruskan daftar untuk mendapatkan nilai yang Anda inginkan.

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

$cdot lateks$

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

Dengan menelusuri daftar tersebut, kami melihat bahwa ada total 45 jabat tangan di pesta yang terdiri dari 10 orang, yang sesuai dengan perhitungan awal kami. Jika Anda seperti murid-murid saya, Anda mungkin bertanya mengapa kita memerlukan cara lain untuk memecahkan masalah ini ketika kita sudah mengetahui jawabannya, terutama karena pendekatan kedua ini tampaknya memakan waktu lebih lama.

Itu pertanyaan yang bagus. Salah satu jawabannya adalah bahwa pendekatan rekursif memberi kita pandangan yang sama sekali berbeda tentang apa yang terjadi dalam soal ini, dan perspektif yang berbeda berguna dalam matematika, sebagaimana halnya dalam segala hal. Mereka memberi kita peluang berbeda untuk memahami konsep dan memungkinkan kita menggunakan alat berbeda, yang dapat membantu saat kita mengalami kebuntuan.

Secara khusus, rekursi berguna karena ada dimana-mana dalam matematika. Misalnya, hal ini muncul dalam hubungan linier yang dipelajari setiap orang di kelas matematika — hubungan yang ditandai dengan laju perubahan yang konstan dan diwakili oleh garis pada bidang. Fungsi linier seperti $latex f(x) = 3x + 5$ dapat dianggap sebagai rumus rekursif:

$lateks a_0 = 5$

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

Meskipun cara yang lebih jelas untuk memikirkan $latex f(2)$ mungkin adalah $latex f(2) = 3 dikali 2 + 5 = 11$, cara lainnya adalah $latex a_2 = a_1 + 3 = a_0 + 3 + 3 = $11. Memodelkan karakteristik dasar fungsi linier secara rekursif — laju perubahan yang konstan — memberi kita cara lain untuk memikirkan hubungan ini. Hal yang sama dapat dilakukan dengan fungsi eksponensial yang bercirikan perubahan perkalian konstan.

Pemikiran rekursif juga bekerja di luar rangkaian angka. Jika Anda pernah memecahkan sistem persamaan, Anda mungkin menerapkan pendekatan rekursif. Untuk memecahkan sistem

$lateks 2x + y = 10$

$lateks 3x – y = 5$

Anda dapat menjumlahkan kedua persamaan terlebih dahulu untuk menghilangkannya y variabel, yang menghasilkan persamaan $lateks 5x = 15$. Selesaikan ini untuk mendapatkan $latex x =$ 3, gantikan dengan mencari $latex y = 4$, dan selesai. Pendekatan ini menggunakan algoritma rekursif, dimana solusi suatu sistem dibangun dari solusi ke sistem yang lebih kecil dan terkait. Misalnya, untuk menyelesaikan sistem 3 × 3, Anda menghilangkan satu variabel untuk mengubahnya menjadi sistem 2 × 2, lalu mengubahnya lagi menjadi sistem 1 × 1. Persamaan tunggal yang mudah diselesaikan ini seperti nilai awal dari proses rekursif ini. Ini menandakan akhir dari kemunduran, dan dari sana Anda kembali ke rantai persamaan, seperti dalam barisan rekursif.

Bahkan ada teknik pembuktian rekursif. Misalnya, rumus geometri yang terkenal adalah rumus jumlah sudut poligon, yang menyatakan bahwa jumlah besar sudut dalam suatu npoligon bersisi adalah $lateks (n-2) dikalikan 180^{circ}$. Salah satu cara untuk membuktikan hasil ini adalah dengan memulai dengan n-gon dan bayangkan apa yang akan terjadi jika Anda menghilangkan sebuah segitiga.

Menghapus segitiga akan mengubah n-gon menjadi (n − 1)-gon, dan juga menghilangkan ukuran sudut dalam sebesar 180 derajat. Ini adalah hubungan rekursif: Jumlah sudut dalam untuk an n-gon lebih besar 180 derajat dari jumlah sudut dalam untuk (n − 1)-gon. Untuk menentukan hasil umum, terus hilangkan segitiga hingga Anda mencapai nilai benih, yang dalam situasi ini terjadi jika Anda telah menghilangkan semua kecuali tiga dari nilai benih. nsimpul -gon. Pada titik ini poligon awal telah direduksi menjadi sebuah segitiga, yang jumlah sudut dalamnya diketahui 180 derajat. Sekarang lanjutkan kembali, tambahkan 180 derajat pada setiap langkah, dan Anda akan mendapatkan rumusnya.

Kembali ke pesta kita, masalah jabat tangan itu sendiri menunjukkan kepada kita apa yang mungkin terjadi ketika kita berpikir kreatif dan kemudian menghubungkan berbagai perspektif berbeda dari suatu masalah bersama-sama. Jika kita bermain-main dengan model rekursif untuk rangkaian jabat tangan kita:

$lateks a_1 = 0$

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

pola yang bagus muncul:

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

$cdot lateks$

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

Kini kita mempunyai cara baru dan umum untuk memikirkan masalah ini: Jumlah jabat tangan dalam sebuah n-pihak orang sama dengan jumlah pihak pertama n − 1 bilangan bulat positif.

Pikirkan kembali pendekatan awal kami. Dalam sebuah n-orang pihak, masing-masing orang akan berjabat tangan dengan yang lain n − 1 orang. Produk $latex n (n-1)$ menghitung setiap jabat tangan sebanyak dua kali, sehingga jumlah total jabat tangan adalah $latex frac{n(n-1)}{2}$. Namun karena metode kami yang berbeda menghitung hal yang sama, maka hasilnya harus sama. Secara khusus, ini berarti:

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

Dengan menghubungkan pendekatan yang berbeda pada masalah jabat tangan, kita mendapatkan rumus tertutup untuk jumlah yang pertama n − 1 bilangan bulat positif. Namun kita mendapatkan lebih banyak lagi: ekspresi $latex frac{n(n-1)}{2}$ melibatkan pecahan, namun karena sama dengan jumlah bilangan bulat, maka harus berupa bilangan bulat juga. Ini membuktikan fakta sederhana teori bilangan: Untuk setiap bilangan bulat n, $latex frac{n(n-1)}{2}$ adalah bilangan bulat.

Argumen serupa terus memperkuat matematika modern. Sebagai salah satu contohnya, para peneliti di awal tahun 2000an membuktikan beberapa hasil yang mengejutkan tentang barisan rekursif yang dikenal sebagai barisan Somos dengan menunjukkan bahwa mereka juga menghitung sesuatu. Melalui kekuatan koneksi kreatif, para ahli matematika sekali lagi menemukan apa yang bisa mereka capai dengan memahami di mana mereka berada.

Latihan

1. Temukan rumus tertutup untuk barisan yang didefinisikan secara rekursif sebagai
$lateks a_1 = 1$
$lateks a_n = a_{n-1} + 2n – 1$

2. Di akhir kolom, ekspresi $latex frac{n(n-1)}{2}$ ditampilkan sebagai bilangan bulat meskipun ekspresi tersebut melibatkan pecahan, karena $latex frac{n(n-1 )}{2}$ adalah hasil penghitungan sesuatu. Ada juga argumen teori bilangan yang menunjukkan ekspresi ini harus berupa bilangan bulat. Apa itu?

3. Temukan beberapa suku pertama barisan rekursif
$lateks a_1 = 1$
$lateks a_n = frac{1}{1+a_{n-1}}$

4. Temukan beberapa suku pertama barisan rekursif
$lateks a_1 = 1$
$lateks a_2 = 1$
$lateks a_n = a_{n-1} – a_{n-2}$