Lewati ke konten utama
Gambar logo

Matematika Diskret Sebuah Pengantar Terbuka, Edisi Keempat

Oscar Levin

Subbab 4.5 Pembuktian dengan Induksi

Subbagian Pratinjau Bagian

Selidiki!
Apa digit satuan (digit paling kanan) dari \(6^n\text{?}\) Apakah jawabannya bergantung pada \(n\text{?}\)
🔗
🔗
Induksi matematika adalah teknik pembuktian yang ampuh untuk membuktikan kebenaran suatu barisan pernyataan, asalkan barisan pernyataan tersebut memiliki titik awal. Sebagai contoh, jika kita ingin menyatakan sesuatu tentang digit satuan \(6^n\text{,}\) kita mengajukan klaim itu untuk \(n=1\text{,}\) lalu \(n = 2\text{,}\) kemudian \(n = 3\text{,}\) dan seterusnya.
🔗
Induksi berkaitan erat dengan definisi rekursif; gagasan utama pembuktian dengan induksi adalah menjelaskan cara beralih dari satu pernyataan dalam barisan ke pernyataan berikutnya.
🔗

Lembar Kerja Kegiatan Pratinjau

1.
Misalkan digit satuan \(6^{472}\) adalah 2. Artinya, misalkan \(6^{472} = 19,381,6\ldots\ldots 2\text{.}\) Berapakah digit satuan \(6^{473}\text{?}\)
🔗
Petunjuk.
\(6^{473} = 6 \cdot 6^{472}\text{.}\)
🔗
🔗
🔗
2.
Berapakah digit satuan \(6^{2}\text{,}\) \(6^3\text{,}\) dan \(6^4\text{?}\)
🔗
Digit satuan \(6^2\) adalah .
🔗
Digit satuan \(6^3\) adalah .
🔗
Digit satuan \(6^4\) adalah .
🔗
🔗
3.
Manakah di antara pernyataan berikut yang benar? Pilih semua yang berlaku.
🔗
  • Jika digit satuan \(6^k\) adalah 6, maka digit satuan \(6^{k+1}\) adalah 6.
    🔗
  • Jika digit satuan \(6^k\) adalah 2, maka digit satuan \(6^{k+1}\) adalah 2.
    🔗
  • Digit satuan \(6^{472}\) adalah 2.
    🔗
  • Digit satuan \(6^{472}\) adalah 6.
    🔗
🔗
4.
Jelaskan jawaban Anda atas pertanyaan sebelumnya.
🔗
🔗
🔗
🔗

Subbagian Penalaran Rekursif

Kita telah melihat bahwa mendeskripsikan barisan secara rekursif sering kali lebih mudah daripada mendeskripsikannya dengan rumus tertutup. Sekarang kita akan melihat bagaimana penalaran rekursif serupa dapat membantu kita membuktikan pernyataan dengan teknik yang disebut induksi matematika. Gaya pembuktian ini sangat berguna ketika berbagai kasus pernyataan tersebut (misalnya, untuk nilai \(n\) yang berbeda) saling berhubungan secara rekursif.
🔗
Sebagai contoh, misalkan kita ingin membuktikan suatu fakta tentang semua suku dalam barisan yang didefinisikan secara rekursif. Perhatikan barisan \((a_n)_{n\ge 0}\) yang didefinisikan oleh \(a_n = 3a_{n-1} - 2\) dengan \(a_0 = 5\text{.}\) Dapatkah kita membuktikan bahwa setiap suku barisan ini ganjil?
🔗
Mari kita mulai dengan menuliskan beberapa suku pertama barisan tersebut:
\begin{equation*} 5, 13, 37, 109, \ldots\text{.} \end{equation*}
Sejauh ini, semua bilangan tersebut tampak ganjil. Apakah bilangan berikutnya juga ganjil? Tentu saja, kita dapat langsung menghitungnya dengan relasi rekurensi, yaitu \(3\cdot 109 - 2\text{.}\) Kita sebenarnya tidak peduli bilangan ganjil mana yang dihasilkan; yang penting bilangan itu memang ganjil. Kita tahu hasilnya ganjil karena hasil kali dua bilangan ganjil adalah ganjil, dan mengurangkan 2 dari bilangan ganjil menghasilkan bilangan ganjil.
🔗
Bagus, jadi \(a_4\) ganjil. Apakah \(a_5\) juga ganjil? Ya, gunakan argumen yang sama: \(a_5 = 3 a_4 - 2\text{.}\) Kita baru saja meyakinkan diri bahwa \(a_4\) ganjil (tanpa mencari nilai sebenarnya), sehingga \(3 a_4\) ganjil, dan bilangan yang 2 lebih kecil darinya juga ganjil.
🔗
Bagaimana dengan \(a_6\text{?}\) Lakukan hal yang sama. Sebenarnya, mengapa kita menggunakan bilangan tertentu sebagai indeks? Jika argumennya selalu sama, kita semestinya dapat menyatakannya sekali saja dan mengatakan bahwa argumen itu selalu berlaku.
🔗
Misalkan kita telah mengetahui bahwa \(a_k\) ganjil (dengan \(k\) suatu bilangan asli sembarang). Dari sini kita dapat menyimpulkan bahwa \(a_{k+1}\) ganjil, sebab \(a_{k+1} = 3 a_k - 2\text{;}\) hasil kali \(3\) dengan bilangan ganjil \(a_k\) adalah ganjil, dan setelah dikurangi 2 hasilnya tetap ganjil. Bagus. Mari kita rangkai semuanya menjadi sebuah pembuktian.
🔗

Bukti.

Kita mengklaim bahwa untuk setiap \(n \ge 0\text{,}\) bilangan \(a_n\) ganjil, dengan \(a_n = 3a_{n-1} - 2\) dan \(a_0 = 5\text{.}\)
🔗
Ketika \(n = 0\text{,}\) klaim tersebut benar karena \(a_0 = 5\) adalah bilangan ganjil.
🔗
Selanjutnya, kita dapat membuktikan bahwa \(a_n\) ganjil untuk setiap \(n\) yang lebih besar karena jika \(a_k\) ganjil, maka \(a_{k+1}\) juga ganjil (sebab \(a_{k+1} = 3a_{k} - 2\text{,}\) dan tiga kali bilangan ganjil dikurangi 2 selalu ganjil).
🔗
Oleh karena itu, \(a_n\) ganjil untuk semua \(n \ge 0\text{.}\)
🔗
🔗
Sebentar lagi kita akan memberikan struktur yang lebih ketat untuk pembuktian dengan induksi, tetapi gagasan dasarnya persis seperti di atas.
🔗
🔗

Subbagian Memformalkan Pembuktian

