Induksi Kuat

Subbab 4.6 Induksi Kuat

Tujuan Pembelajaran

Setelah menyelesaikan bagian ini, Anda diharapkan mampu melakukan hal-hal berikut.

Menjelaskan perbedaan antara pembuktian dengan induksi dan pembuktian dengan induksi kuat.
🔗

🔗
Menggunakan induksi kuat untuk membuktikan pernyataan.
🔗

🔗

Subbagian Pratinjau Bagian

Selidiki!

Mulailah dengan selembar kertas berbentuk persegi. Anda ingin memotong persegi ini menjadi persegi-persegi yang lebih kecil tanpa menyisakan bagian terbuang (setiap potongan kertas yang dihasilkan harus berbentuk persegi). Jelas bahwa persegi tersebut dapat dipotong menjadi 4 persegi. Anda juga dapat memotongnya menjadi 9 persegi. Ternyata persegi tersebut dapat dipotong menjadi 7 persegi (meskipun ukurannya tidak semuanya sama). Jumlah persegi berapa saja yang mungkin dihasilkan?

🔗

Terkadang, untuk membuktikan bahwa $P(k+1)$ benar, akan membantu jika kita mengetahui bahwa $P(k)$ dan $P(k-1)$ dan $P(k-2)$ semuanya benar. Hal ini tentu terjadi ketika kita membuktikan sesuatu tentang relasi rekurensi yang dinyatakan sebagai kombinasi dua suku sebelumnya.

🔗

Contoh 4.6.1.

Buktikan bahwa $2^n$ merupakan solusi bagi relasi rekurensi $a_n = 5a_{n-1} - 6a_{n-2}$ dengan syarat awal $a_0 = 1$ dan $a_1 = 2\text{.}$

🔗

Penyelesaian.

Bukti.

Misalkan $P(n)$ adalah pernyataan, “$a_n = 2^n\text{.}$” Kita akan menunjukkan bahwa pernyataan ini benar untuk semua $n \ge 0\text{.}$

🔗

Kasus dasar: $a_0 = 2^0 = 1$ dan $a_1 = 2^1 = 2$ keduanya sesuai dengan syarat awal.

🔗

Langkah induksi: Misalkan $k \ge 1$ sembarang. Asumsikan $P(k)$ dan $P(k-1)$ keduanya benar. Artinya, asumsikan $a_k = 2^k$ dan $a_{k-1} = 2^{k-1}\text{.}$ Kita akan menunjukkan bahwa $P(k+1)$ benar. Perhatikan $a_{k+1}\text{.}$ Kita memiliki

\begin{align*} a_{k+1} = \amp 5a_k - 6a_{k-1}\\ = \amp 5\cdot 2^k - 6\cdot 2^{k-1}\\ = \amp 10 \cdot 2^{k-1} - 6 \cdot 2^{k-1}\\ = \amp 4\cdot 2^{k-1}\\ = \amp 2^{k+1}\text{.} \end{align*}

Oleh karena itu, berdasarkan prinsip induksi matematika, $P(n)$ benar untuk semua $n \ge 0\text{.}$

🔗

Sebenarnya, hampir saja kita menerapkan prinsip induksi matematika. Apakah yang kita lakukan sah?

🔗

Ada pula kalanya kita ingin meninjau lebih jauh ke belakang dan menggunakan asumsi bahwa $P(j)$ benar untuk $j$ yang jauh lebih kecil daripada $k+1\text{.}$ Inilah gagasan di balik induksi kuat dan topik bagian singkat ini.

🔗

Lembar Kerja Kegiatan Pratinjau

1.

Perhatikan teka-teki berikut:

🔗

Anda memiliki sebatang cokelat berbentuk persegi panjang yang tersusun atas $n$ petak cokelat identik. Anda dapat mematahkan batang tersebut sepanjang garis di antara sembarang baris atau kolom. Berapa kali Anda harus mematahkan batang itu agar terurai menjadi $n$ petak cokelat tunggal?

