Minggu, 06 Desember 2015

Materi Olimpiade SMP : Bab 6 Teori Bilangan [Intermediate] : Induksi Matematika

Materi sebelumnya : Materi Olimpiade SMP : Bab 5 Teori Bilangan [Basic] : Persamaan Kongruensi

Induksi matematika merupakan pembuktian deduktid, meskipun namanya induksi. Induksi matematika atau disebut juga induksi lengkap sering dipergunakan untuk pernyataan - pernyataan yang menyangkut bilangan asli

Pembuktian cara induksi matematika ingin membuktikan bahwa teori atau sifat itu benar untuk semua bilangan asli atau semua bilangan dalam himpunan bagiannya. Caranya ialah dngan menunjukkan bahwa sifat itu benar untuk $n = 1$ (atau $S(1)$ adalah benar), kemudian ditunjukkan bahwa bila sifat itu itu benar untuk $n = k$ (bila $S(k)$ benar ) menyebabkan sifat itu benar untuk $n = k + 1$ ($S(k+1)$ benar)


Prinsip Induksi Matematika Pertama
Misalkan ${P(n) : n \in \mathbb{N}}$ kumpulan pernyataan $P(n)$ yang bergantung pada bilangan asli $n$. Jika

  • $P(1)$ benar dan
  • jika $P(k)$ benar, mengakibatkan bahwa $P(k + 1)$ juga benar
maka pernyataan $P(n)$ benar untuk setiap $n$


Prinsip Induksi Matematika Kedua

Misalkan $n_0 \in \mathbb{N}$ dan ${P(n) : n \in \mathbb{N}}$ kumpulan pernyataan $P(n)$ yang bergantung pada bilangan asli $n$. Jika

  • $P(n_0)$ benar dan
  • untuk setiap $k \ge n_0$, jika $P(k)$ benar, mengakibatkan bahwa $P(k + 1)$ juga benar
maka pernyataan $P(n)$ benar untuk setiap $n \ge n_0$


Prinsip Induksi Matematika Ketiga (Induksi Kuat)

Misalkan ${P(n) : n \in \mathbb{N}}$ kumpulan pernyataan $P(n)$ yang bergantung pada bilangan asli $n$. Jika

  • $P(1)$ benar dan
  • jika $P(m)$ benar untuk setiap $m \le k$, mengakibatkan bahwa $P(k + 1)$ juga benar
maka pernyataan $P(n)$ benar untuk setiap $n$


Untuk lebih handal dalam menyelesaikan soal - soal yang berkaitan dengan induksi matematika, berikut soal - soal beserta solusi mengenai topik ini

Soal 1
Buktikan bahwa $1^2 + 2^2 + \ldots + n^2 = \frac{n(n+1)(2n + 1)}{6}$ benar untuk semua bilangan asli $n$

Solusi
Dengan menggunakan induksi matematika akan kita buktikan 2 pernyataan pada induksi matematika.

1. Untuk $n = 1$ perhatikan bahwa $1^2 = \frac{1\times2\times3}{6} = 1^2$. Jadi, $P(1)$ benar

2. Asumsikan $P(k)$ benar, yaitu $1^2 + 2^2 + \ldots + k^2 = \frac{k(k+1)(2k+1)}{6}$, akan dibuktikan bahwa $P(k+1)$ juga benar. Perhatikan bahwa

\[ 1^2 + 2^2 + \ldots + k^2 + (k+1)^2 = (1^2 + 2^2 + \ldots + k^2) + (k+1)^2 \]
\[= \frac{k(k+1)(2k+1)}{6} + (k+1)^2 = (k + 1) \left( \frac{k(2k+1)}{6} + k + 1  \right) = (k+1)  \left( \frac{2k^2 + 7k + 6}{6}\right) \]
\[= (k + 1) \left( \frac{(k+2)(2k + 3)}{6}  \right) =  \frac{(k + 1)((k+1) + 1)(2(k+1) + 1)}{6} \]

Jadi pernyataan benar untuk $P(k+1)$. Sehingga, dapat disimpulkan bahwa untuk semua bilangan asli $n$ berlaku  $1^2 + 2^2 + \ldots + n^2 = \frac{n(n+1)(2n + 1)}{6}$ 


