Induksi matematika

Induksi matematika adalah metode pembuktian yang sering dipakai dalam matematika, terutama saat kita bekerja dengan bilangan asli atau dengan suatu barisan lain.

Prinsip

Prinsip dasarnya adalah membuktikan pernyataan untuk anggota pertama, yang pada bilangan asli biasanya n = 1. Hal ini kita buktikan dengan substitusi biasa. Pada langkah berikutnya, yaitu langkah induksi, kita membuktikan implikasi “jika pernyataan benar untuk n = a, maka pernyataan juga benar untuk n = a + 1”.

Dari kedua langkah ini, kita dapat menyimpulkan bahwa bentuk tersebut benar untuk semua n (dari himpunan yang sedang kita gunakan). Mengapa demikian? Di awal, kita membuktikan bahwa bentuk tersebut benar untuk n = 1. Kita juga tahu bahwa jika bentuk itu benar untuk n = a, bentuk itu juga benar untuk n = a + 1. Jadi, kita pilih a = 1. Kita tahu bahwa bentuk itu benar untuk a = 1, sehingga kita juga tahu bahwa bentuk itu benar untuk a + 1 = 2. Sekarang kita tahu bahwa bentuk itu benar untuk a = 2. Karena bentuk itu juga benar untuk a + 1, bentuk itu pasti benar untuk 2 + 1 = 3. Begitu seterusnya.

Contoh pertama

Contoh pertama ini trivial. Kita akan membuktikan bahwa jika suatu bilangan genap ditambah 2, hasilnya juga bilangan genap. Karena kita bekerja dengan bilangan asli, bilangan genap secara umum kita tulis sebagai 2n, dengan n bilangan asli. Jika n kita ganti dengan bilangan asli apa pun, hasilnya bilangan genap; hal ini terlihat sekilas. Keterbagian ditulis dengan garis tegak seperti ini:

$$2\mid 2n$$

Penulisan ini berarti 2 membagi habis bentuk 2n. Karena sudah bisa menuliskan keterbagian, kita juga bisa menuliskan apa yang harus kita buktikan dengan induksi matematika.

$$2\mid 2n+2;n\in \mathbb{N}$$

Inilah yang harus kita buktikan pada contoh pertama, yaitu bahwa 2 membagi bentuk 2n + 2. Pernyataan ini tepat sesuai dengan soal ceritanya: “jika suatu bilangan genap ditambah 2, hasilnya juga bilangan genap”.

Pada langkah pertama induksi, kita membuktikannya untuk anggota pertama, yaitu 1. Kita substitusikan n = 1 ke dalam bentuk tersebut:

$$\begin{array}{rcl}2& \mid & 2\cdot 1+2\\ 2& \mid & 4\end{array}$$

Bilangan 2 membagi habis 4, jadi pernyataannya benar untuk anggota pertama. Selanjutnya tiba langkah induksi: kita harus membuktikan bahwa jika pernyataan benar untuk anggota ke-a, maka pernyataan juga benar untuk anggota ke-(a + 1). Di awal, kita menganggap hipotesis induksi kita benar, yaitu untuk n = a:

$$2\mid 2a+2$$

Bentuk ini kita anggap benar, dan akan kita pakai saat menyusun bukti. Sekarang kita ingin membuktikan bahwa

$$2\mid 2(a+1)+2.$$

Apa yang kita lakukan? Sebagai ganti a, kita menuliskan (a + 1). Tanda kurungnya penting; bentuk berikut salah: 2a + 1 + 2. Kita tidak menambahkan 1 pada seluruh bentuk, tetapi benar-benar mengganti a dengan bentuk yang satu lebih besar, yaitu (a + 1). Bentuk tersebut kita ubah dengan menjabarkan tanda kurungnya.

$$\begin{array}{rcl}2& \mid & 2(a+1)+2\\ 2& \mid & 2a+2+2\end{array}$$

Sekarang kita sedikit menyimpang untuk membahas keterbagian. Jika kita mempunyai dua bilangan, misalnya p dan q, yang habis dibagi suatu bilangan, misalnya r, maka jumlahnya juga habis dibagi r. Jadi, berlaku:

