Lewati ke konten utama

Bagian 2.1 Induksi Matematis

Misalkan kita ingin menunjukkan bahwa
\begin{equation*} 1 + 2 + \cdots + n = \frac{n(n + 1)}{2} \end{equation*}
untuk setiap bilangan asli \(n\text{.}\) Rumus ini mudah diperiksa untuk bilangan-bilangan kecil seperti \(n = 1\text{,}\) \(2\text{,}\) \(3\text{,}\) atau \(4\text{,}\) tetapi mustahil memeriksanya satu per satu untuk semua bilangan asli. Untuk membuktikan bahwa rumus tersebut berlaku secara umum, diperlukan metode yang lebih umum.
Misalkan kita telah memeriksa persamaan tersebut untuk \(n\) kasus pertama. Kita akan menunjukkan bahwa dari pengetahuan ini kita dapat memperoleh rumus untuk kasus ke-\((n + 1)\text{.}\) Rumus tersebut benar untuk \(n = 1\) karena
\begin{equation*} 1 = \frac{1(1 + 1)}{2}\text{.} \end{equation*}
Jika kita telah memeriksa \(n\) kasus pertama, maka
\begin{align*} 1 + 2 + \cdots + n + (n + 1) & = \frac{n(n + 1)}{2} + n + 1\\ & = \frac{n^2 + 3n + 2}{2}\\ & = \frac{(n + 1)[(n + 1) + 1]}{2}\text{.} \end{align*}
Ini tepat merupakan rumus untuk kasus ke-\((n + 1)\text{.}\)
Metode pembuktian ini dikenal sebagai induksi matematis. Alih-alih mencoba memeriksa satu per satu suatu pernyataan mengenai himpunan bagian \(S\) dari bilangan bulat positif \({\mathbb N}\text{,}\) suatu tugas yang mustahil jika \(S\) merupakan himpunan tak hingga, kita memberikan bukti khusus untuk bilangan bulat terkecil yang sedang dipertimbangkan, diikuti argumen umum yang menunjukkan bahwa jika pernyataan itu berlaku untuk suatu kasus, maka pernyataan tersebut juga harus berlaku untuk kasus berikutnya dalam barisan. Induksi matematis dirangkum dalam aksioma berikut.

Contoh 2.1.2.

Untuk setiap bilangan bulat \(n \geq 3\text{,}\) berlaku \(2^n \gt n + 4\text{.}\) Karena
\begin{equation*} 8 = 2^3 \gt 3 + 4 = 7\text{,} \end{equation*}
pernyataan tersebut benar untuk \(n_0 = 3\text{.}\) Andaikan \(2^k \gt k + 4\) untuk \(k \geq 3\text{.}\) Maka \(2^{k + 1} = 2 \cdot 2^{k} \gt 2(k + 4)\text{.}\) Namun,
\begin{equation*} 2(k + 4) = 2k + 8 \gt k + 5 = (k + 1) + 4 \end{equation*}
karena \(k\) positif. Jadi, berdasarkan induksi, pernyataan tersebut berlaku untuk setiap bilangan bulat \(n \geq 3\text{.}\)

Contoh 2.1.3.

Setiap bilangan bulat \(10^{n + 1} + 3 \cdot 10^n + 5\) habis dibagi \(9\) untuk \(n \in {\mathbb N}\text{.}\) Untuk \(n = 1\text{,}\)
\begin{equation*} 10^{1 + 1} + 3 \cdot 10 + 5 = 135 = 9 \cdot 15 \end{equation*}
habis dibagi \(9\text{.}\) Misalkan \(10^{k + 1} + 3 \cdot 10^k + 5\) habis dibagi \(9\) untuk \(k \geq 1\text{.}\) Maka
\begin{align*} 10^{(k + 1) + 1} + 3 \cdot 10^{k + 1} + 5& = 10^{k + 2} + 3 \cdot 10^{k + 1} + 50 - 45\\ & = 10 (10^{k + 1} + 3 \cdot 10^{k} + 5) - 45 \end{align*}
habis dibagi \(9\text{.}\)

Contoh 2.1.4.