🔗

Pada awalnya, pertanyaan ini mungkin tampak mustahil dijawab. Mungkin yang dimaksud adalah jumlah paling sedikit pematahan yang diperlukan. Mari kita selidiki.

🔗

(a)

Misalkan Anda memulai dengan batang berukuran $1\times 3\text{.}$ Berapa kali Anda perlu mematahkannya agar terurai menjadi petak-petak tunggal?

🔗

(b)

Jika Anda memiliki batang berukuran $1\times 4\text{,}$ berapa kali pematahan yang diperlukan?

🔗

Jika Anda memiliki 4 petak yang tersusun sebagai persegi $2\times 2\text{,}$ pematahan pertama akan membagi cokelat menjadi dua batang berukuran $1 \times 2\text{.}$ Kemudian masing-masing batang memerlukan kali pematahan lagi, sehingga diperlukan total kali pematahan untuk menguraikan persegi $2\times 2$ menjadi petak-petak tunggal.

🔗

(c)

Batang yang terdiri atas $6$ petak dapat berukuran $1 \times 6\text{,}$ yang memerlukan kali pematahan, atau berukuran $2 \times 3\text{.}$

🔗

Sekarang ada dua cara untuk melanjutkan.

Patahkan batang menjadi dua batang berukuran $1 \times 3\text{.}$ Masing-masing memerlukan kali pematahan lagi, sehingga semuanya memerlukan kali pematahan.
🔗

🔗
Patahkan batang menjadi satu batang berukuran $1\times 2$ dan satu batang berukuran $2 \times 2\text{.}$ Batang $1 \times 2$ memerlukan kali pematahan lagi dan batang $2 \times 2$ memerlukan kali pematahan lagi, sehingga semuanya memerlukan kali pematahan.
🔗

🔗

🔗

(d)

Berdasarkan data di atas, apa dugaan kita mengenai jumlah pematahan yang diperlukan untuk menguraikan batang yang terdiri atas $n$ petak menjadi petak-petak tunggal, jika dinyatakan dalam $n\text{?}$

🔗

Diperlukan kali pematahan untuk menguraikan batang yang terdiri atas $n$ petak menjadi petak-petak tunggal.

🔗

(e)

Apakah kita memercayai dugaan ini? Misalkan satu pematahan membagi batang menjadi dua batang yang lebih kecil, masing-masing terdiri atas $a$ dan $b$ petak. Jika dugaan tersebut benar, berapa kali pematahan lagi yang diperlukan untuk menguraikan batang berukuran $a\text{?}$

🔗

Berapa kali pematahan lagi yang diperlukan untuk menguraikan batang berukuran $b\text{?}$

🔗

Dengan menyertakan pematahan pertama, berapa jumlah seluruh pematahan tersebut jika dinyatakan dalam $a$ dan $b\text{?}$

🔗

Namun, berapakah $a+b\text{?}$ Kita memperoleh $a$ dan $b$ dengan membagi $n$ petak menjadi dua bagian, sehingga $a+b =$. Jadi, jumlah seluruh pematahan adalah .

🔗

Subbagian Bagi dan Taklukkan

Bayangkan definisi rekursif sebagai petunjuk untuk membangun tangga. Anda dapat membangun tangga setinggi yang diinginkan karena Anda memiliki petunjuk untuk membuat anak tangga berikutnya, asalkan Anda sedang berdiri di anak tangga sebelumnya.

🔗

Induksi adalah teknik pembuktian yang bersesuaian. Untuk membuktikan bahwa Anda dapat menaiki tangga setinggi yang diinginkan, Anda membuktikan bahwa Anda dapat naik ke anak tangga pertama (kasus dasar), lalu membuktikan bahwa dari sembarang anak tangga Anda dapat mencapai anak tangga berikutnya (langkah induksi).

🔗