Induksi dapat membuktikan banyak pernyataan yang berlaku untuk semua bilangan asli, bukan hanya pernyataan tentang barisan. Secara khusus, induksi sebaiknya digunakan ketika ada cara untuk beralih dari satu kasus ke kasus berikutnya – ketika Anda dapat melihat cara untuk selalu “melakukan satu langkah lagi.”
🔗
Dengan mengingat cara kita menulis pernyataan dalam simbol logika, kita akan menggunakan induksi untuk membuktikan pernyataan berbentuk
\begin{equation*} \forall n P(n)\text{,} \end{equation*}
dengan semesta pembicaraan (nilai-nilai \(n\) yang dikuantifikasi) memiliki suatu unsur terkecil. Misalkan semesta pembicaraan tersebut adalah bilangan asli. Dengan demikian, kita membuktikan barisan pernyataan berikut:
\begin{equation*} P(0), P(1), P(2), P(3), \ldots\text{.} \end{equation*}
Dengan induksi, kita melakukannya dengan membuktikan suatu kasus dasar, yaitu bahwa \(P(0)\) benar (atau \(P(a)\text{,}\) dengan \(a\) unsur terkecil semesta pembicaraan kita). Selanjutnya, kita membuktikan langkah induksi, yaitu bahwa \(P(k) \imp P(k+1)\) untuk semua \(k \ge 0\) (atau \(k \ge a\)).
🔗
Bersama-sama, kedua bagian ini cukup untuk membuktikan bahwa \(P(n)\) benar untuk semua \(n\text{.}\) Bagaimana kita mengetahuinya? Dengan kata lain, mengapa gaya pembuktian ini sahih? Mari kita yakinkan diri bahwa \(P(3)\) benar. Kita tahu \(P(0)\) benar. Karena kita mengetahui \(P(0) \imp P(1)\text{,}\) kita juga mengetahui bahwa \(P(1)\) benar. Karena \(P(1) \imp P(2)\text{,}\) kita memperoleh bahwa \(P(2)\) benar. Terakhir, karena \(P(2) \imp P(3)\text{,}\) kita mengetahui bahwa \(P(3)\) benar. Tidak ada yang istimewa dari 3. Kita dapat melanjutkan sejauh yang kita inginkan, hingga nilai \(n\) berapa pun!
🔗
Bayangkan sederet domino yang didirikan pada sisinya. Kita ingin menyatakan bahwa satu menit kemudian, semua domino akan roboh. Agar hal ini terjadi, Anda perlu mendorong domino pertama. Itulah kasus dasar. Selain itu, domino-domino tersebut harus cukup berdekatan sehingga ketika satu domino roboh, domino itu menyebabkan domino berikutnya roboh. Itulah langkah induksi. Jika kedua syarat ini terpenuhi – Anda merobohkan domino pertama, dan setiap domino menyebabkan domino berikutnya roboh – maka semua domino akan roboh.
🔗
Induksi sangat ampuh! Bayangkan betapa lebih mudahnya merobohkan domino ketika Anda tidak perlu mendorong setiap domino sendiri. Anda cukup memulai reaksi berantai, lalu mengandalkan kedekatan antar-domino untuk menyelesaikan sisanya.
🔗
Ketika menulis pembuktian dengan induksi, kita akan mengikuti gaya baku. Menulis dengan gaya ini membantu kita menata gagasan dan bahkan dapat membantu kita merumuskan pembuktian.
🔗
Berikut struktur umum pembuktian dengan induksi matematika:
🔗

Struktur Pembuktian dengan Induksi.

Mulailah dengan menyatakan pernyataan yang ingin Anda buktikan: “Misalkan \(P(n)\) adalah pernyataan….” Untuk membuktikan bahwa \(P(n)\) benar untuk semua \(n \ge 0\text{,}\) Anda harus membuktikan dua fakta:
  1. Kasus dasar: Buktikan bahwa \(P(0)\) benar. Lakukan ini secara langsung. Bagian ini sering kali mudah.
    🔗
    🔗
  2. Langkah induksi: Buktikan bahwa \(P(k) \imp P(k+1)\) untuk semua \(k \ge 0\text{.}\) Artinya, buktikan bahwa untuk setiap \(k \ge 0\text{,}\) jika \(P(k)\) benar, maka \(P(k+1)\) juga benar. Ini adalah pembuktian pernyataan jika … maka …, sehingga Anda boleh mengasumsikan bahwa \(P(k)\) benar (\(P(k)\) disebut hipotesis induksi). Selanjutnya Anda harus menjelaskan mengapa \(P(k+1)\) juga benar berdasarkan asumsi tersebut.
    🔗
    🔗
🔗
Jika Anda berhasil membuktikan kedua bagian di atas, Anda dapat menyimpulkan, “Oleh karena itu, berdasarkan prinsip induksi matematika, pernyataan \(P(n)\) benar untuk semua \(n \ge 0\text{.}\)”
🔗
🔗
Terkadang pernyataan \(P(n)\) hanya benar untuk nilai \(n \ge 4\text{,}\) misalnya, atau mulai dari nilai lain. Dalam kasus tersebut, gantilah semua 0 di atas dengan 4 (atau nilai lain itu).
🔗
Sebelum mencoba membuktikan suatu pernyataan dengan induksi matematika, pikirkan terlebih dahulu mengapa pernyataan itu benar menggunakan penalaran induktif. Jelaskan mengapa induksi merupakan metode yang tepat, dan secara garis besar mengapa langkah induksi akan berhasil. Setelah itu, tulislah pembuktian formal dengan cermat menggunakan struktur di atas.
🔗
🔗

Subbagian Contoh

Berikut beberapa contoh pembuktian dengan induksi matematika.
🔗

Contoh 4.5.1.

