Prinsip Induksi Matematis Kuat

Prinsip Induksi Matematis Kuat - Apakah kalian masih ingat dengan materi induksi matematika?

Prinsip Induksi Matematis Kuat

Materi tersebut telah kalian pelajari dalam topik sebelumnya. Perlu kalian ketahui, sebenarnya induksi matematika tidak selalu dapat digunakan untuk menentukan kebenaran dari suatu pernyataan yang berkaitan dengan bilangan asli. Atas dasar itulah, muncul suatu metode pembuktian yang disebut dengan induksi matematika kuat.

Sebagai ilustrasi, misalkan kita akan membuktikan pernyataan: untuk setiap bilangan asli n$n$, berlaku 1≤xn≤2$1\le x_n\le 2$, dimana x1=1$x_1=1$, x2=2$x_2=2$, dan xn+2=12(xn+1+xn)$x_{n+2}=\frac{1}{2}\left(x_{n+1}+x_n\right)$.

Basis Induksi:

Untuk n=1$n=1$, pernyataan bernilai benar, sebab 1≤1≤2⇔1≤x1≤2$1\le 1\le 2\iff 1\le x_1\le 2$.

Hipotesis Induksi:

Misalkan pernyataan bernilai benar untuk n=k$n=k$, yaitu 1≤xk≤2$1\le x_k\le 2$.

Pembuktian untuk n=k+1$n=k+1$:

Akan dibuktikan bahwa 1≤xk+1≤2$1\le x_{k+1}\le 2$ atau 1≤12(xk−1+xk)$1\le \frac{1}{2}\left(x_{k-1}+x_k\right)$ ≤ 2 %].

Nah, untuk membuktikan bahwa 1≤12(xk−1+xk)$1\le \frac{1}{2}\left(x_{k-1}+x_k\right)$ ≤ 2 %], kita perlu jaminan bahwa 1≤xk−1≤2$1\le x_{k-1}\le 2$. Dengan demikian, induksi matematika tidak dapat kita gunakan untuk membuktikan pernyataan tersebut.

Apa yang dapat kalian simpulkan dari ilustrasi di atas?

Ya, kita tidak dapat menggunakan induksi matematika jika dalam pembuktian tidak hanya kebenaran dari p(k)$p(k)$ saja yang diperlukan, tetapi juga kebenaran dari p(k−1)$p(k-1)$, bahkan mungkin kebenaran dari p(1)$p(1)$, p(2)$p(2)$, ... , dan p(k−2)$p(k-2)$.

Prinsip Induksi Kuat

Misalkan p(n)$p(n)$ adalah suatu pernyataan dimana kebenarannya ditentukan oleh nilai n$n$, dengan n$n$ adalah bilangan asli.

Nah, prinsip induksi kuat adalah sebagai berikut:

Prinsip Induksi Matematika Kuat yang Diperluas

Induksi matematis kuat juga dapat diperluas seperti halnya perluasan pada induksi matematika, yaitu bilangan asli n$n$ tidak lagi dimulai dari satu, melainkan dimulai dari m$m$, dimana m$m$ merupakan bilangan asli.

Misalkan p(n)$p(n)$ adalah suatu pernyataan yang bernilai benar untuk setiap bilangan asli n≥m$n\ge m$.

Nah, prinsip induksi kuat yang diperluas adalah sebagai berikut:

Apakah kalian sudah paham dengan penjelasan materi di atas?

Yuk kita cermati beberapa contoh berikut agar kalian semakin jelas.

Contoh 1

Barisan bilangan xn$x_n$ didefinisikan sebagai berikut:

• x1=1$x_1=1$
• x2=2$x_2=2$
• xn+2=12(xn+1+xn)$x_{n+2}=\frac{1}{2}\left(x_{n+1}+x_n\right)$ untuk setiap bilangan asli n≥2$n\ge 2$

Buktikan bahwa 1≤xn≤2$1\le x_n\le 2$ untuk setiap bilangan asli n$n$.

Pembuktian:

Berdasarkan informasi dalam soal, p(n):1≤xn≤2 $p(n):1\le x_n\le 2$ untuk setiap bilangan asli n$n$.

Langkah Dasar:

Untuk n=1$n=1$, pernyataan bernilai benar, sebab 1≤1≤2⇔1≤x1≤2$1\le 1\le 2\iff 1\le x_1\le 2$.

Langkah Induksi:

Untuk setiap bilangan asli k$k$, dimisalkan p(1)$p(1)$, p(2)$p(2)$, ..., p(k−1)$p(k-1)$, dan p(k)$p(k)$ bernilai benar. Akan dibuktikan bahwa p(k+1):1≤xk+1≤2 $p(k+1):1\le x_{k+1}\le 2$ juga bernilai benar.

Oleh karena p(k−1):1≤xk−1≤2$p(k-1):1\le x_{k-1}\le 2$ dan p(k):1≤xk≤2$p(k):1\le x_k\le 2$ bernilai benar, maka 2≤xk−1+xk≤4⇔1≤12(xk−1+xk)≤2⇔1≤
xk+1
≤2$2\le x_{k-1}+x_k\le 4\iff 1\le \frac{1}{2}$

$(x_{k-1}+x_k)\le 2\iff 1\le x_{k+1}\le 2$.

Dengan demikian, terbukti bahwa p(k+1):1≤xk+1≤2 $p(k+1):1\le x_{k+1}\le 2$ bernilai benar.

Kesimpulan:

Berdasarkan hasil yang diperoleh dari langkah dasar dan langkah induksi, maka dapat kita simpulkan bahwa p(n):1≤xn≤2 $p(n):1\le x_n\le 2$ bernilai benar untuk setiap bilangan asli n$n$.

Share this post