$$(r\mid p\wedge r\mid q)\Rightarrow r\mid (p+q)$$

Sebagai contoh, kita bisa menyubstitusikan bilangan p = 8, q = 20, dan r = 4. Terlihat bahwa 4 membagi 8 dan juga 20. Begitu pula, 4 membagi jumlahnya, 8 + 20 = 28.

Bagaimana kita memanfaatkannya dalam contoh kita? Ruas kanan kita bagi menjadi bilangan p dan q seperti ini:

$$p=2a+2;q=2$$

Bilangan q, yaitu 2, jelas habis dibagi 2. Bentuk p juga habis dibagi dua, karena hipotesis induksi menyatakannya. Bentuk p tepat sama dengan hipotesis induksi kita, yang kita anggap benar. Jika p habis dibagi dua dan sekaligus q habis dibagi dua, maka jumlahnya juga habis dibagi dua.

Sekali lagi tentang hipotesis induksi. Di awal, kita menyatakan bahwa kita menganggap berlaku

$$2\mid 2a+2.$$

Karena itu, ketika saat menyusun bukti kita menemukan bentuk 2a + 2, kita boleh mengatakan bahwa bentuk itu habis dibagi dua, justru karena itulah hipotesis induksi kita. Biasanya inilah langkah tersulit dalam induksi matematika: memahami kapan dan mengapa hipotesis induksi boleh dipakai.

Dengan ini, induksi selesai. Bukti berhasil dilakukan, dan teoremanya berlaku.

Jika mau, kamu bisa menguraikannya dengan cara lain tanpa memakai hipotesis induksi: p = 2n dan q = 2 + 2. Bilangan q = 4 jelas habis dibagi dua, begitu pula p = 2n, karena setelah dibagi dua tersisa bilangan n, yang merupakan bilangan asli, jadi bilangan bulat. Sekali lagi kita memperoleh dua bentuk yang sama-sama habis dibagi dua, sehingga jumlahnya juga habis dibagi dua.

Namun, dalam kedua cara itu kita telah membuktikan bahwa

1. bentuk tersebut benar untuk n = 1,
2. jika bentuk tersebut benar untuk n, maka bentuk itu juga benar untuk n + 1.

Dari sini kita dapat menyimpulkan:

• Kita tahu bahwa bentuk tersebut benar untuk n = 1.
• Jika benar untuk n, bentuk itu pasti benar untuk n + 1, yaitu untuk 1 + 1. Jadi, bentuk itu juga benar untuk n = 2.
• Jika benar untuk n, bentuk itu pasti benar untuk n + 1, yaitu untuk 2 + 1. Jadi, bentuk itu juga benar untuk n = 3.
• Jika benar untuk n, bentuk itu pasti benar untuk n + 1, yaitu untuk 3 + 1. Jadi, bentuk itu juga benar untuk n = 4.
• Jika benar untuk n, bentuk itu pasti benar untuk n + 1, yaitu untuk 4 + 1. Jadi, bentuk itu juga benar untuk n = 5.
• …

Contoh kedua

Selanjutnya, dengan induksi matematika kita akan membuktikan pernyataan sederhana berikut:

$$2^n\ge 2n;n\in \mathbb{N}.$$

Pertama, langkah dasar: kita periksa apakah pernyataan benar untuk n = 1, anggota pertama bilangan asli yang menjadi asal n.

$$\begin{array}{rcl}{2}^1& \ge & 2\cdot 1\\ 2& \ge & 2\end{array}$$

Pernyataan ini jelas benar. Sekarang kita lanjutkan ke langkah induksi. Di sini kita harus memeriksa apakah pernyataan yang benar untuk n = a juga benar untuk n = a + 1. Jadi, hipotesis induksi kita adalah bahwa berlaku

$$2^a\ge 2a$$

dan kita ingin membuktikan:

$$2^{a+1}\ge 2(a+1)$$

Pertama, ruas kiri kita uraikan dengan aturan bilangan berpangkat, sedangkan ruas kanan cukup kita jabarkan.

