Induksi Matematika — Prinsip, Langkah & Contoh

Induksi matematika adalah metode pembuktian untuk menunjukkan bahwa suatu pernyataan benar untuk setiap bilangan bulat mulai dari suatu nilai awal tertentu. Untuk membuktikan suatu klaim bagi semua $n \ge n_0$, Anda menunjukkan bahwa kasus pertama benar, lalu menunjukkan bahwa kebenaran pada satu bilangan bulat memaksa kebenaran pada bilangan bulat berikutnya.

Jika kedua bagian itu benar, maka pernyataan tersebut berlaku untuk setiap bilangan bulat dalam rentang yang dinyatakan. Itulah inti idenya.

Cara kerja induksi matematika

Tuliskan klaim sebagai $P(n)$. Lalu induksi memiliki struktur berikut:

1. Buktikan kasus dasar: tunjukkan bahwa $P(n_0)$ benar.
2. Buktikan langkah induksi: tunjukkan bahwa jika $P(k)$ benar untuk suatu bilangan bulat sembarang $k \ge n_0$, maka $P(k+1)$ juga benar.

Setelah itu selesai, Anda dapat menyimpulkan bahwa $P(n)$ benar untuk setiap bilangan bulat $n \ge n_0$.

Logikanya bersifat berurutan. Kasus dasar memulai rantainya, dan langkah induksi menjaga rantai itu terus berjalan satu bilangan bulat pada satu waktu.

Mengapa kasus dasar dan langkah induksi sama-sama penting

Kasus dasar memberi Anda pernyataan benar yang pertama. Langkah induksi menyatakan bahwa kebenaran berpindah dari satu bilangan bulat ke bilangan bulat berikutnya.

Jadi jika $P(n_0)$ benar, maka $P(n_0 + 1)$ benar. Lalu $P(n_0 + 2)$ benar, dan seterusnya. Induksi tidak melewati titik awal, dan juga tidak melewati penghubung dari satu kasus ke kasus berikutnya.

Contoh dikerjakan: membuktikan rumus jumlah dengan induksi

Contoh standar adalah rumus

$$1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$$

untuk semua bilangan bulat $n \ge 1$.

Misalkan

$$P(n): 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$$

Kasus dasar

Ambil $n = 1$. Sisi kiri bernilai $1$, dan sisi kanan adalah

$$\frac{1(1+1)}{2} = 1$$

Jadi $P(1)$ benar.

Langkah induksi

Asumsikan $P(k)$ benar untuk suatu bilangan bulat sembarang $k \ge 1$. Artinya,

$$1 + 2 + 3 + \cdots + k = \frac{k(k+1)}{2}$$

Sekarang buktikan $P(k+1)$. Mulailah dari sisi kiri untuk $k+1$:

$$1 + 2 + 3 + \cdots + k + (k+1)$$

Dengan menggunakan hipotesis induksi,

$$\frac{k(k+1)}{2} + (k+1)$$

Faktorkan $(k+1)$:

$$(k+1)\left(\frac{k}{2} + 1\right)$$

Lalu sederhanakan:

$$(k+1)\left(\frac{k+2}{2}\right) = \frac{(k+1)(k+2)}{2}$$

Itu tepat sama dengan rumus saat $n = k+1$. Jadi $P(k+1)$ benar.

Karena kasus dasar dan langkah induksi keduanya sudah dibuktikan, rumus tersebut berlaku untuk semua bilangan bulat $n \ge 1$.

Kapan menggunakan induksi matematika

Induksi berguna ketika suatu pernyataan bergantung pada parameter bilangan bulat dan setiap kasus secara alami terhubung ke kasus sebelumnya. Ini sering terjadi pada jumlah, pernyataan keterbagian, pertidaksamaan, relasi rekurensi, dan pembuktian algoritma.

Pertama, tentukan nilai awal yang benar. Beberapa klaim dimulai dari $n = 0$, beberapa dari $n = 1$, dan beberapa hanya masuk akal untuk bilangan bulat yang lebih besar.

Lalu periksa apa kasus valid berikutnya. Langkah yang biasa adalah dari $k$ ke $k+1$, tetapi jika pernyataannya hanya tentang bilangan bulat genap, langkah dari $k$ ke $k+2$ mungkin merupakan versi yang tepat.

Kesalahan umum dalam bukti induksi

Hanya membuktikan kasus dasar

Kasus dasar hanya memeriksa nilai pertama. Dengan sendirinya, itu tidak membuktikan pernyataan untuk bilangan bulat berikutnya.

Menggunakan nilai awal yang salah

Jika klaim dimaksudkan untuk semua $n \ge 2$, membuktikan hanya $P(1)$ tidak membantu. Kasus dasar harus sesuai dengan rentang klaim yang sebenarnya.

Memperlakukan hipotesis induksi secara ceroboh

Dalam langkah induksi, Anda mengasumsikan $P(k)$ untuk satu bilangan bulat sembarang $k$ dalam rentang yang valid. Anda tidak mengasumsikan bahwa seluruh teorema sudah terbukti.

Membuktikan kasus berikutnya yang salah

Jika teorema Anda memerlukan langkah $k \to k+1$, membuktikan langkah yang berbeda tidak menyelesaikan argumen kecuali Anda menjelaskan mengapa langkah berbeda itu sudah cukup.

Perluasan yang berguna: induksi kuat

Kadang-kadang membuktikan $P(k+1)$ memerlukan lebih dari sekadar $P(k)$. Dalam situasi itu, induksi kuat memungkinkan Anda mengasumsikan semua kasus sebelumnya hingga $k$, lalu membuktikan kasus berikutnya.

Idenya sangat berkaitan, tetapi asumsinya lebih kuat. Ini berguna, misalnya, ketika suatu bukti bergantung pada pemecahan sebuah bilangan menjadi bagian-bagian yang lebih kecil.

Coba versi Anda sendiri

Ambil klaim

$$1 + 3 + 5 + \cdots + (2n - 1) = n^2$$

dan buktikan untuk semua bilangan bulat $n \ge 1$ dengan menggunakan struktur yang sama: kasus dasar terlebih dahulu, lalu langkah dari $k$ ke $k+1$. Jika Anda bisa menulis bukti itu dengan rapi, biasanya metodenya akan terasa masuk akal.