Lebih khusus lagi, misalkan Anda mencoba membuktikan bahwa Anda dapat mencapai anak tangga ke-4. Anda telah berhasil membuktikan bahwa Anda dapat mencapai anak tangga ke-1 dan bahwa dari sembarang anak tangga Anda dapat mencapai anak tangga berikutnya. Jadi, Anda dapat mencapai anak tangga ke-1, lalu dari anak tangga ke-1 mencapai anak tangga ke-2. Dari anak tangga ke-2 Anda dapat mencapai anak tangga ke-3, dan dari anak tangga ke-3 mencapai anak tangga ke-4. Oleh karena itu, Anda dapat mencapai anak tangga ke-4.

🔗

Namun, perhatikan bahwa sepanjang proses itu Anda mengetahui bahwa Anda telah melewati anak tangga ke-1 sampai ke-3. Dengan demikian, kita dapat saja mengasumsikan bahwa kita telah melewati semua anak tangga di bawah anak tangga berikutnya yang hendak dicapai. Inilah gagasan di balik induksi kuat.

🔗

Metafora tangga yang lebih baik untuk induksi kuat adalah membayangkan tangga-tangga sebagai benda yang dapat ditumpuk. Kita ingin menunjukkan bahwa 20 anak tangga dapat dinaiki. Mari kita membaginya menjadi dua tangga yang lebih kecil, misalnya tangga dengan 12 anak tangga dan tangga dengan 8 anak tangga. Kita dapat mengasumsikan bahwa kedua tangga ini dapat dinaiki karena 20 adalah ukuran terkecil yang belum kita yakini dapat dinaiki. Jika kedua tangga itu disatukan, kita memperoleh $12+8 = 20$ anak tangga.

🔗

Sebaiknya kita turun dari metafora yang goyah ini sebelum terluka. Mari kita lihat definisi formal induksi kuat.

🔗

Struktur Pembuktian dengan Induksi Kuat.

Mulailah dengan menyatakan apa yang ingin kita buktikan: “Misalkan $P(n)$ adalah pernyataan….” Kemudian buktikan dua fakta:

Kasus dasar: Buktikan bahwa $P(0)$ benar. (Mungkin Anda juga perlu membuktikan kasus dasar lain yang diperlukan.)
🔗

🔗
Langkah induksi: Asumsikan $P(j)$ benar untuk semua $j \le k\text{.}$ Buktikan bahwa $P(k+1)$ benar.
🔗

🔗

Simpulkan, “Oleh karena itu, berdasarkan induksi kuat, $P(n)$ benar untuk semua $n \ge 0\text{.}$”

🔗

Tentu saja, jika diperlukan, 0 boleh diganti dengan kasus dasar yang lebih besar.

Secara teknis, induksi kuat tidak mengharuskan Anda membuktikan kasus dasar secara terpisah. Hal ini karena ketika membuktikan langkah induksi, Anda harus menunjukkan bahwa $P(0)$ benar dengan mengasumsikan bahwa $P(k)$ benar untuk semua $k \lt 0\text{.}$ Namun, asumsi ini tidak membantu, sehingga Anda tetap harus membuktikan $P(0)\text{.}$ Untuk amannya, kita akan selalu mencantumkan kasus dasar secara terpisah.

🔗

Untuk menggambarkan induksi kuat, mari kita kembali ke masalah batang cokelat.

🔗

Proposisi 4.6.2.

Untuk batang cokelat persegi panjang yang terdiri atas $n$ petak, selalu diperlukan $n-1$ kali pematahan untuk menguraikan batang tersebut menjadi petak-petak tunggal.

🔗

Bukti.

Misalkan $P(n)$ adalah pernyataan, “Diperlukan $n-1$ kali pematahan untuk menguraikan batang cokelat yang terdiri atas $n$ petak menjadi petak-petak tunggal.”

🔗

Kasus dasar: Perhatikan $P(2)\text{.}$ Petak-petak tersebut harus tersusun sebagai persegi panjang $1\times 2\text{,}$ dan kita memerlukan $2-1 = 1$ kali pematahan untuk menguraikannya menjadi petak-petak tunggal.