$$2\cdot 2^a\ge 2a+2$$

Pada ruas kiri, perkalian kita ganti dengan penjumlahan, sedangkan ruas kanan dibiarkan tetap.

$$2^a+2^a\ge 2a+2$$

Sekarang kita memanfaatkan hipotesis induksi. Hipotesis induksi adalah pernyataan yang kita anggap benar. Dalam pertidaksamaan ini, di setiap ruas ada dua suku yang dijumlahkan. Selain itu, kita tahu bahwa

$$\begin{array}{rcl}{2}^a& \ge & 2a\\ 2^a& \ge & 2.\end{array}$$

Baris pertama berasal dari hipotesis induksi, dan pernyataan kedua trivial (nilai 2^a terkecil dicapai untuk a = 1, dan nilainya sama dengan dua). Jadi, kita tahu bahwa kedua suku di ruas kiri lebih besar daripada atau sama dengan kedua suku di ruas kanan. Dengan demikian, kita telah membuktikan dengan induksi bahwa jika bentuk tersebut benar untuk a, bentuk itu juga benar untuk (a + 1). Karena bentuk tersebut juga benar untuk 1, bentuk itu benar.

Contoh ketiga

Mari kita coba membuktikan pernyataan berikut:

$$3\mid n\Rightarrow 3\mid n^2;n\in \mathbb{N}$$

Dengan kata-kata: jika n habis dibagi tiga, maka n² juga habis dibagi tiga. Jika n tidak habis dibagi tiga, bentuk tersebut jelas benar (menurut definisi implikasi), jadi kita hanya akan membahas kasus ketika n habis dibagi tiga. Kasus ini menghasilkan barisan bilangan asli a_i=3, 6, 9, 12, 15… Mulai sekarang, kita bekerja di dalam barisan a_i ini.

Bukti dengan induksi kita mulai dengan langkah dasar, yaitu memeriksa apakah pernyataan benar untuk anggota pertama. Ingat, kita bekerja di dalam barisan a_i, jadi kita mengambil suku pertama barisan ini, yaitu suku a₁, yang sama dengan 3. Untuk 3, bentuk tersebut benar:

$$3\mid 3\Rightarrow 3\mid 3^2$$

Sekarang kita lanjutkan ke langkah induksi. Terlihat bahwa barisan a_i dapat ditulis sebagai 3n, dengan n bilangan asli. Jadi, suku kedua tiga lebih besar daripada suku sebelumnya, dan seterusnya. Sekarang kita anggap bentuk tersebut benar untuk n, dan kita harus memastikan bahwa bentuk itu juga benar untuk (n + 3), yaitu rumus yang menghasilkan suku berikutnya dalam barisan yang kita gunakan. Pertama, kita tuliskan hipotesis induksinya:

$$3\mid n\Rightarrow 3\mid n^2$$

lalu apa yang ingin kita buktikan:

$$3\mid (n+3)\Rightarrow 3\mid (n+3{)}^2.$$

Tanda kurung di ruas kanan kita jabarkan dengan rumus:

$$3\mid (n+3)\Rightarrow 3\mid n^2+6n+9.$$

Kita hampir sampai. Di ruas kiri ada bentuk yang pasti habis dibagi tiga, karena menurut hipotesis n habis dibagi tiga (kita hanya bekerja dengan bilangan dari barisan a_i), dan 3 juga habis dibagi tiga. Di ruas kanan, pertama ada n², yang menurut hipotesis habis dibagi tiga. Sebab, kita tahu bahwa n habis dibagi tiga, dan hipotesis induksi menyatakan bahwa jika n habis dibagi tiga, maka n² juga habis dibagi tiga:

$$3\mid n\Rightarrow 3\mid n^2$$

Selanjutnya ada bentuk 6n, yang jelas habis dibagi tiga. Kamu bisa membayangkannya sebagai penyederhanaan pecahan:

$$\frac{6n}{3}=2n$$

