Berbagi pengetahuan, dari mana saja, dari siapa saja, untuk semua

Pembuktian dengan Induksi Matematis

Dalam membuktikan suatu pernyataan atau rumusan matematis, kadang kita berhadapan dengan suatu masalah khusus yang ingin dibuktikan kebenarannya secara umum. Misalkan saja kita berhadapan dengan sebuah deret:

\sum_{i=1}^n i^2 = 1^2 + 2^2 + \ldots + n^2,

dengan n adalah bilangan asli. Kemudian anggaplah ada seseorang yang berkata pada kita bahwa ada rumus singkat yang dapat digunakan untuk menghitung deret tersebut, yaitu

\frac{1}{6} n (n+1) (2 n + 1).

Pertanyaannya sekarang, apakah rumus ini benar?

Kita dapat mencoba beberapa nilai n:

n = 1:

\sum_{i=1}^1 i^2 = 1^2 = 1

\frac{1}{6} n (n+1) (2 n + 1) = \frac{1}{6} \times 1 \times 2 \times 3 = 1 n = 2:

\sum_{i=1}^2 i^2 = 1^2 + 2^2 = 1 + 4 = 5

\frac{1}{6} n (n+1) (2 n + 1) = \frac{1}{6} \times 2 \times 3 \times 5 = 5 n = 3:

\sum_{i=1}^3 i^2 = 1^2 + 2^2 + 3^2 = 1 + 4 + 9 = 14

\frac{1}{6} n (n+1) (2 n + 1) = \frac{1}{6} \times 3 \times 4 \times 7 = 14

Tampaknya hasil yang diperoleh sudah benar, tetapi, apakah rumus tersebut benar untuk seluruh nilai n? Sepertinya hal yang mustahil untuk membuktikan kebenaran rumus tersebut dengan mencoba satu per satu nilai n. Adakah cara yang lebih sederhana namun akurat untuk membuktikan kebenaran rumus seperti ini?

Untuk menjawab pertanyaan ini, mari kita ambil pelajaran dari permainan domino. Jika kita mengatur banyak kartu domino dalam sebuah barisan, kemudian kita mengetuk kartu paling depan, kartu-kartu di belakangnya akan ikut jatuh semua.

ed24-matematika-1

Prinsip pembuktian dengan induksi matematis mirip seperti permasalahan domino ini. Misalkan kita punya sebuah pernyataan matematis P(n), dan kita ingin buktikan benar untuk seluruh P(n). Dalam contoh kita sebelumnya, P(n) didefinisikan sebagai

P(n) = \sum_{i=1}^n i^2 = \frac{1}{6} n (n+1) (2 n + 1).

Nah, setiap nilai P(n) dapat dibayangkan sebagai sebuah kartu domino. Jika kita dapat menunjukkan P(1) benar, kita harus mampu menunjukkan P(n) dan P(n+1) benar secara berturutan. Singkat kata, kita harus buktikan P(n+1) memiliki pola yang sama seperti P(n). Dengan begitu kita boleh mengatakan P(n) benar untuk seluruh n \geq 1.

Untuk contoh kasus yang kita hadapi ini artinya kita harus buktikan bahwa \sum_{i=1}^{n+1} i^2 memiliki pola rumus yang sama seperti \sum_{i=1}^n i^2 = \frac{1}{6} n (n+1) (2 n + 1).

Ok, kalau begitu mari kita hitung \sum_{i=1}^{n+1} i^2:

\sum_{i=1}^{n+1} i^2 = (n+1)^2 + \sum_{i=1}^n i^2

= (n+1)^2 + \frac{1}{6} n (n+1) (2 n + 1)
= \frac{1}{6} (n+1) [6 (n+1) + n (2 n + 1)]
= \frac{1}{6} (n+1) (6 n + 6 + 2 n^2 + n)
= \frac{1}{6} (n+1) (2 n^2 + 7 n + 6)
= \frac{1}{6} (n+1) (n + 2) (2 n + 3)

Hmm, tampaknya bentuk yang terakhir ini mirip sesuatu yang kita kenali. Mari kita coba cek P(n+1). Kita substitusi n+1 pada tempatnya n dalam rumusan P(n):

\sum_{i=1}^n i^2 = \frac{1}{6} n (n+1) (2 n + 1)

sehingga

\sum_{i=1}^{n+1} i^2 = \frac{1}{6} (n+1) (n+2) [2 (n+1) + 1] = \frac{1}{6} (n+1) (n + 2) (2 n + 3).

Wow! Hasilnya sama persis dengan perhitungan sebelumnya. Dengan cara ini, kita sudah menunjukkan bahwa jika P(n) benar, maka P(n+1) pun benar, sehingga P(n) dapat berlaku untuk seluruh n.

Sebagai rangkuman, untuk membuktikan kebenaran sebuah pernyataan atau rumus matematis dengan metode induksi, hal yang perlu kita lakukan adalah:

  1. Kita perlu buktikan P(1) benar, dan
  2. Kita perlu menunjukkan P(n+1) memiliki pola rumus yang sama dengan P(n).

Oya,  perlu diketahui sebenarnya kartu “domino” kita yang pertama pun tidak perlu selalu P(1), bisa saja kita gunakan P(2), atau P(3), atau bahkan P(1000). Dengan demikian, kita bisa menunjukkan (contoh saja) 3^n > n^3 untuk rentang yang sudah dibatasi pada n \geq 4. Tentu saja induksi matematis hanyalah salah satu contoh metode pembuktian. Kita tidak selalu bisa menggunakan metode ini untuk membuktikan persoalan yang lain. Atau, bisa saja persoalan tersebut dibuktikan dengan metode induksi namun sebenarnya ada metode yang lain bisa lebih efektif untuk membuktikan sebuah pernyataan matematis. Di sinilah pentingnya untuk mengenal bermacam-macam metode pembuktian dalam matematika.

Catatan:
Tulisan ini merupakan saduran bebas dari salah satu artikel berbahasa Inggris di http://nrich.maths.org/ tentang metode pembuktian.

Bahan bacaan:

Penulis:
Ahmad Ridwan T. Nugraha, peneliti fisika, alumnus ITB dan Tohoku University.
Kontak: art.nugraha(at)gmail(dot)com.