🔗

Langkah induksi: Tetapkan $k\ge 2$ sembarang dan asumsikan $P(j)$ benar untuk semua $j \le k\text{.}$ Perhatikan batang cokelat persegi panjang yang terdiri atas $(k+1)$ petak. Patahkan batang itu sekali sepanjang sembarang garis antarbaris atau antarkolom. Hasilnya adalah dua batang cokelat, misalnya masing-masing berukuran $a$ dan $b\text{.}$ Artinya, kita memiliki batang cokelat persegi panjang yang terdiri atas $a$ petak, batang cokelat persegi panjang yang terdiri atas $b$ petak, dan $a+b = k+1\text{.}$

🔗

Kita juga mengetahui bahwa $a \le k$ dan $b \le k\text{,}$ sehingga berdasarkan hipotesis induksi, $P(a)$ dan $P(b)$ benar. Untuk menguraikan batang yang terdiri atas $a$ petak menjadi petak-petak tunggal diperlukan $a-1$ kali pematahan; untuk menguraikan batang yang terdiri atas $b$ petak menjadi petak-petak tunggal diperlukan $b-1$ kali pematahan. Dengan melakukan ini, batang semula terurai menjadi petak-petak tunggal. Secara keseluruhan, kita melakukan pematahan pertama, ditambah $a-1$ dan $b-1$ kali pematahan, sehingga jumlahnya

\begin{equation*} 1+a-1+b-1 = a+b-1 = k+1 - 1 = k \end{equation*}

kali pematahan. Jadi, $P(k+1)$ benar.

🔗

Oleh karena itu, berdasarkan induksi kuat, $P(n)$ benar untuk semua $n \ge 2\text{.}$

🔗

Berikut ini contoh yang lebih relevan secara matematis:

🔗

Contoh 4.6.3.

Buktikan bahwa setiap bilangan asli yang lebih besar dari 1 merupakan bilangan prima atau dapat ditulis sebagai hasil kali bilangan-bilangan prima.

🔗

Penyelesaian.

Pertama, gagasannya: Jika kita mengambil suatu bilangan $n\text{,}$ mungkin bilangan itu prima. Jika demikian, kita selesai. Jika tidak, bilangan itu komposit, sehingga merupakan hasil kali dua bilangan yang lebih kecil. Masing-masing faktor ini lebih kecil daripada $n$ (tetapi setidaknya 2), sehingga kita dapat mengulangi argumen tersebut untuk kedua bilangan itu. Kita telah mereduksi masalah menjadi kasus yang lebih kecil.

🔗

Sekarang pembuktian formalnya:

🔗

Bukti.

Misalkan $P(n)$ adalah pernyataan, “$n$ merupakan bilangan prima atau dapat ditulis sebagai hasil kali bilangan-bilangan prima.” Kita akan membuktikan bahwa $P(n)$ benar untuk semua $n \ge 2\text{.}$

🔗

Kasus dasar: $P(2)$ benar karena $2$ memang bilangan prima.

🔗

Langkah induksi: Asumsikan $P(j)$ benar untuk semua $j \le k\text{.}$ Kita ingin menunjukkan bahwa $P(k+1)$ benar. Artinya, kita ingin menunjukkan bahwa $k+1$ merupakan bilangan prima atau merupakan hasil kali bilangan-bilangan prima. Jika $k+1$ prima, kita selesai. Jika tidak, $k+1$ memiliki lebih dari 2 pembagi, sehingga kita dapat menulis $k+1 = m_1 \cdot m_2\text{,}$ dengan $m_1$ dan $m_2$ lebih kecil daripada $k+1$ (dan lebih besar dari 1). Berdasarkan hipotesis induksi, $m_1$ dan $m_2$ masing-masing merupakan bilangan prima atau dapat ditulis sebagai hasil kali bilangan-bilangan prima. Dalam kedua hal tersebut, kita memperoleh bahwa $m_1\cdot m_2 = k+1$ dapat ditulis sebagai hasil kali bilangan-bilangan prima.

