Bukti dengan induksi
Diperkenalkan| English | Makna |
|---|---|
| positive integer/ˈpɒzɪtɪv ˈɪntɪdʒə/ | bilangan bulat positif |
| mathematical induction/ˌmæθɪˈmætɪkl ɪnˈdʌkʃn/ | induksi matematika |
| base case/beɪs keɪs/ | kasus dasar |
| inductive step/ɪnˈdʌktɪv step/ | langkah induksi |
| conjecture/kənˈdʒektʃə/ | konjektur |
| divisible/dɪˈvɪzɪbl/ | habis dibagi |
Pembuktian domino
- Bagaimana Anda membuktikan sesuatu benar untuk setiap bilangan bulat positif — tak terhingga banyak kasus?
- Induksi matematika bekerja seperti domino: menjatuhkan yang pertama (kasus dasar), dan menunjukkan setiap domino menjatuhkan berikutnya (langkah induktif). Jika keduanya berhasil, semuanya akan jatuh.
Rute bukti dengan induksi
Anggap induksi sebagai domino pertama ditambah aturan yang mendorong setiap kasus berikutnya.
Dua langkah induksi
- Induksi matematika membuktikan suatu hasil untuk setiap bilangan bulat positif $n$ dalam dua langkah:
- Kasus dasar: tunjukkan bahwa itu benar untuk $n = 1$.
- Langkah induktif: asumsikan benar untuk $n = k$, lalu buktikan untuk $n = k + 1$.
Contoh terpecahkan. Buktikan $\sum_{r=1}^{n} r = \dfrac{n(n+1)}{2}$. Kasus dasar ($n=1$): Sisi kiri $= 1$, sisi kanan $= \dfrac{1(2)}{2} = 1$. ✓ Langkah induktif: Asumsikan benar untuk $n = k$. Untuk $n = k+1$: $\sum_{r=1}^{k+1} r = \dfrac{k(k+1)}{2} + (k+1) = \dfrac{(k+1)(k+2)}{2}$. ✓
Pembuktian dengan induksi bekerja seperti rantai domino yang jatuh
Dua langkah bukti dengan induksi adalah kasus dasar dan:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Induksi memerlukan kasus dasar ditambah langkah induktif dari k ke k+1.
Kasus dasar biasanya menunjukkan bahwa hasilnya benar untuk:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Kasus dasar memeriksa nilai terkecil, biasanya n = 1.
Jika baik kasus dasar maupun langkah induktif berlaku, hasilnya benar untuk semua bilangan bulat positif n.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Itu persis apa yang dijamin oleh prinsip induksi.
Mengapa kedua langkah itu penting
- Kasus dasar memulai rantai. Tanpanya, Anda bisa "membuktikan" pernyataan yang salah.
- Langkah induktif memperluasnya. Tanpanya, Anda hanya telah membuktikan satu kasus.
Kedua langkah itu penting. Pembuktian dengan hanya langkah induktif seperti barisan domino yang tidak didorong siapa pun — mereka tidak akan pernah mulai jatuh. Pembuktian dengan hanya kasus dasar seperti mendorong satu domino — hanya satu yang jatuh.
Anda dapat membuktikan suatu hasil dengan induksi hanya menggunakan langkah induktif, tanpa kasus dasar.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Kedua langkah sangat penting. Tanpa kasus dasar, rantai tidak pernah dimulai.
Konjektur lalu buktikan
- Seringkali Anda membuat konjektur (tebakan masuk akal) dari beberapa kasus, lalu mengonfirmasinya melalui pembuktian induktif.
- Contoh: $1 + 3 + 5 + 7 = 16 = 4^2$. Konjektur: jumlah $n$ bilangan ganjil pertama adalah $n^2$.
Menggunakan induksi, jumlah 1 + 2 + ... + n = n(n+1)/2. Untuk n = 10, temukan jumlahnya.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
10(11)/2 = 55.
Induksi untuk keterbagian
- Buktikan $3^n - 1$ habis dibagi oleh $2$ untuk semua bilangan bulat positif $n$.
- Kasus dasar ($n=1$): $3^1 - 1 = 2$, habis dibagi $2$. ✓
- Langkah induktif: $3^{k+1} - 1 = 3 \cdot 3^k - 1 = 3(3^k - 1) + 2$. Karena $3^k - 1$ habis dibagi oleh $2$ (berdasarkan asumsi), maka seluruh ekspresi juga habis dibagi. ✓
Dalam matematika, konjektur adalah:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Konjektur adalah pernyataan yang belum terbukti berdasarkan bukti — Anda kemudian mencoba membuktikannya (sering dengan induksi).
Anda telah memahaminya
- induksi = kasus dasar ($n=1$) + langkah induktif ($n=k \Rightarrow n=k+1$)
- kedua langkah bersama-sama membuktikannya untuk semua bilangan bulat positif
- sering kali konjektur dari kasus, lalu buktikan dengan induksi