Cara Mengerjakan Soal Induksi Matematika

Proses berpikir induktif (berpola dari khusus ke umum) dilakukan dengan cara diawali dari premis-premis yang benar (dibuktikan benar) kemudian ditarik sebuah kesimpulan yang berlaku benar untuk semua kasus (bersifat menggeneralisasi). Kendatipun premis-premis dan proses pembuktiannya benar, kesimpulannya (generalisasi) tidak pasti benar, kecuali semua kasusnya dapat dibuktikan. Tetapi, hal tersebut tidak selalu bisa dilakukan jika kasusnya terlalu banyak. Sedangkan di dalam matematika diajarkan membuktikan semua kasus. Tidak boleh memunculkan suatu pernyataan yang mengklaim pernyataan itu benar untuk semua kasus yang dibicarakan. Adapun misalkan ada beberapa kasus yang pernyataan itu menjadi salah maka harus diberi batasan pada kasus apa saja pernyataan tersebut benar. Semakin luas cakupan kasusnya maka pernyataan tersebut semakin berarti.

Di dalam soal-soal matematika, yang dimaksud soal induksi matematika adalah pembuktian terhadap pernyataan-pernyataan dalam bentuk n dimana n bilangan asli. Kita misalkan kumpulan-kumpulan soal induksi matematika tersebut dengan menggunakan notasi pembentuk himpunan yakni {P(n) : n $ \in N$}. Untuk membuktikan suatu pernyataan  P(n) bernilai benar untuk setiap bilangan asli n, tentu kita harus dapat membuktikan pernyataan tersebut berlaku untuk semua n. Apabila pernyataan tersebut dibatasi misalnya pada $n \ge a$ maka harus dapat ditunjukkan pernyataan P(n) benar untuk semua $ n \ge a$. Karena  bilangan asli ada banyak sekali (tak hingga) maka perlu dikembangkan suatu cara yang dapat menggeneralisasi. Hal ini dilakukan dengan cara menggunakan variabel sebagai refresentatif dari semua anggota himpunan bilangan asli yang dibicarakan tersebut dengan dua prinsip induksi matematika yang akan dibahas berikut ini.

Prinsip Induksi Matematika Pertama

Misalkan {P(n): n $ \in N$} kumpulan pernyataan untuk setiap bilangan asli mempunyai satu pernyataan. Jika P(n=1) benar; dan jika P(n=k) benar mengakibatkan P(n=k+1) juga benar; Maka pernyataan P(n) benar untuk setiap n.
Prinsip ini diturunkan berdasarkan sifat aksioma Peano. Dengan sifat tersebut, kita dapat membuktikan pernyataan yang berlaku bagi setiap bilangan asli.

Modifikasi Prinsip Induksi Matematika Pertama

Misalkan {P(n): n $ \in N$} kumpulan pernyataan untuk setiap bilangan asli mempunyai satu pernyataan. Jika P(a) benar untuk suatu bilangan asli a, dan jika P(k) benar mengakibatkan P(k+1) juga benar, maka pernyataan P(n) benar untuk setiap bilangan asli  $n \ge a$.
Dengan prinsip tersebut, untuk membuktikan pernyataan P(n) benar untuk semua bilangan asli dengan $n \ge a$, kita lakukan dengan dua langkah berikut ini.
Langkah pertama: Tunjukkan P(n) benar untuk n=a.
Langkah kedua: Tunjukkan jika P(n) benar untuk n=k mengakibatkan P(n) juga benar untuk n=k+1.
Kesimpulan: P(n) benar untuk setiap bilangan asli $n \ge a$.

Contoh soal 1: Buktikan bahwa $n! \le n^n$ untuk semua n bilangan asli ($n \ge 1$)
Contoh soal 2: Buktikan bahwa untuk $2^n < n!$ untuk $n \ge 4$
  • Jawaban Soal 1
