Cara Mengerjakan Soal Induksi Matematika
(Diperbarui:
)
-
Posting Komentar
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. Cara berpikir induksi dapat diilustrasikan melalui gambar di bawah ini.
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. Cara berpikir induksi dapat diilustrasikan melalui gambar di bawah ini.
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 pernyataan 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 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 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
Selanjutnya kita akan membuktikan bahwa
$(2+ \sqrt{3})^{k+1} + (2 – \sqrt{3})^{k+1}$
juga bilangan bulat.
Tetapi
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.
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.
TANYA JAWAB
Pertanyaan: Buktikan bahwa $1+3+5+...+2n-1=n^2$
Jawab:
Untuk $n=1$ maka $2(1)-1=1^2$ (benar).
Jika $n=k$ benar maka $n=k+1$ juga benar, yaitu:
$\begin{align} & 1+3+5+...+(2k-1) = k^2 \\ \Leftrightarrow & 1+3+5+...+(2k-1)+(2k+1) = k^2+(2k+1) \\ \Leftrightarrow & 1+3+5+...+(2k-1)+2(k+1)-1 = (k+1)^2 \end{align}$
TANYA JAWAB
Pertanyaan: Buktikan bahwa $1+3+5+...+2n-1=n^2$
Jawab:
Untuk $n=1$ maka $2(1)-1=1^2$ (benar).
Jika $n=k$ benar maka $n=k+1$ juga benar, yaitu:
$\begin{align} & 1+3+5+...+(2k-1) = k^2 \\ \Leftrightarrow & 1+3+5+...+(2k-1)+(2k+1) = k^2+(2k+1) \\ \Leftrightarrow & 1+3+5+...+(2k-1)+2(k+1)-1 = (k+1)^2 \end{align}$
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.
Langganan:
Posting Komentar (Atom)
Posting Komentar untuk "Cara Mengerjakan Soal Induksi Matematika"