Soal 2
Buktikan bahwa $(6 + \sqrt{7})^n + (6 - \sqrt{7})^n$ selalu merupakan bilangan bulat untuk semua $n \in \mathbb{N}$

Solusi
Dengan menggunakan prinsip induksi matematika ketiga, akan kita buktikan 2 pernyataan yang ada pada prinsip tersebut

1. Perhatikan bahwa untuk $n = 1$, nilai dari  $(6 + \sqrt{7})^1 + (6 - \sqrt{7})^1 = 12$ merupakan bilangan bulat. Jadi, $P(1)$ benar

Perhatikan bahwa untuk $n = 2$, nilai dari  $(6 + \sqrt{7})^2 + (6 - \sqrt{7})^2 = 86$ merupakan bilangan bulat. Jadi, $P(2)$ benar

2. Asumsikan benar bahwa $(6 + \sqrt{7})^n + (6 - \sqrt{7})^n$ untuk semua $n \le k$. Akan dibuktikan bahwa  $(6 + \sqrt{7})^{k+1} + (6 - \sqrt{7})^{k+1}$ benar.

Perhatikan bahwa $ a^{k+1} + b^{k+1} = (a^k + b^k)(a + b) - ab(a^{k-1} + b^{k-1})$. Untuk $a = 6 + \sqrt{7}$ dan $b = 6 - \sqrt{7}$ diperoleh bahwa $a + b = 12$ dan $ab = 29$. Sehingga, 

\[ (6 + \sqrt{7})^{k+1} + (6 - \sqrt{7})^{k+1}  = 12((6 + \sqrt{7})^k + (6 - \sqrt{7})^k) - 29((6 + \sqrt{7})^{k-1} + (6 - \sqrt{7})^{k-1})  \]

Karena $(6 + \sqrt{7})^k + (6 - \sqrt{7})^k$ dan $(6 + \sqrt{7})^{k-1} + (6 - \sqrt{7})^{k-1}$ bulat, haruslah $(6 + \sqrt{7})^{k+1} + (6 - \sqrt{7})^{k+1}$ juga bilangan bulat. Jadi benar bahwa $(6 + \sqrt{7})^{k+1} + (6 - \sqrt{7})^{k+1}$ merupakan bilangan bulat

Jadi, dapat disimpulkan bahwa $(6 + \sqrt{7})^n + (6 - \sqrt{7})^n$ selalu merupakan bilangan bulat untuk semua $n \in \mathbb{N}$


Soal 3
Buktikan bahwa untuk setiap bilangan asli $n$ berlaku \[ \frac{1}{1^2} + \frac{1}{2^2} + \ldots + \frac{1}{n^2} \le 2 - \frac{1}{n} \]
Solusi
Dengan menggunakan prinsip induksi matematika 1

1. Perhatikan bahwa saat $n = 1$, benar bahwa $\frac{1}{1^2} = 1 \le 2 - \frac{1}{1^2}$. Jadi, $P(1)$ benar

2. Asumsikan untuk $n = k$, $P(k)$ benar yaitu  $\frac{1}{1^2} + \frac{1}{2^2} + \ldots + \frac{1}{k^2} \le 2 - \frac{1}{k}$. Akan dibuktikan bahwa $P(k+1)$ benar. Perhatikan bahwa

\[ \frac{1}{1^2} + \frac{1}{2^2} + \ldots + \frac{1}{k^2} + \frac{1}{(k+1)^2} \le 2 - \frac{1}{k} + \frac{1}{(k+1)^2} \le 2 - \frac{1}{k} + \frac{1}{k(k+1)} = 2 - \frac{1}{k+1} \]

Jadi $P(k+1)$ benar. Sehingga, dapat disimpulkan bahwa untuk setiap bilangan asli $n$ berlaku \[ \frac{1}{1^2} + \frac{1}{2^2} + \ldots + \frac{1}{n^2} \le 2 - \frac{1}{n} \]