Misalkan P(n): $n! \le n^n$.
Langkah Pertama: Untuk n=1 maka $1! \le 1^1 \Leftrightarrow 1 \le 1 $. Perhatikan $1 \le 1 $ bernilai benar, maka  P(1) bernilai benar.
Langkah Kedua: Jika P(k) benar untuk k sebarang bilangan asli akan ditunjukkan bahwa P(k+1) juga benar:
$\begin{align} k! & \le k^k \\ (k+1)k! & \le (k+1)k^k < (k+1)(k+1)^k \\ (k+1)! & < (k+1)(k+1)^k \\ (k+1)! & < (k+1)^{k+1} \end{align} $ 
Kesimpulan: Karena untuk P(k) yang diandaikan benar mengimplikasikan P(k+1) juga benar, maka disimpulkan $n! \le n^n$ benar untuk setiap n.   
  • Jawaban Soal 2
Misalkan P(n): $2^n < n!$. 
Langkah Pertama: Untuk n=4 maka $2^4 < 4! \Leftrightarrow 16 < 24 $. Jadi, P(4) bernilai benar.
Langkah Kedua: Andaikan P(k) benar untuk  sebarang $k \ge 4$ akan ditunjukkan P(k+1) juga benar:
$\begin{align} 2^k &< k! \\ 2.2^k &< 2.k! < (k+1)k!  \\ 2.2^k &< (k+1)k! \\ 2^{k+1} &< (k+1)!  \end{align}$
Kesimpulan: Karena P(k) yang diandaikan benar mengakibatkan P(k+1) juga benar, maka disimpulkan $2^n < n!$ benar untuk setiap $n \ge 4$.

Prinsip Induksi Matematika Kedua

Misalkan {P(n): n $ \in N$} kumpulan pernyataan untuk setiap bilangan asli mempunyai satu pernyataan. Jika P(1) benar, dan jika P(m) benar untuk setiap $m \le k$ mengakibatkan P(k+1) juga benar, maka pernyataan P(n) benar untuk setiap n.
Contoh Soal: Buktikan bahwa $(2+ \sqrt{3})^n + (2 – \sqrt{3})^n$ selalu merupakan bilangan bulat untuk n $\in N$.
Jawab: 
Kita lakukan dua langkah.
Langkah 1: Untuk n=1, maka
$(2+ \sqrt{3})^1 + (2 – \sqrt{3})^1=4$
merupakan bilangan bulat. Jadi pernyataan benar untuk n=1.
Langkah 2: Jika k bilangan asli, asumsikan bahwa pernyataan benar untuk semua bilangan asli $m \le k$, artinya
$(2+ \sqrt{3})^m + (2 – \sqrt{3})^m$
suatu bilangan bulat untuk semua bilangan asli $m \le k$. Selanjutnya kita akan membuktikan bahwa
$(2+ \sqrt{3})^{k+1} + (2 – \sqrt{3})^{k+1}$
juga bilangan bulat. Tetapi 
$\begin{align}a^{k+1}+b^{k+1} &= (a^k+b^k)(a+b)-ab^k-ba^k \\ &=(a^k+b^k)(a+b)-ab(a^{k-1}+b^{k-1}) \end{align}$
dengan $a=2+\sqrt{3}$ dan $b=2-\sqrt{3}$. Kita dapat menguji langsung bahwa ab bilangan bulat. Berdasarkan asumsi bahwa $a^k+b^k$, $a^{k-1}+b^{k-1}$ dan $a+b$ bilangan bulat, maka $a^{k+1}+b^{k+1}$ juga bilangan bulat.
Kesimpulan: Berdasarkan prinsip induksi, kita telah membuktikan pernyataan yang diminta.

REFERENSI:
  • Setya Budhi, Wono. 2003. Langkah Awal Menuju ke Olimpiade Matematika. Jakarta: CV Ricardo. (hal.: 59-64)
  • Raji, Wissam. “An Introductory Course in Elementary Number Theory.” Ebook.

Berlangganan Update Artikel Terbaru

0 Response to "Cara Mengerjakan Soal Induksi Matematika"

Post a Comment

Iklan Atas Artikel

Iklan Tengah Artikel 1

Iklan Tengah Artikel 2

Iklan Bawah Artikel

Searching of Online Shop