Buktikan bahwa untuk setiap bilangan asli \(n \ge 1\text{,}\) berlaku \(1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}\text{.}\)
🔗
Penyelesaian.
Pertama, mari kita pikirkan persamaan ini secara induktif. Sebenarnya, kita tahu persamaan ini benar karena alasan lain (misalnya dengan membalik urutan lalu menjumlahkannya). Namun, mengapa induksi dapat diterapkan? Ruas kiri menjumlahkan bilangan dari 1 sampai \(n\text{.}\) Jika kita sudah mengetahui jumlah itu, menambahkan satu suku lagi (\(n+1\)) tidaklah sulit. Sebagai contoh, jika \(n = 100\text{,}\) misalkan kita tahu bahwa jumlah 100 bilangan pertama adalah \(5050\) (jadi \(1 + 2 + 3 + \cdots + 100 = 5050\text{,}\) yang memang benar). Untuk mencari jumlah 101 bilangan pertama, lebih masuk akal jika kita cukup menambahkan 101 pada 5050 daripada menghitung ulang seluruh jumlah tersebut. Kita memperoleh \(1 + 2 + 3 + \cdots + 100 + 101 = 5050 + 101 = 5151\text{.}\) Sebenarnya, menambahkan satu suku lagi akan selalu mudah. Inilah alasan kita sebaiknya menggunakan induksi.
🔗
Sekarang, pembuktian formalnya:
🔗
Bukti.
Misalkan \(P(n)\) adalah pernyataan \(1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}\text{.}\) Kita akan menunjukkan bahwa \(P(n)\) benar untuk semua bilangan asli \(n \ge 1\text{.}\)
🔗
Kasus dasar: \(P(1)\) adalah pernyataan \(1 = \frac{1(1+1)}{2}\text{,}\) yang jelas benar.
🔗
Langkah induksi: Misalkan \(k \ge 1\) suatu bilangan asli. Asumsikan (untuk induksi) bahwa \(P(k)\) benar. Artinya, \(1 + 2 + 3 + \cdots + k = \frac{k(k+1)}{2}\text{.}\) Kita akan membuktikan bahwa \(P(k+1)\) juga benar. Dengan kata lain, kita harus membuktikan \(1 + 2 + 3 + \cdots + k + (k+1) = \frac{(k+1)(k+2)}{2}\text{.}\) Untuk membuktikan persamaan ini, mulailah dengan menambahkan \(k+1\) pada kedua ruas hipotesis induksi:
\begin{equation*} 1 + 2 + 3 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1)\text{.} \end{equation*}
🔗
Dengan menyederhanakan ruas kanan, kita memperoleh:
\begin{align*} \frac{k(k+1)}{2} + k+1 \amp = \frac{k(k+1)}{2} + \frac{2(k+1)}{2}\\ \amp = \frac{k(k+1) + 2(k+1)}{2}\\ \amp = \frac{(k+2)(k+1)}{2}\text{.} \end{align*}
🔗
Jadi, \(P(k+1)\) benar, sehingga berdasarkan prinsip induksi matematika, \(P(n)\) benar untuk semua bilangan asli \(n \ge 1\text{.}\)
🔗
🔗
🔗
🔗
Perhatikan bahwa pada bagian pembuktian ketika kita membuktikan \(P(k+1)\) dari \(P(k)\text{,}\) kita menggunakan persamaan dalam \(P(k)\text{.}\) Persamaan itu adalah hipotesis induksi. Cara menggunakan hipotesis induksi biasanya mudah terlihat ketika membuktikan fakta tentang penjumlahan seperti ini. Dalam pembuktian lain, tempat penggunaannya mungkin tidak begitu jelas.
🔗

Contoh 4.5.2.

Buktikan bahwa untuk semua \(n \in \N\text{,}\) \(6^n - 1\) merupakan kelipatan 5.
🔗
Penyelesaian.
Sekali lagi, mulailah dengan memahami dinamika masalahnya. Apa akibat dari menaikkan \(n\text{?}\) Mari kita coba beberapa contoh. Jika \(n = 1\text{,}\) maka benar bahwa \(6^1 - 1 = 5\) merupakan kelipatan 5. Apa yang terjadi ketika \(n\) dinaikkan menjadi 2? Kita memperoleh \(6^2 - 1 = 35\text{,}\) yang juga merupakan kelipatan 5. Berikutnya, \(n = 3\text{.}\) Namun, alih-alih sekadar mencari \(6^3 - 1\text{,}\) mari kita tanyakan apa akibat kenaikan \(n\) tersebut. Kita tetap akan mengurangkan 1, tetapi terlebih dahulu kita mengalikan dengan satu faktor 6 lagi. Dilihat dengan cara lain, kita mengalikan bilangan yang satu lebih besar daripada suatu kelipatan 5 dengan 6 (karena \(6^2 - 1\) merupakan kelipatan 5, maka \(6^2\) satu lebih besar daripada suatu kelipatan 5). Seperti apakah bilangan yang satu lebih besar daripada kelipatan 5? Digit terakhirnya pasti 1 atau 6. Apa yang terjadi jika bilangan semacam itu dikalikan dengan 6? Hasilnya bergantung pada bilangannya, tetapi bagaimanapun juga, digit terakhir bilangan baru itu pasti 6. Jika kemudian kita mengurangkan 1, digit terakhirnya menjadi 5, sehingga hasilnya merupakan kelipatan 5.
🔗
Intinya, setiap kali kita mengalikan dengan satu faktor 6 lagi, kita tetap memperoleh bilangan berdigit terakhir 6, sehingga mengurangkan 1 menghasilkan kelipatan 5. Sekarang, pembuktian formalnya:
🔗
Bukti.
Misalkan \(P(n)\) adalah pernyataan, “\(6^n - 1\) merupakan kelipatan 5.” Kita akan membuktikan bahwa \(P(n)\) benar untuk semua \(n \in \N\text{.}\)
🔗
Kasus dasar: \(P(0)\) benar: \(6^0 -1 = 0\text{,}\) yang merupakan kelipatan 5.
🔗
Langkah induksi: Misalkan \(k\) suatu bilangan asli sembarang. Asumsikan, untuk induksi, bahwa \(P(k)\) benar. Artinya, \(6^k - 1\) merupakan kelipatan \(5\text{.}\) Dengan demikian, \(6^k - 1 = 5j\) untuk suatu bilangan bulat \(j\text{.}\) Ini berarti \(6^k = 5j + 1\text{.}\) Kalikan kedua ruas dengan \(6\text{:}\)
\begin{equation*} 6^{k+1} = 6(5j+1) = 30j + 6\text{.} \end{equation*}
🔗
Namun, kita ingin mengetahui \(6^{k+1} - 1\text{,}\) jadi kurangkan 1 dari kedua ruas:
\begin{equation*} 6^{k+1} - 1 = 30j + 5\text{.} \end{equation*}
🔗
Tentu saja \(30j+5 = 5(6j+1)\text{,}\) sehingga bilangan ini merupakan kelipatan 5.
🔗
Oleh karena itu, \(6^{k+1} - 1\) merupakan kelipatan 5, atau dengan kata lain, \(P(k+1)\) benar. Jadi, berdasarkan prinsip induksi matematika, \(P(n)\) benar untuk semua \(n \in \N\text{.}\)
🔗
🔗
🔗
🔗
Kita perlu sedikit cerdik (yakni menggunakan aljabar) untuk menemukan \(6^k - 1\) di dalam \(6^{k+1} - 1\) sebelum dapat menerapkan hipotesis induksi. Hal inilah yang dapat membuat pembuktian dengan induksi terasa menantang.
🔗
Dalam dua contoh di atas, kita mulai dari \(n = 1\) atau \(n = 0\text{.}\) Jika perlu, kita dapat mulai dari nilai yang lebih besar.
🔗

Contoh 4.5.3.