Variabel n adalah suatu bilangan asli, jadi hasil kali 2n juga bilangan asli. Artinya, setelah dibagi tiga kita memperoleh bilangan asli, sehingga bentuk 6n pasti habis dibagi tiga. Terakhir, 9 juga habis dibagi tiga. Bentuk tersebut benar untuk anggota pertama dan pada langkah induksi, jadi bentuk itu benar.

Banyaknya tanda kurung dalam suatu ekspresi

Contoh terakhir ini agak tidak biasa. Kita akan mencoba membuktikan pernyataan bahwa banyaknya tanda kurung dalam ekspresi sederhana selalu genap. Dengan begitu, kamu akan melihat bahwa induksi matematika dapat dipakai juga dalam konteks yang sama sekali berbeda, bukan hanya pada bilangan asli. Pertama, kita harus mendefinisikan apa itu ekspresi sederhana. Ekspresi sederhana adalah:

• bilangan asli,
• jika p ekspresi sederhana, maka (p²) juga ekspresi sederhana,
• jika p dan q ekspresi sederhana, maka (p + q) juga ekspresi sederhana.

Jadi, berikut ini adalah ekspresi sederhana: 12, 54, (5 + 6), (12 + 7), (6²), ((5 + 6)²). Sebaliknya, berikut ini bukan ekspresi sederhana:

• 1 + 2 → tidak ada tanda kurung luar,
• (1 + 2 → tidak ada kurung tutup,
• 13² → tidak ada tanda kurung luar,
• (1 + 2 + 3) → kurang tanda kurung; penulisan yang benar adalah (1 + (2 + 3))

Ekspresi sederhana dapat terbentuk, misalnya, seperti ini. Di awal, kita pilih ekspresi sederhana (a + b). Sekarang kita ganti a dengan ekspresi sederhana a = (c + d), sehingga diperoleh ((c + d) + b), lalu b kita ganti dengan 3: ((c + d) + 3). Kemudian c kita ganti dengan 10: ((10 + d) + 3), dan terakhir d kita ganti dengan (5²): ((10 + (5²)) + 3). Tanda kurung harus dijaga dengan tepat, jika tidak, cara ini tidak akan berhasil.

Sekarang kita akan membuktikan bahwa ekspresi sederhana memuat tanda kurung yang banyaknya genap (nol juga termasuk bilangan genap).

Pada langkah pertama induksi, kita memilih suatu anggota pertama. Dalam kasus ini, anggota pertama adalah ekspresi sederhana yang paling trivial, yaitu bilangan asli sembarang. Jadi, kita tetapkan

$$j=n;n\in \mathbb{N}.$$

Untuk ekspresi j, banyaknya tanda kurung adalah nol, jadi anggota pertama memenuhi pernyataan. Pada langkah induksi, kita menganggap bahwa kita mempunyai dua ekspresi sederhana p dan q, dan keduanya memuat tanda kurung yang banyaknya genap. Lalu kita harus membuktikan bahwa ekspresi sederhana (p + q) dan (p²) juga memuat tanda kurung yang banyaknya genap.

Pertama, penjumlahan. Kita definisikan fungsi z(q) yang menghasilkan banyaknya tanda kurung dalam ekspresi q. Maka ekspresi (p + q) memuat z(p) + z(q) + 2 tanda kurung, yaitu dua tanda kurung lebih banyak daripada jumlah tanda kurung pada ekspresi p dan q. Menurut hipotesis induksi, z(p) dan z(q) genap, sehingga jika kita menjumlahkan tiga bilangan genap, kita memperoleh bilangan genap lagi. Untuk kasus ini, pernyataannya benar.

Sekarang pangkat. Sekali lagi berlaku hipotesis induksi bahwa ekspresi sederhana p memuat tanda kurung yang banyaknya genap. Maka ekspresi (p²) memuat z(p) + 2 tanda kurung, yaitu sekali lagi dua tanda kurung lebih banyak daripada ekspresi p. Dalam kasus ini pun kita menjumlahkan bilangan-bilangan genap, sehingga hasilnya genap.

Pernyataan ini benar untuk anggota pertama dan juga pada langkah induksi, sehingga pernyataannya benar.