3.
Petunjuk.
Pertama-tama, tentukan makna setiap pernyataan. Untuk butir (c), Anda tidak perlu mengasumsikan bahwa semestanya merupakan himpunan tak hingga.
Lampiran A Petunjuk Terpilih
1 Logika dan Pembuktian
1.1 Pernyataan Matematis
Latihan Tambahan
1.2 Implikasi
Latihan Tambahan
4.
Petunjuk.
Tentu terdapat banyak jawaban. Akan membantu jika Anda mengasumsikan bahwa pernyataan tersebut benar dan konversnya tidak benar. Pikirkan maknanya dalam dunia nyata, lalu mulailah menyatakannya dengan berbagai cara. Beberapa gagasan: gunakan bahasa “perlu dan cukup”, gunakan “hanya jika”, pertimbangkan negasi, dan gunakan ungkapan “atau jika tidak”.
1.3 Aturan Logika
Latihan Tambahan
1.
Petunjuk.
Anda mungkin dapat menalar setiap kasus secara langsung, tetapi cobalah membuat tabel kebenaran. Gunakan dua pernyataan: \(P\) menyatakan “kami sepupu” dan \(Q\) menyatakan “kami berdua adalah penipu”.
4.
Petunjuk.
Tuliskan tiga pernyataan menggunakan simbol \(P, Q, R, S\text{.}\) Jika Geoff adalah orang yang selalu berkata benar, ketiga pernyataan tersebut benar. Jika ia pembohong, ketiganya salah. Namun, dalam kedua kasus itu, kita belum mengetahui apakah keempat pernyataan atomik tersebut benar atau salah karena ia tidak mengucapkannya secara tersendiri.
Tabel kebenaran mungkin membantu, meskipun barangkali tidak mutlak diperlukan.
8.
Petunjuk.
-
Akan ada tiga baris yang pernyataannya bernilai salah.
-
Perhatikan tiga baris yang bernilai salah, lalu nyatakan nilai kebenaran \(T\text{,}\) \(S\text{,}\) dan \(P\) pada baris-baris tersebut.
-
Carilah baris tempat \(P\) bernilai benar dan seluruh pernyataan juga bernilai benar.
9.
Petunjuk.
Tuliskan tiga pernyataan, lalu ambil negasi masing-masing (karena ia pembohong). Anda seharusnya menemukan bahwa Tommy makan satu jenis makanan dan minum satu jenis minuman. (\(Q\) menyatakan roti lapis mentimun.)
11.
Petunjuk.
Apa arti konsep-konsep ini jika dinyatakan dalam tabel kebenaran?
14.
Petunjuk.
Cobalah sebuah contoh. Bagaimana jika \(P(x)\) adalah predikat “\(x\) merupakan bilangan prima”? Bagaimana jika predikatnya adalah “Jika \(x\) habis dibagi 4, maka bilangan itu genap”? Tentu saja, contoh tidak cukup untuk membuktikan sesuatu secara umum, tetapi justru itulah inti pertanyaan ini.
15.
Petunjuk.
Mungkin akan membantu jika pernyataan-pernyataan tersebut dinyatakan dengan simbol, lalu aturan-aturan formal digunakan untuk menyederhanakan negasi (yaitu aturan untuk kuantor dan hukum De Morgan). Setelah disederhanakan, untuk pernyataan pertama, misalnya, Anda seharusnya memperoleh \(\forall x(\neg E(x) \wedge \neg O(x))\text{.}\) Kemudian nyatakan kembali hasilnya dalam bahasa Indonesia.
1.4 Pembuktian
Latihan Tambahan
6.
Petunjuk.
Salah satu implikasi dapat dibuktikan secara langsung; implikasi lainnya dapat dibuktikan melalui kontraposisi.
7.
Petunjuk.
Soal ini pada dasarnya meminta Anda memodifikasi pembuktian bahwa \(\sqrt{2}\) merupakan bilangan irasional. Dalam pembuktian tersebut Anda menunjukkan bahwa bilangan-bilangan tertentu genap; di sini Anda akan menunjukkan bahwa bilangan-bilangan tersebut merupakan kelipatan 3.
8.
Petunjuk.
Bagian (a) dapat dibuktikan dengan pembuktian langsung yang relatif mudah. Carilah contoh penyangkal untuk bagian (b).
10.
Petunjuk.
Pembuktian dengan kontradiksi cocok digunakan di sini karena Anda dapat mengasumsikan bahwa \(a\) dan \(b\) keduanya ganjil. Simpulkan bahwa \(c^2\) genap dan karena itu merupakan kelipatan 4 (mengapa? dan mengapa hal tersebut merupakan kontradiksi?).
12.
Petunjuk.
Gunakan metode pembuktian yang berbeda untuk setiap bagian.
14.
Petunjuk.
Perhatikan bahwa jika \(\log(7) = \frac{a}{b}\text{,}\) maka \(7 = 10^\frac{a}{b}\text{.}\) Dapatkah suatu pangkat dari 7 sama dengan suatu pangkat dari 10?
15.
Petunjuk.
Bagaimana jika solusi semacam itu ada? Simpulkan bahwa \(x\) harus ganjil, lalu lanjutkan hingga memperoleh kontradiksi.
16.
Petunjuk.
Buktikan kontraposisinya dengan pembuktian per kasus. Terdapat 4 kasus yang perlu diperhatikan.
17.
Petunjuk.
Pembuktian teman Anda memang membuktikan sesuatu, tetapi apa? Implikasi apa yang mengikuti dari pembuktian tersebut? Apakah hal itu membantu?
19.
Petunjuk.
Perhatikan himpunan banyaknya teman yang dimiliki setiap orang. Jika setiap orang memiliki jumlah teman yang berbeda, himpunan ini harus memuat 20 elemen. Apakah hal itu mungkin? Mengapa tidak?
20.
Petunjuk.
Soal ini terasa seperti penerapan prinsip sarang merpati, meskipun sedikit lebih rumit. Setidaknya, Anda dapat mencoba meniru gaya pembuktian yang digunakan pada prinsip sarang merpati. Bagaimana jarak antarepisode harus diatur agar tidak ada dua dari 60 episode yang posisinya berselisih tepat 4?
1.5 Bukti tentang Struktur Diskret
Latihan Tambahan
1.
Petunjuk.
Untuk membuktikan bahwa \(A \subseteq B\) jika dan hanya jika \(A \cup B = B\text{,}\) Anda perlu membuktikan dua implikasi:
-
Jika \(A \subseteq B\text{,}\) maka \(A \cup B = B\text{.}\)
-
Jika \(A \cup B = B\text{,}\) maka \(A \subseteq B\text{.}\)
Untuk membuktikan bahwa dua himpunan sama, biasanya kita membuktikan bahwa masing-masing merupakan himpunan bagian dari yang lain.
2 Teori Graf
2.1 Masalah dan Definisi
Soal Latihan
5.
Petunjuk.
Ingatlah bahwa \(P_n\) adalah lintasan yang memuat \(n\) sisi dan \(n+1\) simpul.
Latihan Tambahan
3.
Petunjuk.
Kedua situasi tersebut mungkin terjadi. Carilah beberapa contohnya.
6.
Petunjuk.
Bagian graf bipartit sedikit lebih rumit. Anda tentu memerlukan graf bipartit lengkap, tetapi grafnya dapat berupa \(K_{5,5}\text{,}\) mungkin \(K_{1,9}\text{,}\) atau …
7.
Petunjuk.
Graf pertama bipartit, sebagaimana terlihat dengan memberi label berikut.
Dua dari tiga graf lainnya juga bipartit.
8.
Petunjuk.
\(C_4\) bipartit, sedangkan \(C_5\) tidak. Bagaimana dengan semua nilai \(n\) lainnya?
11.
Petunjuk.
Anda seharusnya dapat menyimpulkan semuanya langsung dari definisi. Namun, mungkin akan membantu jika diketahui bahwa \(N\) melambangkan lingkungan.
12.
Petunjuk.
Pastikan bahwa sisi-sisinya tidak “berarah.” Dalam graf, jika \(a\) bertetangga dengan \(b\text{,}\) maka \(b\) bertetangga dengan \(a\text{.}\) Dalam bahasa relasi, kita mengatakan bahwa relasi sisi bersifat simetris.
13.
Petunjuk.
Anda mungkin perlu menjawab pertanyaan-pertanyaan tersebut untuk beberapa nilai khusus \(n\) agar memahami polanya, tetapi jawaban akhir harus dinyatakan dalam \(n\text{.}\)
14.
Petunjuk.
Cobalah contoh kecil terlebih dahulu: setiap graf dengan 8 simpul pasti memiliki dua simpul dengan derajat yang sama. Jika tidak demikian, seperti apakah barisan derajatnya?
15.
Petunjuk.
Gunakan lema jabat tangan 2.1.8. Apa yang akan terjadi jika semua simpul berderajat 2?
2.2 Pohon
Latihan Tambahan
3.
Petunjuk.
Berhati-hatilah: graf-graf tersebut mungkin tidak terhubung.
4.
Petunjuk.
Cobalah gunakan Latihan 2.
5.
Petunjuk.
Cobalah bukti dengan kontradiksi dan tinjau suatu pohon merentang dari graf tersebut.
7.
Petunjuk.
Untuk bagian (b), mencoba beberapa contoh sederhana seharusnya membantu Anda menemukan rumusnya. Setelah itu, Anda hanya perlu membuktikan bahwa rumus tersebut benar.
8.
Petunjuk.
Dengan mencermati bukti Proposisi 2.2.2, Anda akan memperoleh hampir semua hal yang diperlukan. Namun, pastikan Anda hanya memberikan bagian-bagian yang relevan dan berhati-hatilah agar tidak menggunakan bukti dengan kontradiksi.
9.
Petunjuk.
Minimalitas di sini harus dinyatakan dalam banyaknya simpul. Jika Anda memiliki contoh penyangkal minimal dan menghapus suatu simpul daun, graf yang dihasilkan akan menjadi pohon yang lebih kecil, sehingga...
10.
Petunjuk.
Jika \(e\) merupakan akar, maka \(b\) akan memiliki tiga anak (\(a\text{,}\) \(c\text{,}\) dan \(d\)); ketiganya merupakan saudara kandung dan memiliki \(b\) sebagai induk. \(a\) tidak akan memiliki anak.
Secara umum, bagaimana Anda dapat menentukan banyaknya anak yang dimiliki suatu simpul jika simpul tersebut bukan akar?
14.
Petunjuk.
Terdapat contoh dengan 7 sisi.
15.
Petunjuk.
Latihan sebelumnya akan membantu.
16.
Petunjuk.
Perhatikan bahwa jika sisi semacam itu dihapus, graf akan menjadi tidak terhubung. Graf yang memiliki sisi seperti ini disebut graf terhubung-1.
2.3 Graf Planar
Latihan Tambahan
3.
Petunjuk.
Apa yang dinyatakan oleh rumus Euler?
5.
Petunjuk.
Anda dapat menggunakan lema jabat tangan untuk menyatakan banyaknya sisi dalam \(v\text{,}\) yaitu banyaknya simpul.
11.
Petunjuk.
Berapa panjang siklus terpendeknya? (Besaran ini biasanya disebut panjang siklus terpendek (girth) suatu graf.)
14.
Petunjuk.
Panjang siklus terpendek (girth) graf tersebut adalah 4.
15.
Petunjuk.
Apa yang terjadi pada panjang siklus terpendek (girth)? Hati-hati: banyaknya sisi juga berbeda. Sebaiknya periksa rumus Euler.
2.4 Jejak dan Sirkuit Euler
Latihan Tambahan
7.
Petunjuk.
Soal ini lebih sulit daripada tiga soal sebelumnya. Pikirkan pada “bagian” graf yang mana lintasan Hamilton harus berada pada setiap langkah berselang-seling.
9.
Petunjuk.
Jika nama para mahasiswa dibaca menurut urutan tempat duduk, setiap nama harus dibaca tepat satu kali, dan nama terakhir harus merupakan mahasiswa yang berteman dengan mahasiswa pertama. Siklus jenis apakah ini?
10.
Petunjuk.
Gambarlah graf dengan 6 simpul dan 8 sisi. Jenis jalan apakah yang sesuai?
2.5 Pewarnaan
Latihan Tambahan
6.
6.c
Petunjuk.
Apakah pada akhirnya Anda akan mewarnai setiap simpul dengan mengikuti prosedur tersebut? Mungkinkah ada simpul yang tidak dapat Anda warnai sesuai prosedur itu?
7.
7.a
Petunjuk.
Representasikan tim sebagai simpul dan pertandingan sebagai sisi. Manakah yang lebih tepat untuk diwarnai?
10.
Petunjuk.
Bilangan kromatiknya adalah 4. Sekarang, buktikanlah!
Perhatikan bahwa di sini Anda tidak dapat menggunakan teorema empat warna, teorema Brooks, ataupun bilangan klik. Faktanya, graf ini, yang disebut graf Grötzsch, merupakan graf terkecil dengan bilangan kromatik 4 yang tidak memuat segitiga.
13.
Petunjuk.
Anda dapat mewarnai \(K_5\) sedemikian rupa sehingga setiap simpul bersisian dengan tepat dua sisi biru dan dua sisi merah. Namun, terdapat sebuah graf dengan hanya 5 sisi yang pasti menghasilkan suatu simpul yang bersisian dengan tiga sisi berwarna sama, apa pun pewarnaan sisi-sisinya. Graf apakah itu, dan bagaimana Anda dapat menggeneralisasikannya?
14.
Petunjuk.
Latihan sebelumnya berguna sebagai titik awal.
2.8 Ringkasan Bab
Tinjauan Bab
2.8.23.
Petunjuk.
Anda dapat membagi bukti menjadi dua bagian. Pertama, buktikan dengan induksi bahwa siklus \(C_n\) memenuhi \(v=e\text{.}\) Kemudian, tinjau apa yang terjadi jika graf tersebut tidak hanya terdiri atas siklus itu.
3 Pencacahan
3.2 Menggabungkan Hasil
Soal Latihan
9.
Petunjuk.
Pisahkan pertanyaan ini menjadi 3 kasus.
Latihan Tambahan
2.
Petunjuk.
Sebagai contoh yang lebih sederhana, terdapat 4 pembagi dari \(6 = 2\cdot 3\text{.}\) Keempatnya adalah \(1 = 2^0\cdot 3^0\text{,}\) \(2 = 2^1\cdot 3^0\text{,}\) \(3 = 2^0\cdot 3^1\text{,}\) dan \(6 = 2^1\cdot 3^1\text{.}\)
3.3 Hasil yang Tidak Saling Lepas
Soal Latihan
6.
Petunjuk.
Untuk menentukan banyak bilangan yang habis dibagi 8 dan 9, misalnya, hitung \(790/(8\cdot9)\) lalu bulatkan ke bawah.
Latihan Tambahan
1.
Petunjuk.
Untuk bagian (a), Anda dapat menggunakan rumus PIE, tetapi untuk bagian (b), menggambar diagram Venn mungkin lebih membantu.
2.
Petunjuk.
Anda dapat mempertimbangkan beberapa kasus. Sebagai contoh, sembarang bilangan berbentuk GANJIL-GANJIL-GENAP akan memiliki jumlah digit yang genap. Sebagai alternatif, ada berapa banyak bilangan tiga digit dengan jumlah digit genap jika dua digit pertamanya adalah 54? Bagaimana jika dua digit pertamanya adalah 19?
3.4 Kombinasi dan Permutasi
Latihan Tambahan
1.
Petunjuk.
Jika Anda memilih sembarang tiga titik, Anda dapat membentuk sebuah segitiga, kecuali jika ketiga titik itu semuanya berada pada sumbu \(x\) atau sumbu \(y\text{.}\) Ada pula cara lain untuk memulai penyelesaian ini, dan setiap metode yang benar seharusnya memberikan jawaban yang sama.
3.5 Menghitung Multihimpunan
Soal Latihan
6.
Petunjuk.
Peluangnya adalah 1 dibagi banyaknya kombinasi berbeda dari 11 keping uang logam yang mungkin dimiliki teman Anda.
Latihan Tambahan
3.
3.b
Petunjuk.
Hal ini sebenarnya memerlukan pembuktian empat fakta: setiap multihimpunan berkorespondensi dengan sedikitnya satu diagram, dan setiap diagram berkorespondensi dengan sedikitnya satu multihimpunan; lalu setiap multihimpunan berkorespondensi dengan paling banyak satu diagram, dan setiap diagram berkorespondensi dengan paling banyak satu multihimpunan. Dengan kata lain, kita harus membuktikan bahwa fungsi tersebut terdefinisi dengan baik, injektif, dan surjektif.
3.6 Pembuktian Kombinatorial
Latihan Tambahan
3.
Petunjuk.
Akan terdapat 185 segitiga. Namun, untuk menemukannya …
-
Berapa banyak simpul segitiga yang dapat berada pada sumbu horizontal?
-
Apakah sembarang tiga titik dapat menjadi simpul-simpulnya?
4.
Petunjuk.
Jawabannya adalah 120.
6.
Petunjuk.
Cobalah Latihan 5.
7.
Petunjuk.
Bagaimana jika Anda menginginkan sepasang pengiring pengantin utama bersama?
8.
Petunjuk.
Untuk pembuktian kombinatorial: bagaimana jika Anda belum mengetahui berapa banyak pengiring pengantin yang akan dipilih?
9.
Petunjuk.
Hitung jabat tangan.
13.
Petunjuk.
Soal ini mungkin mengingatkan Anda pada Contoh 3.6.6
14.
Petunjuk.
Untuk lintasan kisi, pikirkan jenis lintasan yang dicacah oleh \(2^n\text{.}\) Tidak semua lintasan akan berakhir pada titik yang sama, tetapi Anda dapat mendeskripsikan himpunan titik akhirnya sebagai sebuah garis.
16.
Petunjuk.
Berapa banyak sisi yang dimiliki \(K_n\text{?}\) Salah satu dari kedua graf tidak akan terhubung (kecuali \(j=1\) ).
3.7 Penerapan pada Peluang
Soal Latihan
7.
Petunjuk.
Anda dapat mendaftarkan semua cara memperoleh jumlah 6 atau menggunakan metode batang dan batu.
Latihan Tambahan
4.
Petunjuk.
Gunakan peluang komplemen. Jangan terkejut jika jawaban Anda lebih besar daripada yang diperkirakan.
3.9 Ringkasan Bab
Tinjauan Bab
3.9.16.
Petunjuk.
Gunakan metode batang dan batu.
4 Barisan
4.1 Mendeskripsikan Barisan
Soal Latihan
4.
Petunjuk.
Cobalah menambah atau mengurangi setiap suku dengan bilangan kecil yang sama untuk melihat apakah Anda mengenali barisan tersebut.
5.
Petunjuk.
Cobalah menambah, mengurangi, atau membagi setiap suku dengan suatu konstanta agar pola barisan lebih mudah dikenali.
Untuk bagian (d), cobalah menyatakan barisan sebagai jumlah dua barisan yang sudah dikenal.
Latihan Tambahan
8.
Petunjuk.
Tuliskan barisannya, dugalah rumus tertutupnya, lalu verifikasi bahwa dugaan Anda benar.
9.
Petunjuk.
Tuliskan barisannya, dugalah definisi rekursifnya, lalu verifikasi bahwa rumus tertutup tersebut merupakan solusi definisi rekursif itu.
12.
Petunjuk.
Cobalah sebuah contoh: ketika garis keempat digambar, garis tersebut memotong tiga garis lain sehingga terbagi menjadi empat ruas, dua di antaranya tak terbatas. Setiap ruas membagi satu daerah yang sudah ada menjadi dua.
13.
Petunjuk.
Pertimbangkan tiga kasus: angka terakhir adalah 0, 1, atau 2. Dua kasus mudah dicacah, tetapi string yang berakhir dengan 0 tidak boleh didahului oleh 2, sehingga kasus ini memerlukan sedikit usaha tambahan.
15.
Petunjuk.
Berpikirlah secara rekursif, seperti yang Anda lakukan pada segitiga Pascal.
16.
Petunjuk.
Hanya ada satu cara mengubin papan berukuran \(2 \times 1\) dan dua cara mengubin papan berukuran \(2\times 2\) (domino dapat diorientasikan dengan dua cara). Secara umum, pertimbangkan dua kemungkinan orientasi domino yang menutupi sudut kiri atas.
4.2 Laju Pertumbuhan
Latihan Tambahan
5.
Petunjuk.
Kita dapat menuliskan relasi rekurensi sebagai \(\frac{a_n}{a_{n-1}} = r\text{.}\) Apa yang terjadi ketika Anda mengalikan semua versi relasi rekurensi ini (untuk nilai \(n\) yang berbeda-beda)?
6. Peneleskopan untuk Menentukan Jumlah.
Petunjuk.
Dengan menggunakan fakta bahwa \(T_n = \frac{n(n+1)}{2}\text{,}\) setiap suku dalam barisan adalah \(\frac{2}{n(n+1)}\text{.}\)
Apa hasil pengurangan pecahan berikut: \(\frac{2}{3}- \frac{2}{4}\text{,}\) atau \(\frac{2}{4}-\frac{2}{5}\text{?}\) Apa yang terjadi secara umum?
4.4 Barisan Eksponensial
Soal Latihan
3.
Petunjuk.
Gunakan metode teleskopik atau iterasi.
4.5 Pembuktian dengan Induksi
Latihan Tambahan
9.
Petunjuk.
Tidak mungkin mencetak tepat 11 poin. Dapatkah Anda membuktikan bahwa Anda dapat mencetak \(n\) poin untuk setiap \(n \ge 12\text{?}\)
11.
Petunjuk.
Mulailah dengan segi-\((k+1)\text{,}\) lalu bagilah menjadi segi-\(k\) dan sebuah segitiga.
15.
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{?}\)
17.
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.
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.
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.
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.
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.
23.
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.
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.
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.
4.6 Induksi Kuat
Latihan Tambahan
1.
Petunjuk.
Jika tiga kasus dasar telah dibuktikan, dapatkah Anda selalu memastikan bahwa tiga poin lagi dapat diperoleh?
2.
Petunjuk.
Mulailah dengan segi-\((k+1)\text{,}\) lalu bagilah menjadi dua poligon yang lebih kecil.
4.
Petunjuk.
Seperti pada soal sebelumnya, dalam langkah induksi kita ingin mengurangkan sesuatu dari \(n\text{.}\) Pada soal itu kita mengurangkan pangkat terbesar dari 2 yang kurang dari \(n\text{.}\) Jadi, apa yang sebaiknya Anda kurangkan di sini?
Perhatikan bahwa Anda masih perlu memastikan bahwa jumlah yang diperoleh dari hipotesis induksi, bersama dengan bilangan yang Anda kurangkan, merupakan jumlah bilangan-bilangan Fibonacci yang berbeda. Bahkan, Anda dapat membuktikan bahwa tidak ada dua bilangan Fibonacci dalam jumlah tersebut yang berurutan!
6.
Petunjuk.
Anda perlu menggunakan induksi kuat. Untuk langkah induksi, coba kalikan \(\left (x^k + \frac{1}{x^{k}}\right)\left(x+\frac{1}{x}\right)\text{,}\) lalu kelompokkan suku-suku yang bersama-sama membentuk bilangan bulat.
8.
Petunjuk.
Anda akan memerlukan tiga kasus dasar. Ini petunjuk yang sangat baik karena menyiratkan bahwa untuk membuktikan \(P(n)\) benar, Anda perlu menggunakan fakta bahwa \(P(n-3)\) benar. Jadi, Anda perlu menemukan cara untuk menambah banyaknya persegi sebesar 3.
4.7 Ringkasan Bab
Tinjauan Bab
4.7.14.
Petunjuk.
-
\((n+1)^{n+1} > (n+1) \cdot n^{n}\text{.}\)
-
Pembuktian ini seharusnya serupa dengan pembuktian jumlah lainnya. Langkah terakhir bermuara pada penjumlahan pecahan.
-
Tuliskan \(4^{k+1} - 1 = 4\cdot 4^k - 4 + 3\text{.}\)
-
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.
4.7.15.
Petunjuk.
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{.}\)
4.7.16.
Petunjuk.
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.
5 Meninjau Kembali Struktur Diskret
5.1 Himpunan
Latihan
7.
Petunjuk.
Anda dapat menuliskan semuanya. Jangan lupakan \(A\) dan \(B\text{,}\) yang juga merupakan kemungkinan bagi \(C\text{.}\)
14.
Petunjuk.
Mungkin akan membantu jika Anda terlebih dahulu memikirkan gabungan \(A_2
\cup A_3\text{.}\) Kemudian pikirkan bilangan mana yang tidak berada dalam gabungan tersebut. Apa yang akan terjadi ketika Anda juga menyertakan \(A_5\text{?}\)
17.
Petunjuk.
Kita mencari sebuah himpunan yang memuat 16 himpunan.
18.
Petunjuk.
Tuliskan himpunan-himpunan tersebut, atau setidaknya mulailah menuliskannya lalu carilah sebuah pola.
29.
Petunjuk.
Sekilas tampaknya Anda dapat mendefinisikan himpunan \(A\) dengan cara ini. Namun, pertimbangkan dua nilai yang mungkin untuk \(\card{A}\text{.}\)
5.2 Fungsi
Latihan
2.
Petunjuk.
Karena domain dan kodomain berukuran sama, mungkinkah suatu fungsi bersifat injektif tetapi tidak surjektif, atau surjektif tetapi tidak injektif?
20.
Petunjuk.
Cobalah beberapa contoh. Bagaimana jika \(f = \twoline{1\amp 2 \amp 3}{a \amp a \amp b}\) dan \(g = \twoline{a\amp b \amp c}{5
\amp 6 \amp 7}\text{?}\)
25.
Petunjuk.
Untuk memperoleh relasi rekurensinya, perhatikan berapa banyak jabat tangan baru yang terjadi ketika orang ke-\(n+1\) memasuki ruangan.
29.
Petunjuk.
Salah satu kesamaan ini tidak selalu benar. Cobalah beberapa contoh!
6 Topik Tambahan
6.1 Fungsi Pembangkit
Latihan
10.
Petunjuk.
Anda perlu “mengalikan” kedua barisan tersebut.
6.2 Pengantar Teori Bilangan
Latihan
13.
Petunjuk.
Mula-mula, reduksikan setiap bilangan modulo 9; ini dapat dilakukan dengan menjumlahkan digit-digit bilangan tersebut.
18.
Petunjuk.
Selesaikan persamaan Diofantin \(13x + 20 y = 2\) (mengapa?). Kemudian tentukan nilai \(k\) (parameter dalam solusi) yang optimal.