Buktikan bahwa \(n^2 \lt 2^n\) untuk semua bilangan bulat \(n \ge 5\text{.}\)
🔗
Penyelesaian.
Pertama, perhatikan gagasan argumennya. Apa yang terjadi ketika kita menaikkan \(n\) sebesar 1? Pada ruas kiri, kita menaikkan bilangan yang dikuadratkan dan beralih ke bilangan kuadrat berikutnya. Pada ruas kanan, kita menaikkan pangkat 2. Artinya, kita menggandakan bilangan tersebut. Jadi pertanyaannya adalah, bagaimana hubungan menggandakan suatu bilangan dengan beralih ke bilangan kuadrat berikutnya? Perhatikan selisih dua bilangan kuadrat berurutan. Kita memiliki \((n+1)^2 - n^2\text{.}\) Bentuk ini dapat difaktorkan:
\begin{equation*} (n+1)^2 - n^2 = (n+1-n)(n+1+n) = 2n+1\text{.} \end{equation*}
🔗
Sementara itu, menggandakan ruas kanan menambah nilainya sebesar \(2^n\text{,}\) sebab \(2^{n+1} = 2^n + 2^n\text{.}\) Ketika \(n\) cukup besar, \(2^n > 2n + 1\text{.}\)
🔗
Yang kita nyatakan di sini adalah bahwa setiap kali \(n\) bertambah, pertambahan ruas kiri lebih kecil daripada pertambahan ruas kanan. Jadi, jika ruas kiri bermula lebih kecil (seperti ketika \(n = 5\)), nilainya tidak akan pernah menyusul. Sekarang, pembuktian formalnya:
🔗
Bukti.
Misalkan \(P(n)\) adalah pernyataan \(n^2 \lt 2^n\text{.}\) Kita akan membuktikan bahwa \(P(n)\) benar untuk semua bilangan bulat \(n \ge 5\text{.}\)
🔗
Kasus dasar: \(P(5)\) adalah pernyataan \(5^2 \lt 2^5\text{.}\) Karena \(5^2 = 25\) dan \(2^5 = 32\text{,}\) kita melihat bahwa \(P(5)\) memang benar.
🔗
Langkah induksi: Misalkan \(k \ge 5\) suatu bilangan bulat sembarang. Asumsikan, untuk induksi, bahwa \(P(k)\) benar. Artinya, asumsikan \(k^2 \lt 2^k\text{.}\) Kita akan membuktikan bahwa \(P(k+1)\) benar, yakni \((k+1)^2 \lt 2^{k+1}\text{.}\) Untuk membuktikan pertidaksamaan semacam ini, mulailah dari ruas kiri dan bergerak menuju ruas kanan:
\begin{align*} (k+1)^2 \amp = k^2 + 2k + 1 \amp\\ \amp \lt 2^k + 2k + 1 \amp \ldots\text{berdasarkan hipotesis induksi.}\\ \amp \lt 2^k + 2^k \amp \ldots\text{ karena } 2k + 1 \lt 2^k \text{ untuk }k \ge 5.\\ \amp = 2^{k+1}. \amp \end{align*}
🔗
Dengan mengikuti rangkaian persamaan dan pertidaksamaan tersebut, kita memperoleh \((k+1)^2 \lt 2^{k+1}\text{,}\) atau dengan kata lain, \(P(k+1)\) benar. Oleh karena itu, berdasarkan prinsip induksi matematika, \(P(n)\) benar untuk semua \(n \ge 5\text{.}\)
🔗
🔗
🔗
🔗
Contoh sebelumnya mungkin mengingatkan Anda pada prinsip lintasan pacu dari kalkulus, yang menyatakan bahwa jika \(f(a) \lt g(a)\text{,}\) dan \(f'(x) \lt g'(x)\) untuk \(x > a\text{,}\) maka \(f(x) \lt g(x)\) untuk \(x > a\text{.}\) Gagasannya sama: fungsi yang lebih besar bertambah lebih cepat daripada fungsi yang lebih kecil, sehingga fungsi yang lebih besar akan tetap lebih besar. Dalam matematika diskret, kita tidak menggunakan turunan, jadi kita memperhatikan selisih. Oleh sebab itu, induksi merupakan metode yang tepat.
🔗

Sebuah Peringatan.

Kekuatan besar membawa tanggung jawab besar. Induksi bukanlah sihir. Kemampuan untuk mengasumsikan bahwa \(P(k)\) benar tampak sangat ampuh. Lagi pula, kita sedang berusaha membuktikan bahwa \(P(n)\) benar, dan satu-satunya perbedaan terletak pada variabelnya: \(k\) dibandingkan dengan \(n\text{.}\) Apakah kita mengasumsikan bahwa hal yang ingin kita buktikan sudah benar? Tidak demikian. Kita mengasumsikan \(P(k)\) benar hanya untuk membuktikan bahwa \(P(k+1)\) benar.
🔗
Meskipun demikian, Anda mungkin mulai percaya bahwa apa pun dapat dibuktikan dengan induksi. Perhatikan “pembuktian” keliru berikut bahwa setiap orang Kanada memiliki warna mata yang sama: Misalkan \(P(n)\) adalah pernyataan bahwa sembarang \(n\) orang Kanada memiliki warna mata yang sama. \(P(1)\) benar, karena setiap orang memiliki warna mata yang sama dengan dirinya sendiri. Sekarang asumsikan \(P(k)\) benar. Artinya, asumsikan bahwa dalam sembarang kelompok beranggotakan \(k\) orang Kanada, setiap orang memiliki warna mata yang sama. Sekarang perhatikan sembarang kelompok beranggotakan \(k+1\) orang Kanada. \(k\) orang pertama dalam kelompok itu pasti memiliki warna mata yang sama, karena \(P(k)\) benar. Selain itu, \(k\) orang terakhir juga pasti memiliki warna mata yang sama, karena \(P(k)\) benar. Jadi, semua orang dalam kelompok itu pasti memiliki warna mata yang sama. Dengan demikian, \(P(k+1)\) benar. Maka, berdasarkan prinsip induksi matematika, \(P(n)\) benar untuk semua \(n\text{.}\)
🔗
Jelas ada sesuatu yang keliru. Masalahnya adalah pembuktian bahwa \(P(k)\) mengimplikasikan \(P(k+1)\) mengasumsikan \(k \ge 2\text{.}\) Kita baru menunjukkan bahwa \(P(1)\) benar. Padahal, \(P(2)\) salah. Cobalah membaca kembali paragraf sebelumnya dengan mengganti setiap \(k\) dengan \(1\text{.}\) Dapatkah Anda menemukan kekeliruan dalam argumen tersebut?
🔗
🔗
🔗

Pertanyaan Bacaan Pertanyaan Bacaan

1.