🔗

Jadi, berdasarkan induksi kuat, $P(n)$ benar untuk semua $n \ge 2\text{.}$

🔗

Pilihan antara induksi biasa dan induksi kuat bergantung pada pernyataan yang ingin Anda buktikan. Agar aman, Anda selalu dapat menggunakan induksi kuat. Metode ini memang lebih kuat, sehingga dapat melakukan semua yang dapat dilakukan oleh induksi “lemah”. Meskipun demikian, induksi biasa sering kali lebih mudah digunakan karena hipotesis induksi hanya dapat digunakan di satu tempat. Selain itu, ada nilai keanggunan dalam pembuktian. Jika suatu pernyataan dapat dibuktikan dengan alat yang lebih sederhana, sebaiknya kita melakukannya.

🔗

Pertanyaan Bacaan Pertanyaan Bacaan

1.

Benar atau salah: Untuk membuktikan langkah induksi dalam pembuktian dengan induksi kuat, Anda harus mengasumsikan bahwa $P(k+1)$ benar dan membuktikan bahwa $P(j)$ benar untuk semua $j \le k\text{.}$

🔗

True.
Ini terbalik. Anda tetap membuktikan kasus berikutnya; bedanya, Anda boleh mengasumsikan semua kasus sebelumnya (bukan hanya satu kasus tepat sebelumnya).
False.
Ini terbalik. Anda tetap membuktikan kasus berikutnya; bedanya, Anda boleh mengasumsikan semua kasus sebelumnya (bukan hanya satu kasus tepat sebelumnya).

🔗

2.

Manakah di antara pernyataan berikut tentang hubungan antara pembuktian dengan induksi dan pembuktian dengan induksi kuat yang benar?

🔗

Setiap pembuktian dengan induksi dapat ditulis sebagai pembuktian dengan induksi kuat.
🔗
Setiap pembuktian dengan induksi kuat dapat ditulis sebagai pembuktian dengan induksi.
🔗
Induksi kuat “lebih kuat” karena kasus dasarnya lebih kuat.
🔗
Induksi kuat “lebih kuat” karena hipotesis induksinya lebih kuat.
🔗

🔗

3.

Apa yang ingin Anda tanyakan? Tuliskan setidaknya satu pertanyaan tentang isi bagian ini yang mungkin membuat Anda atau teman sekelas penasaran setelah membaca bagian ini.

🔗

Latihan Soal Latihan

1.

Misalkan Anda sedang mencoba membuktikan dengan induksi kuat bahwa suatu pernyataan $P(n)$ benar untuk semua $n \ge 0\text{.}$ Apa yang akan Anda coba buktikan pada langkah induksi dalam pembuktian tersebut? (Pilih semua yang berlaku.)

🔗