Soal 4
Misalkan $c_0, c_1, c_2, \ldots$ merupakan barisan yang didefinisikan sebagai 
  • $c_0 = 1$, $c_1 = 2$, $c_2 = 3$, dan
  • $c_n = c_{n-1} + c_{n-2} + c_{n-3}$ untuk semua $n \ge 3$
Buktikan bahwa $c_n \ge 3^n$

Solusi
Dengan menggunakan prinsip induksi matematika $3$,

1. Perhatikan bahwa $c_0 = 1 \le 3^0, c_1 = 2 \le 3^1$, dan $c_2 = 3 \le 3^2$. Jadi, $P(1), P(2)$, dan $P(3)$ benar.

2. Asumsikan untuk semua $n \le k$, pernyataan $P(n)$ benar, yaitu $c_n \le 3^n$ untuk semua $n \le k$. Akan dibuktikan bahwa $P(k + 1)$ benar. Perhatikan bahwa

\[ c_{k + 1} = c_k + c_{k-1} + c_{k-2} \le 3^k + 3^{k-1} + 3^{k-2} \le 3^k + 3^{k} + 3^{k} \le 3^{k+1} \]

Jadi $P(k + 1)$ benar. Sehingga dapat disimpulkan bahwa untuk semua bilangan asli $n$ berlaku $c_n \le 3^n$. 



Sebagai latihan untuk pembaca, berikut saya sertakan beberapa soal - soal berkaitan dengan induksi matematika

Latihan 1
Buktikan bahwa untuk setiap bilangan asli $n$ berlaku \[ 1 + 2 + 3 + \ldots + n = \frac{n(n+1)}{2} \]
Latihan 2
Buktikan bahwa untuk setiap bilangan asli $n$ berlaku \[ 1.2 + 2.3 + 3.4 + \ldots + n(n+1) = \frac{n(n+1)(n+2)}{3} \]
Latihan 3
Buktikan bahwa untuk setiap bilangan asli $n$ berlaku \[ \frac{1.2.3} + \frac{1}{2.3.4} + \frac{1}{3.4.5} + \ldots + \frac{1}{n(n+1)(n+2)} = \frac{n(n+3)}{4(n+1)(n+2)} \]
Latihan 4
Buktikan bahwa untuk setiap bilangan asli $n$ berlaku \[ \frac{1.4} + \frac{1}{4.7} + \ldots + \frac{1}{(3n-2)(3n+1)} = \frac{n}{3n + 1} \]
Latihan 5
Buktikan bahwa untuk setiap bilangan asli $n$, bilangan $(3 + \sqrt{5})^n + (3 - \sqrt{5})^n$ habis dibagi $2^n$

Latihan 6
Buktikan bahwa untuk setiap bilangan asli $n$, bilangan $(8 + 3\sqrt{7})^n + (8 - 3\sqrt{7})^n$ merupakan bilangan ganjil

Latihan 7
Buktikan bahwa untuk setiap bilangan asli $n$, bilangan $\frac{(2n)!}{2^n. n!}$ merupakan bilangan asli

Latihan 8
Buktikan bahwa untuk setiap bilangan asli $n \ge 5$ berlaku $2^n > n^2$

Latihan 9
Misalkan $c_0, c_1, c_2, \ldots$ merupakan barisan yang didefinisikan sebagai 
  • $c_0 = 1$, $c_1 = 4$, dan
  • $c_n = 6c_{n-1} - 5c_{n-2}$ untuk semua $n \ge 2$
Buktikan bahwa $c_n = 5^n - 1$ untuk semua bilangan asli $n$

Latihan 10
Misalkan $c_0, c_1, c_2, \ldots$ merupakan barisan yang didefinisikan sebagai 
  • $c_0 = 5$, $c_1 = 16$, dan
  • $c_n = 7c_{n-1} - 10c_{n-2}$ untuk semua $n \ge 2$
Buktikan bahwa $c_n = 3.2^n + 2.5^n$ untuk semua bilangan asli $n$

Latihan 11
Buktikan bahwa untuk setiap bilangan asli $n$, himpunan dengan $n$ anggota memiliki tepat $2^n$ himpunan bagian

Tidak ada komentar:

Posting Komentar