Misalkan Anda ingin membuktikan dengan induksi matematika bahwa \(1+3+5+\cdots+2n-1 = n^2\) untuk semua nilai \(n \ge 1\text{.}\) Manakah di antara pilihan berikut yang dapat menjadi baris pertama pembuktian? Pilih semua yang berlaku.
🔗
  • Misalkan \(P(n)\) adalah pernyataan “\(1+3+5+\cdots+2n-1 = n^2\text{.}\)”
    🔗
  • Benar. Perhatikan khususnya bahwa kita tidak memasukkan “untuk semua \(n \ge 1\)” sebagai bagian dari definisi \(P(n)\text{.}\)
  • Untuk setiap \(n \ge 1\text{,}\) misalkan \(P(n)\) adalah pernyataan, “jumlah \(n\) bilangan ganjil pertama adalah \(n^2\text{.}\)”
    🔗
  • Ini benar. Perhatikan bahwa mengatakan kita mendefinisikan \(P(n)\) untuk setiap \(n\ge 1\) berbeda dengan mengatakan bahwa \(P(n)\) mencakup “...untuk semua \(n\ge 1\text{.}\)”
  • Asumsikan \(1+3+\cdots + 2n-1 = n^2\) untuk semua \(n \ge 1\text{.}\)
    🔗
  • Inilah yang hendak Anda buktikan, sehingga Anda tidak boleh mengasumsikannya. Nanti dalam pembuktian (pada langkah induksi), kita akan mengasumsikan bahwa \(P(k)\) benar untuk suatu \(k\) sembarang, tetapi itu tidak sama dengan mengasumsikan kebenarannya untuk semua \(n\) sekaligus.
  • Misalkan \(P(n)\) adalah pernyataan, “\(1+3+\cdots+2n-1 = n^2\) untuk semua \(n \ge 1\text{.}\)”
    🔗
  • Ini tidak masuk akal: apakah bentuk \(P(3)\text{?}\) Bahwa \(1 + 3 + 5 = 3^2\) untuk semua \(3 \ge 1\text{?}\)
  • Karena \(P(1) = 1 = 1^2\text{,}\) kasus dasarnya benar.
    🔗
  • Ada dua masalah di sini: pertama, Anda perlu menyatakan apa itu \(P(n)\text{.}\) Kedua, \(P(1)\) adalah pernyataan, sehingga tidak mungkin sama dengan bilangan 1.
🔗

2.

Misalkan Anda ingin membuktikan bahwa \(P(n,3) \ge \binom{n}{3}\) untuk semua \(n \ge 4\text{.}\) Tuliskan baris pertama pembuktian dengan induksi.
🔗
🔗

3.

Pertanyaan apa yang Anda miliki? Tuliskan setidaknya satu pertanyaan tentang isi bagian ini yang mungkin membuat Anda atau teman sekelas penasaran setelah membacanya.
🔗
🔗
🔗

Latihan Soal Latihan

1.

Misalkan Anda sedang mencoba membuktikan dengan induksi matematika bahwa pernyataan \(P(n)\) benar untuk semua \(n \ge 0\text{.}\) Apa yang perlu Anda buktikan pada langkah induksi? (Pilih semua yang berlaku.)
🔗
  • Bahwa dengan mengasumsikan \(P(k)\) benar untuk suatu \(k \ge 0\) sembarang, kita dapat membuktikan bahwa \(P(k+1)\) benar.
    🔗
  • Bahwa \(P(k)\) mengimplikasikan \(P(k+1)\) untuk semua \(k \ge 0\text{.}\)
    🔗
  • Bahwa dengan mengasumsikan \(P(k+1)\) benar untuk suatu \(k \ge 0\) sembarang, kita dapat membuktikan bahwa \(P(k)\) benar.
    🔗
  • Bahwa \(P(k+1)\) mengimplikasikan \(P(k)\) untuk semua \(k \ge 0\text{.}\)
    🔗
  • Bahwa \(P(k)\) mengimplikasikan \(P(k+1)\) untuk setidaknya satu \(k \ge 0\text{.}\)
    🔗
🔗

2.

Misalkan Anda ingin membuktikan pernyataan berikut:
\begin{equation*} 2 + 4 + 6 + \cdots + 2n = n(n+1) \text{ untuk semua } n \ge 1\text{.} \end{equation*}
Apa baris pertama pembuktian dengan induksi yang tepat?
🔗
  • Misalkan \(P(n)\) adalah pernyataan “\(2 + 4 + 6 + \cdots + 2n = n(n+1)\text{.}\)”
    🔗
  • Misalkan \(P(n)\) adalah pernyataan “\(2 + 4 + 6 + \cdots + 2n = n(n-1)\) untuk semua \(n \ge 1\text{.}\)”
    🔗
  • Asumsikan \(P(n)\) benar untuk semua \(n \ge 1\text{.}\)
    🔗
  • Misalkan \(P(n) = 2 + 4 + 6 + \cdots + 2n\text{.}\)
    🔗
  • Misalkan \(P(n) = n(n+1)\) untuk semua \(n \ge 1\text{.}\)
    🔗
🔗

3.

Misalkan Anda sedang membuktikan pernyataan berikut dengan induksi matematika:
\begin{equation*} 2 + 4 + 6 + \cdots + 2n = n(n+1) \text{ untuk semua } n \ge 1\text{.} \end{equation*}
Apa yang perlu Anda tunjukkan untuk membuktikan kasus dasar?
🔗
  • Tunjukkan bahwa \(P(1)\) benar. Artinya, tunjukkan bahwa \(2 = 1(1+1)\text{.}\)
    🔗
  • Tunjukkan bahwa \(P(2)\) benar. Artinya, tunjukkan bahwa \(2 + 4 = 2(2+1)\text{.}\)
    🔗
  • Meskipun penjumlahan dimulai dengan \(2\text{,}\) kita perlu memperhatikan nilai \(n\) terkecil yang dicakup oleh pernyataan \(P(n)\text{.}\)
  • Tunjukkan bahwa \(P(1)\) dan \(P(2)\) keduanya benar.
    🔗
  • Tunjukkan bahwa \(P(1)\) mengimplikasikan \(P(2)\text{.}\)
    🔗
  • Tidak perlu menunjukkan apa pun karena penjumlahan tersebut sudah memiliki lebih dari \(n = 1\) suku.
    🔗
🔗

4.

Misalkan Anda sedang membuktikan pernyataan berikut dengan induksi matematika:
\begin{equation*} 2 + 4 + 6 + \cdots + 2n = n(n+1) \text{ untuk semua } n \ge 1\text{.} \end{equation*}
Apa baris pertama langkah induksi yang tepat?
🔗
  • Asumsikan \(P(k)\) benar untuk suatu \(k \ge 1\) sembarang; artinya, asumsikan \(2+4+6+\cdots + 2k = k(k+1)\text{.}\)
    🔗
  • Asumsikan \(P(k)\) benar untuk semua \(k \ge 1\text{;}\) artinya, asumsikan \(2+4+6+\cdots + 2k = k(k+1)\text{.}\)
    🔗
  • Ini mengasumsikan bahwa \(P(k)\) benar untuk semua \(k \ge 1\text{,}\) tepat seperti hal yang hendak dibuktikan. Dalam langkah induksi, kita hanya boleh mengasumsikan \(P(k)\) untuk suatu \(k\) sembarang, lalu membuktikan \(P(k+1)\text{.}\)
  • Asumsikan \(P(k)\) mengimplikasikan \(P(k+1)\) untuk suatu \(k \ge 1\) sembarang.
    🔗
  • Asumsikan \(P(k)\) benar untuk suatu \(k \ge 1\) yang besar; misalnya, asumsikan \(2 + 4 + 6 + \cdots + 432 = 216(217)\text{.}\)
    🔗
