Induksi Matematika

Induksi Matematika. Suatu proses berpikir induktif (berpola dari khusus ke umum) dilakukan dengan cara diawali dari premis-premis yang benar (dibuktikan atau diandaikan benar) kemudian ditarik sebuah kesimpulan yang berlaku umum (bersifat menggeneralisasi).

Banyak soal-soal matematika pembuktian yang dikerjakan dengan induksi matematika, yang dimaksud soal induksi matematika adalah soal pembuktian terhadap pernyataan-pernyataan dalam bentuk n dimana n bilangan asli. Kita misalkan pernyataan dalam n 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$ dengan prinsip-prinsip induksi matematika 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.

Posting Komentar untuk "Induksi Matematika"


Jangan Lewatkan Kaos Matematika Keren & Unik di👇



Dapatkan panduan Belajar Matematika dari Nol GRATIS di👇