Bahwa dengan mengasumsikan $P(j)$ benar untuk semua $j \le k\text{,}$ untuk suatu $k \ge 0$ sembarang, kita dapat membuktikan bahwa $P(k+1)$ benar.
🔗
Bahwa $(P(0) \wedge P(1) \wedge \cdots \wedge 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(j)$ benar untuk semua $j \le k\text{.}$
🔗
Bahwa $P(k+1)$ mengimplikasikan $P(j)$ untuk semua $j \le k\text{.}$
🔗
Bahwa $P(k-2)$ mengimplikasikan $P(k+1)$ untuk setidaknya satu $k \ge 0\text{.}$
🔗

🔗

2.

Versi yang lebih sederhana dari masalah batang cokelat adalah sebagai berikut: Misalkan Anda memiliki batang cokelat yang panjangnya $n$ petak. Anda dapat membagi batang cokelat menjadi dua bagian dengan satu pematahan lurus melintang pada batang. Di mana pun setiap pematahan dilakukan, Anda akan menguraikan batang cokelat itu menjadi $n$ bagian setelah melakukan $n-1$ kali pematahan.

🔗

Susun beberapa pernyataan berikut dalam urutan yang tepat untuk membentuk pembuktian klaim ini dengan induksi kuat.

🔗

Misalkan \(P(n)\) adalah pernyataan bahwa batang cokelat yang panjangnya \(n\) petak dapat diuraikan menjadi \(n\) bagian dengan melakukan \(n-1\) kali pematahan.🔗

---

\(P(1)\) benar karena batang cokelat yang panjangnya 1 petak sudah berupa satu bagian.🔗

---
Asumsikan bahwa \(P(j)\) benar untuk semua \(j \le k\text{,}\) untuk suatu \(k \ge 1\) sembarang.🔗

---
Perhatikan batang cokelat yang panjangnya \(k+1\) petak.🔗

---
Di mana pun Anda mematahkan batang ini, hasilnya adalah dua batang yang lebih kecil, misalnya masing-masing dengan panjang \(a\) dan \(b\text{.}\)🔗

---
Karena \(a\) dan \(b\) tidak lebih besar daripada \(k\text{,}\) berdasarkan hipotesis induksi kedua batang yang lebih kecil ini dapat diuraikan menjadi petak-petak tunggal dengan masing-masing \(a-1\) dan \(b-1\) kali pematahan.🔗

---
Jadi, jumlah seluruh pematahan adalah \(a-1 + b-1 + 1 = a+b -1\text{,}\) yaitu \(k+1-1 = k\text{.}\)🔗

---
Oleh karena itu, berdasarkan prinsip induksi kuat, \(P(n)\) benar untuk semua \(n \ge 1\text{.}\)🔗

🔗

Latihan Latihan Tambahan

1.

Misalkan sebuah tim sepak bola Amerika hanya mencetak gol lapangan bernilai 3 poin dan touchdown bernilai 7 poin (abaikan kemungkinan safety, kegagalan poin tambahan, dan konversi dua poin). Buktikan dengan induksi kuat bahwa tim tersebut dapat memperoleh setiap jumlah poin yang sedikitnya 12.

🔗

Petunjuk.

Jika tiga kasus dasar telah dibuktikan, dapatkah Anda selalu memastikan bahwa tiga poin lagi dapat diperoleh?

🔗

2.

Buktikan dengan induksi kuat bahwa jumlah sudut dalam sebuah segi-$n$ konveks adalah $(n-2)\cdot 180^\circ\text{.}$ (Segi-$n$ konveks adalah poligon bersisi $n$ yang setiap sudut dalamnya kurang dari $180^\circ\text{.}$)

🔗

Petunjuk.

Mulailah dengan segi-$(k+1)\text{,}$ lalu bagilah menjadi dua poligon yang lebih kecil.

🔗

3.

Buktikan bahwa setiap bilangan bulat positif merupakan pangkat dari 2 atau dapat ditulis sebagai jumlah beberapa pangkat dari 2 yang saling berbeda.

🔗

4.

Buktikan dengan induksi kuat bahwa setiap bilangan asli merupakan bilangan Fibonacci atau dapat ditulis sebagai jumlah bilangan-bilangan Fibonacci yang berbeda.

🔗

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!

🔗

5.

Sebelumnya kita telah membuktikan bahwa untuk setiap pohon, banyaknya sisi selalu satu kurangnya dari banyaknya simpul. Artinya, pohon dengan $v$ simpul dan $e$ sisi memenuhi $v = e+1\text{.}$

🔗

Berikan pembuktian alternatif untuk fakta ini dengan menggunakan induksi kuat pada banyaknya simpul. Lakukan dengan mengambil sebuah simpul bukan daun dan “membelahnya” menjadi dua simpul yang masing-masing termasuk dalam pohon yang berbeda.

🔗

6.

Misalkan suatu bilangan riil $x$ memiliki sifat bahwa $x + \frac{1}{x}$ merupakan bilangan bulat. Buktikan bahwa $x^n + \frac{1}{x^n}$ merupakan bilangan bulat untuk semua bilangan asli $n\text{.}$

🔗

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.

🔗

7.

Berikut ini contoh teknik induksi yang lebih rumit, yang disebut induksi ganda.

🔗

Anda akan membuktikan bahwa bilangan-bilangan Fibonacci memenuhi identitas $F_n^2 + F_{n+1}^2 = F_{2n+1}\text{.}$ Salah satu caranya adalah dengan membuktikan identitas yang lebih umum,

\begin{equation*} F_mF_n + F_{m+1}F_{n+1} = F_{m+n+1}\text{,} \end{equation*}

lalu memperhatikan bahwa ketika $m = n\text{,}$ kita memperoleh hasil yang diinginkan.

🔗

Perhatikan bahwa sekarang kita memiliki dua variabel, sehingga kita ingin membuktikan hal ini untuk semua $m \ge 0$ dan semua $n \ge 0$ secara bersamaan. Untuk setiap pasangan $(m,n)$ tersebut, misalkan $P(m,n)$ adalah pernyataan $F_mF_n + F_{m+1}F_{n+1} = F_{m+n+1}\text{.}$

🔗

(a)

Pertama, tetapkan $m = 0\text{,}$ lalu berikan pembuktian dengan induksi matematika bahwa $P(0,n)$ berlaku untuk semua $n \ge 0\text{.}$ Perhatikan bahwa pembuktian ini akan sangat mudah.

🔗

(b)

Sekarang tetapkan $n$ sembarang, lalu berikan pembuktian dengan induksi matematika kuat bahwa $P(m,n)$ berlaku untuk semua $m \ge 0\text{.}$

🔗

(c)

Sekarang Anda dapat menyimpulkan bahwa $P(m,n)$ berlaku untuk semua $m,n\ge 0\text{.}$ Apakah Anda memercayainya? Jelaskan mengapa induksi semacam ini sah. Sebagai contoh, mengapa pembuktian Anda di atas menjamin bahwa $P(2,3)$ benar?

🔗

8.

Diberikan sebuah persegi, Anda dapat memotongnya menjadi persegi-persegi yang lebih kecil dengan membuat potongan sepanjang garis-garis yang sejajar dengan sisi persegi semula (garis-garis ini tidak harus membentang sepanjang seluruh sisi persegi semula). Sebagai contoh, dengan memotong sepanjang garis-garis di bawah ini, Anda akan membagi sebuah persegi menjadi 6 persegi yang lebih kecil:

🔗

$Satu persegi besar dengan lima persegi yang panjang sisinya setengah panjang sisi persegi tersebut, tersusun mengitari sisi atas dan kanan sehingga membentuk persegi yang lebih besar lagi.$

Buktikan dengan induksi kuat bahwa sebuah persegi dapat dipotong menjadi $n$ persegi yang lebih kecil untuk setiap $n \ge 6\text{.}$

🔗

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.

🔗

Sblm Top Lnjt

Subbab 4.6 Induksi Kuat

Tujuan Pembelajaran

Subbagian Pratinjau Bagian

Selidiki!

Contoh 4.6.1.

Bukti.

Lembar Kerja Kegiatan Pratinjau

1.

(a)

(b)

(c)

(d)

(e)

Subbagian Bagi dan Taklukkan

Struktur Pembuktian dengan Induksi Kuat.

Proposisi 4.6.2.

Bukti.

Contoh 4.6.3.

Bukti.

Pertanyaan Bacaan Pertanyaan Bacaan

1.

2.

3.

Latihan Soal Latihan

1.

2.

Latihan Latihan Tambahan

1.

2.

3.

4.

5.

6.

7.

(a)

(b)

(c)

8.

Lembar Kerja Kegiatan Pratinjau