🔗

5.

Susun beberapa pernyataan di bawah ini untuk membentuk pembuktian dengan induksi yang benar bahwa relasi rekurensi \(a_n = 5a_{n-1} + 4\) dengan syarat awal \(a_0 = 0\) memiliki rumus tertutup \(a_n = 5^n - 1\text{.}\)
🔗
🔗

6.

Susun beberapa pernyataan di bawah ini untuk membentuk pembuktian dengan induksi yang benar bahwa untuk semua \(n \ge 1\text{,}\) bilangan \(14^n - 1\) merupakan kelipatan \(13\text{.}\)
🔗
🔗

7.

Susun beberapa pernyataan di bawah ini untuk membentuk pembuktian dengan induksi yang benar bahwa untuk semua \(n \ge 1\text{,}\) berlaku \(1+1+2+3+5+\cdots + F_n = F_{n+2} - 1\text{,}\) dengan \(F_n\) bilangan Fibonacci ke-\(n\text{.}\)
🔗
🔗
🔗

Latihan Latihan Tambahan

1.

Dalam perjalanan ke pasar, Anda menukar sapi Anda dengan sejumlah biji espreso cokelat hitam ajaib. Biji-biji ini memiliki sifat bahwa setiap malam tepat tengah malam, setiap biji membelah menjadi dua sehingga jumlah koleksi Anda berlipat ganda. Anda memutuskan untuk memanfaatkan hal ini, dan setiap pagi (sekitar pukul 08.00) Anda memakan 5 biji.
  1. Jelaskan mengapa benar bahwa jika pada tengah hari di hari ke-\(n\) jumlah biji Anda berakhiran 5, maka pada tengah hari di hari ke-\(n+1\) jumlah biji Anda juga akan berakhiran 5.
    🔗
    🔗
  2. Mengapa fakta sebelumnya belum cukup untuk menyimpulkan bahwa jumlah biji Anda akan selalu berakhiran 5? Fakta tambahan apa yang Anda perlukan?
    🔗
    🔗
  3. Dengan mengasumsikan bahwa Anda memiliki fakta tambahan pada bagian (b) dan telah berhasil membuktikan fakta pada bagian (a), bagaimana Anda mengetahui bahwa jumlah biji Anda akan selalu berakhiran 5? Gambarkan apa yang terjadi dengan menjelaskan secara cermat bagaimana kedua fakta di atas membuktikan bahwa jumlah biji Anda akan berakhiran 5, khususnya pada hari ke-4. Dengan kata lain, jelaskan mengapa induksi berlaku dalam konteks ini.
    🔗
    🔗
🔗
🔗

2.

Gunakan induksi untuk membuktikan bahwa untuk semua \(n \in \N\text{,}\) berlaku \(\d\sum_{k=0}^n 2^k = 2^{n+1} - 1\text{.}\)
🔗
🔗

3.

Buktikan bahwa \(7^n - 1\) merupakan kelipatan 6 untuk semua \(n \in \N\text{.}\)
🔗
🔗

4.

Buktikan bahwa \(1 + 3 + 5 + \cdots + (2n-1) = n^2\) untuk semua \(n \ge 1\text{.}\)
🔗
🔗

5.

Buktikan bahwa \(F_0 + F_2 + F_4 + \cdots + F_{2n} = F_{2n+1} - 1\text{,}\) dengan \(F_n\) bilangan Fibonacci ke-\(n\text{.}\)
🔗
🔗

6.

Buktikan bahwa \(2^n \lt n!\) untuk semua \(n \ge 4\text{.}\) (Ingat, \(n! = 1\cdot 2 \cdot 3 \cdot \cdots\cdot n\text{.}\))
🔗
🔗

7.

Buktikan, dengan induksi matematika, bahwa \(F_0 + F_1 + F_2 + \cdots + F_{n} = F_{n+2} - 1\text{,}\) dengan \(F_n\) bilangan Fibonacci ke-\(n\) (\(F_0 = 0\text{,}\) \(F_1 = 1\) dan \(F_n = F_{n-1} + F_{n-2}\)).
🔗
🔗

8.

Zombi Euler dan Zombi Cauchy, dua matematikawan zombi terkenal, baru saja mendaftar akun Myspace. Setelah satu hari, Zombi Cauchy memiliki lebih banyak pengikut daripada Zombi Euler. Setiap hari setelah itu, jumlah pengikut baru Zombi Cauchy persis sama dengan jumlah pengikut baru Zombi Euler (dan keduanya tidak kehilangan pengikut). Jelaskan bagaimana pembuktian dengan induksi matematika dapat menunjukkan bahwa pada setiap hari setelah hari pertama, Zombi Cauchy akan memiliki lebih banyak pengikut daripada Zombi Euler. Artinya, jelaskan kasus dasar dan langkah induksinya, serta mengapa keduanya membuktikan bahwa Zombi Cauchy akan memiliki lebih banyak pengikut pada hari keempat.
🔗
🔗

9.

Tentukan jumlah poin terbesar yang tidak mungkin diperoleh secara tepat oleh sebuah tim sepak bola Amerika hanya dengan gol lapangan bernilai 3 poin dan touchdown bernilai 7 poin (abaikan kemungkinan safety, kegagalan poin tambahan, dan konversi dua poin). Buktikan dengan induksi matematika bahwa jawaban Anda benar.
🔗
Petunjuk.
Tidak mungkin mencetak tepat 11 poin. Dapatkah Anda membuktikan bahwa Anda dapat mencetak \(n\) poin untuk setiap \(n \ge 12\text{?}\)
🔗
🔗
🔗

10.

Buktikan bahwa jumlah kuadrat dari \(n\) bilangan asli pertama diberikan oleh rumus berikut
\begin{equation*} 1^2 +2^2 +3^2+\cdots+n^2 = \frac{n(n+1)(2n+1)}{6}\text{.} \end{equation*}
🔗
🔗

11.

Buktikan bahwa jumlah sudut dalam segi-\(n\) cembung adalah \((n-2)\cdot 180^\circ\text{.}\) (Segi-\(n\) cembung adalah poligon bersisi \(n\) yang setiap sudut dalamnya kurang dari \(180^\circ\text{.}\))
🔗
Petunjuk.
Mulailah dengan segi-\((k+1)\text{,}\) lalu bagilah menjadi segi-\(k\) dan sebuah segitiga.
🔗
🔗
🔗

12.