Kita akan membuktikan teorema binomial dengan induksi matematis; yaitu,
\begin{equation*} (a + b)^n = \sum_{k = 0}^{n} \binom{n}{k} a^k b^{n - k}\text{,} \end{equation*}
dengan \(a\) dan \(b\) bilangan real, \(n \in \mathbb{N}\text{,}\) dan
\begin{equation*} \binom{n}{k} = \frac{n!}{k! (n - k)!} \end{equation*}
merupakan koefisien binomial. Pertama-tama kita tunjukkan bahwa
\begin{equation*} \binom{n + 1}{k} = \binom{n}{k} + \binom{n}{k - 1}\text{.} \end{equation*}
Hasil ini diperoleh dari
\begin{align*} \binom{n}{k} + \binom{n}{k - 1} & = \frac{n!}{k!(n - k)!} +\frac{n!}{(k-1)!(n - k + 1)!}\\ & = \frac{(n + 1)!}{k!(n + 1 - k)!}\\ & =\binom{n + 1}{k}\text{.} \end{align*}
Jika \(n = 1\text{,}\) teorema binomial mudah diperiksa. Sekarang andaikan hasil tersebut benar untuk \(n\) yang lebih besar daripada atau sama dengan \(1\text{.}\) Maka
\begin{align*} (a + b)^{n + 1} & = (a + b)(a + b)^n\\ & = (a + b) \left( \sum_{k = 0}^{n} \binom{n}{k} a^k b^{n - k}\right)\\ & = \sum_{k = 0}^{n} \binom{n}{k} a^{k + 1} b^{n - k} + \sum_{k = 0}^{n} \binom{n}{k} a^k b^{n + 1 - k}\\ & = a^{n + 1} + \sum_{k = 1}^{n} \binom{n}{k - 1} a^{k} b^{n + 1 - k} + \sum_{k = 1}^{n} \binom{n}{k} a^k b^{n + 1 - k} + b^{n + 1}\\ & = a^{n + 1} + \sum_{k = 1}^{n} \left[ \binom{n}{k - 1} + \binom{n}{k} \right]a^k b^{n + 1 - k} + b^{n + 1}\\ & = \sum_{k = 0}^{n + 1} \binom{n + 1}{k} a^k b^{n + 1- k}\text{.} \end{align*}
Terdapat bentuk ekuivalen dari Prinsip Induksi Matematis yang sering kali sangat berguna.
Suatu himpunan bagian tak kosong \(S\) dari \({\mathbb Z}\) disebut terurut baik jika \(S\) memuat suatu elemen terkecil. Perhatikan bahwa himpunan \({\mathbb Z}\) tidak terurut baik karena tidak memuat elemen terkecil. Akan tetapi, bilangan asli terurut baik.
Prinsip Urutan Baik ekuivalen dengan Prinsip Induksi Matematis.

Bukti.
Misalkan \(S = \{ n \in {\mathbb N} : n \geq 1 \}\text{.}\) Maka \(1 \in S\text{.}\) Andaikan \(n \in S\text{.}\) Karena \(0 \lt 1\text{,}\) harus berlaku \(n = n + 0 \lt n + 1\text{.}\) Oleh karena itu, \(1 \leq n \lt n + 1\text{.}\) Akibatnya, jika \(n \in S\text{,}\) maka \(n + 1\) juga harus berada dalam \(S\text{,}\) dan berdasarkan Prinsip Induksi Matematis kita memperoleh \(S = \mathbb N\text{.}\)

Bukti.
Kita harus menunjukkan bahwa jika \(S\) merupakan himpunan bagian tak kosong dari bilangan asli, maka \(S\) memuat suatu elemen terkecil. Jika \(S\) memuat \(1\text{,}\) maka teorema ini benar berdasarkan Lema 2.1.7. Andaikan bahwa jika \(S\) memuat suatu bilangan bulat \(k\) sedemikian sehingga \(1 \leq k \leq n\text{,}\) maka \(S\) memuat suatu elemen terkecil. Kita akan menunjukkan bahwa jika suatu himpunan \(S\) memuat bilangan bulat yang lebih kecil daripada atau sama dengan \(n + 1\text{,}\) maka \(S\) mempunyai suatu elemen terkecil. Jika \(S\) tidak memuat bilangan bulat yang lebih kecil daripada \(n+1\text{,}\) maka \(n+1\) merupakan bilangan bulat terkecil dalam \(S\text{.}\) Jika tidak demikian, karena \(S\) tak kosong, \(S\) harus memuat bilangan bulat yang lebih kecil daripada atau sama dengan \(n\text{.}\) Dalam hal ini, berdasarkan induksi, \(S\) memuat suatu elemen terkecil.
Induksi juga dapat sangat berguna dalam merumuskan definisi. Sebagai contoh, ada dua cara untuk mendefinisikan \(n!\text{,}\) yaitu faktorial dari bilangan bulat positif \(n\text{.}\)
  • Definisi eksplisit: \(n! = 1 \cdot 2 \cdot 3 \cdots (n - 1) \cdot n\text{.}\)
  • Definisi induktif atau rekursif: \(1! = 1\) dan \(n! = n(n - 1)!\) untuk \(n \gt 1\text{.}\)
Setiap matematikawan atau ilmuwan komputer yang baik mengetahui bahwa memandang masalah secara rekursif, alih-alih secara eksplisit, sering kali menghasilkan pemahaman yang lebih baik terhadap persoalan rumit.
Sblm.Paling AtasLanjut