Setiap hari persediaan biji kopi espresso ajaib berlapis cokelat Anda menjadi dua kali lipat (setiap biji membelah menjadi dua), tetapi kemudian Anda memakan 5 biji. Pada awal hari ke-0 Anda memiliki 10 biji.
Tuliskan beberapa suku pertama barisan tersebut. Kemudian berikan definisi rekursif untuk barisan itu dan jelaskan bagaimana Anda mengetahui bahwa definisi tersebut benar.
Dalam bab ini, kita mempelajari barisan dan induksi matematika. Pada awalnya, keduanya mungkin tampak tidak sepenuhnya berkaitan, tetapi terdapat satu penghubung: penalaran rekursif. Ketika terdapat banyak kasus (bahkan mungkin tak berhingga), sering kali lebih mudah menjelaskan suatu kasus tertentu dengan menyatakan hubungannya dengan kasus-kasus lain daripada menjelaskannya dari awal. Untuk barisan, kita dapat menjelaskan suku ke-\(n\) dengan menyatakan hubungannya dengan suku sebelumnya. Ketika menunjukkan bahwa suatu pernyataan yang melibatkan peubah \(n\) benar untuk setiap nilai \(n\text{,}\) kita dapat menjelaskan mengapa kasus \(n = k\) benar berdasarkan alasan mengapa kasus \(n = k-1\) benar.
Meskipun memikirkan masalah secara rekursif sering kali lebih mudah daripada memikirkannya secara langsung (setidaknya setelah Anda terbiasa dengan cara berpikir ini), tujuan akhir kita adalah melampaui deskripsi rekursif tersebut. Untuk barisan, kita ingin menemukan rumus tertutup bagi suku ke-\(n\text{.}\) Untuk pembuktian, kita ingin mengetahui bahwa pernyataan itu benar untuk suatu \(n\) tertentu (bukan hanya dengan mengasumsikan bahwa pernyataan tersebut benar untuk nilai \(n\) sebelumnya). Dalam bab ini, kita melihat beberapa metode untuk beralih dari deskripsi rekursif ke deskripsi langsung.
Jika suku-suku suatu barisan bertambah dengan beda tetap atau rasio tetap (keduanya merupakan deskripsi rekursif), maka barisan dengan beda tetap merupakan barisan aritmetika, sedangkan barisan dengan rasio tetap merupakan barisan geometri, dan kita memiliki rumus tertutup untuk keduanya berdasarkan suku awal serta beda atau rasio tetapnya.
Jika suku-suku suatu barisan bertambah dengan laju polinomial (yaitu, jika beda antarsukunya membentuk barisan dengan rumus tertutup polinomial), maka barisan tersebut diberikan oleh suatu rumus tertutup polinomial (dengan derajat satu lebih tinggi daripada derajat rumus untuk barisan bedanya).
Jika suku-suku suatu barisan bertambah dengan laju eksponensial, kita mengharapkan rumus tertutup barisan tersebut berbentuk eksponensial. Barisan-barisan ini sering memiliki rumus rekursif yang relatif sederhana, dan teknik akar karakteristik memungkinkan kita menemukan rumus tertutupnya.
Jika kita ingin membuktikan bahwa suatu pernyataan benar untuk setiap nilai \(n\) (mulai dari suatu nilai awal yang kecil), dan kita dapat menjelaskan mengapa pernyataan untuk \(n = k\) mengakibatkan pernyataan untuk \(n = k+1\text{,}\) maka prinsip induksi matematika menjamin bahwa pernyataan tersebut benar untuk setiap nilai \(n\) (mulai dari kasus dasarnya).
Sepanjang bab ini, kita berusaha memahami mengapa fakta-fakta di atas benar. Sebagian dari tujuan pembuktian, baik dengan induksi maupun tidak, adalah mencapai pemahaman tersebut: pembuktian menjelaskan mengapa kebenaran matematika memang benar. Ketika mengembangkan kemampuan bernalar tentang matematika, kita perlu memastikan bahwa metode penalaran kita sahih. Cabang matematika yang menentukan apakah suatu penalaran sahih atau tidak adalah logika matematika, yang telah dibahas dalam bab Logika.
Temukan rumus tertutup untuk \(a_n\text{,}\) suku ke-\(n\) barisan tersebut, dengan menuliskan setiap suku sebagai jumlah suatu barisan. Petunjuk: tentukan dahulu \(a_0\text{,}\) tetapi abaikan suku itu ketika menyederhanakan jumlahnya.
Temukan kembali suatu rumus tertutup, kali ini dengan menggunakan pencocokan polinomial atau teknik akar karakteristik (pilih yang sesuai). Tunjukkan langkah-langkah Anda.
Temukan sekali lagi suatu rumus tertutup, kali ini dengan mengenali barisan tersebut sebagai modifikasi dari satu atau beberapa barisan yang terkenal. Jelaskan.
Dalam lagu The Twelve Days of Christmas, kekasih saya mula-mula memberi saya 1 hadiah; kemudian 2 hadiah dan 1 hadiah; lalu 3 hadiah, 2 hadiah, dan 1 hadiah; dan seterusnya. Berapa jumlah seluruh hadiah yang diberikan kekasih saya selama dua belas hari tersebut?
Kelinci cokelat ajaib Anda berkembang biak seperti kelinci: setiap kelinci besar menghasilkan 2 kelinci mini baru setiap hari, dan setiap hari, semua kelinci mini yang lahir pada hari sebelumnya tumbuh menjadi kelinci besar. Anggap Anda mulai dengan 2 kelinci mini dan tidak ada kelinci yang pernah mati (atau dimakan).
Perhatikan barisan jumlah parsial kuadrat bilangan Fibonacci: \(F_1^2\text{,}\)\(F_1^2 + F_2^2\text{,}\)\(F_1^2 + F_2^2 + F_3^2, \ldots\text{.}\) Barisan tersebut diawali oleh \(1, 2, 6, 15, 40,\ldots\text{.}\)
Tebak suatu rumus untuk jumlah parsial ke-\(n\) yang dinyatakan menggunakan bilangan Fibonacci. Petunjuk: tuliskan setiap suku sebagai hasil kali.
Sebuah persegi panjang dibagi menjadi persegi di sebelah kiri dan persegi panjang sebangun di sebelah kanan. Persegi panjang sebangun itu dibagi menjadi persegi di bawah dan persegi panjang sebangun di atas. Persegi panjang bagian atas kemudian dibagi menjadi persegi di kanan dan persegi panjang di kiri. Persegi panjang di kiri dibagi menjadi persegi di atas dan persegi panjang di bawah. Persegi panjang paling bawah dibagi menjadi dua persegi yang sama besar.
Satu perangko 9 sen bernilai 1 sen lebih besar daripada dua perangko 4 sen, dan tujuh perangko 4 sen bernilai 1 sen lebih besar daripada tiga perangko 9 sen.
Pastikan Anda benar-benar menggunakan induksi di sini. Kasus dasar: \(2^2 = 4\text{.}\) Kasus induksi: anggap \((2n)^2\) habis dibagi 4, lalu perhatikan \((2n+2)^2 = (2n)^2 + 4n + 4\text{.}\) Bilangan ini habis dibagi 4 karena \(4n +4\) jelas habis dibagi 4, sedangkan menurut hipotesis induksi kita, \((2n)^2\) juga habis dibagi 4.
Ini merupakan pembuktian induksi yang langsung. Perhatikan bahwa Anda perlu menyederhanakan \(\left(\frac{n(n+1)}{2}\right)^2 + (n+1)^3\) hingga memperoleh \(\left(\frac{(n+1)(n+2)}{2}\right)^2\text{.}\)
Misalkan \(a_0 = 1\text{,}\)\(a_1 = 1\) dan \(a_n = 3a_{n-1} - 2a_{n-2}\text{.}\) Buktikan dengan induksi kuat bahwa \(a_n = 1\) untuk setiap \(n\text{.}\)
Terdapat dua kasus dasar, yaitu \(P(0)\) dan \(P(1)\text{.}\) Kemudian, untuk kasus induksi, anggap \(P(k)\) benar untuk setiap \(k \lt n\text{.}\) Dengan demikian, Anda dapat menganggap \(a_{n-1} = 1\) dan \(a_{n-2} = 1\text{.}\) Terapkan relasi rekurensinya.