Apa yang salah dengan “pembuktian” berikut atas “fakta” bahwa \(n+3 = n+7\) untuk semua nilai \(n\) (selain, tentu saja, bahwa pernyataan yang hendak dibuktikannya memang salah)?
🔗
Bukti.
Misalkan \(P(n)\) adalah pernyataan bahwa \(n + 3 = n + 7\text{.}\) Kita akan membuktikan bahwa \(P(n)\) benar untuk semua \(n \in \N\text{.}\) Untuk langkah induksi, asumsikan bahwa \(P(k)\) benar. Artinya, \(k+3 = k+7\text{.}\) Kita harus menunjukkan bahwa \(P(k+1)\) benar. Karena \(k + 3 = k + 7\text{,}\) tambahkan 1 pada kedua ruas. Ini menghasilkan \(k + 3 + 1 = k + 7 + 1\text{.}\) Dengan mengelompokkan kembali, diperoleh \((k+1) + 3 = (k+1) + 7\text{.}\) Namun, ini tepat merupakan \(P(k+1)\text{.}\) Jadi, berdasarkan prinsip induksi matematika, \(P(n)\) benar untuk semua \(n \in \N\text{.}\)
🔗
🔗
🔗

13.

Pembuktian pada soal sebelumnya tidak berhasil. Namun, jika kita mengubah “fakta” tersebut, kita dapat memperoleh pembuktian yang benar. Buktikan bahwa \(n + 3 \lt n + 7\) untuk semua nilai \(n \in \N\text{.}\) Anda dapat membuktikannya secara aljabar (tanpa induksi), tetapi tujuan latihan ini adalah menuliskan pembuktian induksi yang sah.
🔗
🔗

14.

Temukan kekeliruan dalam “pembuktian” berikut atas “fakta” bahwa \(n \lt 100\) untuk setiap \(n \in \N\text{.}\)
🔗
Bukti.
Misalkan \(P(n)\) adalah pernyataan \(n \lt 100\text{.}\) Kita akan membuktikan bahwa \(P(n)\) benar untuk semua \(n \in \N\text{.}\) Pertama, kita membuktikan kasus dasar: ketika \(n = 0\text{,}\) \(P(n)\) benar karena \(0 \lt 100\text{.}\) Sekarang, untuk langkah induksi, asumsikan bahwa \(P(k)\) benar. Artinya, \(k \lt 100\text{.}\) Jika \(k \lt 100\text{,}\) maka \(k\) adalah suatu bilangan, misalnya 80. Tentu saja, \(80+1 = 81\text{,}\) yang masih kurang dari 100. Jadi, \(k +1 \lt 100\) juga berlaku. Namun, inilah yang dinyatakan oleh \(P(k+1)\text{,}\) sehingga kita telah menunjukkan bahwa \(P(k) \imp P(k+1)\text{.}\) Jadi, berdasarkan prinsip induksi matematika, \(P(n)\) benar untuk semua \(n \in \N\text{.}\)
🔗
🔗
🔗

15.

Meskipun pembuktian di atas tidak berhasil (memang tidak mungkin berhasil karena pernyataan yang hendak dibuktikannya salah!), kita dapat membuktikan sesuatu yang serupa. Buktikan bahwa terdapat barisan bilangan \(a_1, a_2, a_3, \ldots\) yang naik tegas (bilangan-bilangan itu tidak harus bulat) sedemikian sehingga \(a_n \lt 100\) untuk semua \(n \ge 1\text{.}\) (Yang dimaksud dengan naik tegas adalah \(a_n \lt a_{n+1}\) untuk semua \(n \ge 1\text{.}\) Jadi, setiap suku harus lebih besar daripada suku sebelumnya.)
🔗
Petunjuk.
Untuk langkah induksi, Anda dapat mengasumsikan bahwa Anda telah memiliki barisan yang naik tegas hingga \(a_k\text{,}\) dengan \(a_k \lt 100\text{.}\) Sekarang Anda hanya perlu menentukan suku berikutnya, \(a_{k+1}\text{,}\) agar \(a_{k} \lt a_{k+1} \lt 100\text{.}\) Berapakah seharusnya \(a_{k+1}\text{?}\)
🔗
🔗
🔗

16.

Apa yang salah dengan “pembuktian” berikut atas “fakta” bahwa untuk semua \(n \in \N\text{,}\) bilangan \(n^2 + n\) adalah ganjil?
🔗
Bukti.
Misalkan \(P(n)\) adalah pernyataan “\(n^2 + n\) adalah ganjil.” Kita akan membuktikan bahwa \(P(n)\) benar untuk semua \(n \in \N\text{.}\) Untuk langkah induksi, andaikan bahwa \(P(k)\) benar, yaitu bahwa \(k^2 + k\) adalah ganjil. Sekarang perhatikan pernyataan \(P(k+1)\text{.}\) Kita mempunyai \((k+1)^2 + (k+1) = k^2 + 2k + 1 + k + 1 = k^2 + k + 2k + 2\text{.}\) Berdasarkan hipotesis induksi, \(k^2 + k\) adalah ganjil, dan tentu saja \(2k + 2\) adalah genap. Bilangan ganjil ditambah bilangan genap selalu ganjil, sehingga \((k+1)^2 + (k+1)\) adalah ganjil. Jadi, berdasarkan prinsip induksi matematika, \(P(n)\) benar untuk semua \(n \in \N\text{.}\)
🔗
🔗
🔗

17.

Sekarang berikan pembuktian yang sah (dengan induksi, meskipun Anda mungkin dapat membuktikannya tanpa induksi) untuk pernyataan “Untuk semua \(n \in \N\text{,}\) bilangan \(n^2 + n\) adalah genap.”
🔗
Petunjuk.
Untuk langkah induksi, Anda perlu menunjukkan bahwa \((k+1)^2 + (k+1)\) adalah genap. Jabarkan bentuk ini dan temukan bagian yang berupa \(k^2 + k\text{.}\) Apa yang telah Anda asumsikan tentang besaran tersebut?
🔗
🔗
🔗

18.

Buktikan bahwa terdapat barisan bilangan real positif \(a_0, a_1, a_2, \ldots\) sedemikian sehingga jumlah parsial \(a_0 + a_1 + a_2 + \cdots + a_n\) kurang dari \(2\) untuk semua \(n \in \N\text{.}\) Petunjuk: Pikirkan bagaimana Anda dapat mendefinisikan \(a_{k+1}\) agar argumen induksi berhasil.
🔗
Petunjuk.
Soal ini serupa dengan Latihan 15. Di sana Anda menunjukkan bahwa semua suku suatu barisan kurang dari suatu nilai, sedangkan di sini Anda menunjukkan bahwa setiap jumlah parsialnya kurang dari suatu nilai. Namun, jumlah-jumlah parsial tersebut membentuk sebuah barisan, sehingga kedua soal ini sebenarnya sangat serupa.
🔗
🔗
🔗

19.

Gunakan induksi untuk membuktikan bahwa jika \(n\) orang semuanya berjabat tangan satu sama lain, jumlah seluruh jabat tangan adalah \(\frac{n(n-1)}{2}\text{.}\)
🔗
Petunjuk.
Kita telah membuktikan hasil ini tanpa menggunakan induksi, tetapi memandang masalah ini secara induktif memberikan wawasan baru (dan juga menyenangkan).
🔗
Pertanyaan yang perlu Anda jawab untuk melengkapi langkah induksi adalah: berapa banyak jabat tangan baru yang terjadi ketika orang ke-\((k+1)\) memasuki ruangan? Mengapa penambahan jumlah ini menghasilkan rumus yang benar?
🔗
🔗
🔗

20.

Gunakan induksi untuk membuktikan bahwa \(\d\sum_{k=0}^n {n \choose k} = 2^n\text{.}\) Dengan kata lain, jumlah pada baris ke-\(n\) segitiga Pascal adalah \(2^n\text{.}\)
🔗
Petunjuk.
Gagasannya adalah sebagai berikut: kita dapat memperoleh baris ke-\(k+1\) dengan menjumlahkan pasangan-pasangan entri yang bersebelahan pada baris ke-\(k\text{,}\) dengan menganggap terdapat entri 0 di kedua ujung baris. Dengan konvensi ini, setiap entri pada baris ke-\(k\) digunakan dua kali. Jadi, setiap kali kita turun ke baris berikutnya, jumlah keseluruhannya menjadi dua kali lipat. Tentu saja, baris ke-0 memiliki jumlah \(1 = 2^0\) (kasus dasar). Sekarang cobalah menyatakan gagasan ini secara tepat dalam pembuktian induksi formal. Untuk langkah induksi, Anda akan menggunakan fakta bahwa \({n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}\text{.}\)
🔗
🔗
🔗

21.

Gunakan induksi untuk membuktikan \({4 \choose 0} + {5 \choose 1} + {6 \choose 2} + \cdots + {4+n \choose n} = {5+n \choose n}\text{.}\) (Ini merupakan salah satu contoh teorema tongkat hoki.)
🔗
Petunjuk.
Untuk memahami mengapa ini benar, cobalah pada salinan segitiga Pascal. Kita menjumlahkan entri-entri sepanjang sebuah diagonal, dimulai dari 1 di sisi kiri baris ke-4. Misalkan kita menjumlahkan 5 entri pertama pada diagonal ini. Klaimnya adalah bahwa jumlah tersebut sama dengan entri di bawah dan di sebelah kiri entri terakhir dari kelima entri itu. Perhatikan bahwa jika klaim ini benar dan kemudian kita menjumlahkan 6 entri pertama, kita perlu menambahkan entri yang terletak satu posisi di sebelah kanan jumlah sebelumnya. Namun, kedua entri ini jika dijumlahkan menghasilkan entri di bawah keduanya, yang terletak di bawah dan di sebelah kiri entri terakhir dari keenam entri pada diagonal tersebut. Jika Anda mengikuti penjelasan itu, Anda dapat melihat apa yang terjadi. Namun, penjelasan tersebut belum merupakan pembuktian yang baik. Diperlukan pembuktian induksi formal.
🔗
🔗
🔗

22.

Gunakan aturan hasil kali logaritma (\(\log(ab) = \log(a) + \log(b)\)) untuk membuktikan, dengan induksi pada \(n\text{,}\) bahwa \(\log(a^n) = n \log(a)\text{,}\) untuk setiap bilangan real positif \(a\) dan setiap bilangan asli \(n \ge 2\text{.}\)
🔗
🔗

23.

Misalkan \(f_1, f_2,\ldots, f_n\) adalah fungsi-fungsi terdiferensialkan. Buktikan, dengan menggunakan induksi, bahwa
\begin{equation*} (f_1 + f_2 + \cdots + f_n)' = f_1' + f_2' + \cdots + f_n'\text{.} \end{equation*}
🔗
Anda boleh mengasumsikan \((f+g)' = f' + g'\) untuk sembarang fungsi terdiferensialkan \(f\) dan \(g\text{.}\)
🔗
Petunjuk.
Anda boleh mengasumsikan bahwa kasus dasar berlaku. Untuk langkah induksi, kelompokkan semua fungsi kecuali fungsi terakhir menjadi satu jumlah fungsi, lalu terapkan aturan turunan untuk jumlah dua fungsi, kemudian terapkan hipotesis induksi.
🔗
🔗
🔗

24.

Misalkan \(f_1, f_2, \ldots, f_n\) adalah fungsi-fungsi terdiferensialkan. Gunakan induksi matematika untuk membuktikan aturan hasil kali umum:
\begin{equation*} (f_1 f_2 f_3 \cdots f_n)' = f_1' f_2 f_3 \cdots f_n + f_1 f_2' f_3 \cdots f_n + f_1 f_2 f_3' \cdots f_n + \cdots + f_1 f_2 f_3 \cdots f_n'\text{.} \end{equation*}
🔗
Anda boleh mengasumsikan bahwa aturan hasil kali untuk dua fungsi berlaku.
🔗
Petunjuk.
Untuk langkah induksi, berdasarkan aturan hasil kali untuk dua fungsi, kita mengetahui bahwa
\begin{equation*} (f_1f_2f_3 \cdots f_k f_{k+1})' = (f_1f_2f_3\cdots f_k)'f_{k+1} + (f_1f_2f_3\cdots f_k)f_{k+1}'\text{.} \end{equation*}
🔗
Kemudian gunakan hipotesis induksi pada suku pertama, lalu terapkan sifat distributif.
🔗
🔗
🔗

25.

Dalam Latihan , kita telah membuktikan bahwa berikut ini merupakan aturan deduksi yang sah:
🔗
\(P \imp Q\)
\(Q \imp R\)
\(\therefore\) \(P \imp R\)
Sekarang gunakan induksi matematika untuk membuktikan bahwa sebanyak apa pun implikasi semacam ini dapat dirangkai. Dengan kata lain, buktikan untuk setiap \(n \ge 3\) bahwa berikut ini merupakan aturan deduksi yang sah:
🔗
\(P_1 \imp P_2\)
\(P_2 \imp P_3\)
\(\vdots\)
\(P_{n-1} \imp P_n\)
\(\therefore\) \(P_1 \imp P_n\text{.}\)
Petunjuk.
Anda dapat mengasumsikan secara induktif bahwa dari \(n-2\) implikasi pertama, Anda dapat menyimpulkan \(P_1 \imp P_{n-1}\text{.}\) Kemudian Anda dapat menggunakan tabel kebenaran untuk memverifikasi bahwa aturan deduksi yang telah disederhanakan ini sah.
🔗
🔗
🔗
🔗
🔗
SblmTopLnjt
Umpan Balik