Induksi matematika adalah suatu metode pembuktian yang banyak
digunakan
dalam buku ini. Metode ini digunakan untuk membuktikan kebenaran suatu pernyataan yang berkenaan dengan himpunan bilangan asli. Dalam bagian ini akan disajikan prinsip induksi matematika dan beberapa variasinya. Beberapa contoh juga akan diberikan untuk menjelaskan penggunaan induksi matematika dalam membu-ktikan
suatu pernyataan.
Teorema 1.3.1 (Sifat Terurut dengan Baik pada N) Setiap himpunan bagian takkosong dari N
mempunyai unsur terkecil.
Sifat Terurut dengan Baik pada N secara ringkas dapat dinyatakan sebagai berikut. Jika S Í N, S ¹ Æ, maka ada m Î S sehingga m £ s, untuk setiap s Î S.
Sifat ini seringkali dianggap sebagai postulat
atau aksioma yang berlaku pada N. Teorema 1.3.2 (Prinsip Induksi Matematika) Untuk masing-masing n Î N, misa- lkan P(n) adalah pernyataan yang berkaitan
dengan n. Jika
(a)
P(1) benar, dan
(b) P(k + 1) benar, jika P(k) benar, maka P(n) benar
untuk semua n Î N.
Bukti: Andaikan
hipotesis pada Teorema 1.3.2 benar tetapi kesimpulannya salah, yakni P(n) tidak benar untuk semua n
Î N. Berarti ada n Î N sehingga P(n) salah.
Misalkan
A = { k Î N
⏐ P(k) salah}. Jadi, A Í N dan A ¹ Æ. Sesuai sifat terurut
dengan baik, maka A mempunyai
unsur terkecil, sebut m. Karena P(1) benar, maka m > 1. Jadi, m – 1 Î N dan m – 1 < m. Karena m unsur terkecil di A, maka m – 1 Ï
A. Berarti P(m –1) benar. Sesuai hipotesis bagian (b), maka P(m) juga benar. Jadi, m
Ï A.
Terjadi kontradiksi. Terbukti bahwa P(n) benar
untuk semua n Î N.
Berikut ini beberapa contoh penggunaan induksi matematika untuk membuk- tikan pernyataan
yang berkaitan dengan himpunan
bilangan asli.
1.
Misalkan P(n)
adalah pernyataan
1 + 2 + 3 + ××× + n =
1 n(n + 1) ,
2
n Î N. Akan ditunjukan bahwa P(n) benar untuk semua n Î N. Untuk n = 1, maka P(1)
benar karena
1 = 1 ×1(1 +
1).
2
Untuk n =
k, asumsikan P(k)
benar. Artinya,
Maka diperoleh
1 + 2 + 3 + ××× + k =
1 k(k + 1).
2
1 + 2 + 3 + ××× + k + (k + 1) =
1 k(k + 1) +
(k + 1)
2
= 1 [k(k
+ 1) + 2(k + 1)]
2
= 1 (k + 1)(k +
2) 2= 1 (k + 1)[(k +
1) + 1).
2
Berarti, jika P(k) benar maka P(k + 1) juga benar. Sesuai prinsip induksi matematika, terbukti
1 + 2 + 3 + ××× + n =
berlaku untuk
semua n Î N.
1 n(n + 1) ,
2
2.
Misalkan P(n) adalah pernyataan n < 2n, untuk semua n Î N. Akan ditunjukkan bahwa P(n) benar untuk semua n Î N. Untuk n = 1, maka P(1) benar karena
1 < 21. Untuk n = k,
asumsikan P(k)
benar. Artinya, k < 2k.
Maka
diperoleh
k + 1 < 2k + 1 < 2k + 2k = 2(2k) = 2k + 1.
Jadi, jika P(k) benar maka P(k + 1) juga benar. Sesuai prinsip induksi matematika, terbukti n <
2n, benar untuk
semua n Î N.
3.
Misalkan P(n) adalah pernyataan n + 5 < n, untuk semua n Î N. Jika P(k) benar maka P(k + 1) juga benar, yaitu k + 5 < k maka
(k + 1) + 5 <
(k + 1).
Meskipun demikian, tidak dapat disimpulkan bahwa P(n) benar untuk semua n, karena untuk n = 1 ternyata P(1) salah. Dalam hal ini kondisi P(1) harus benar sangat
krusial.
Prinsip induksi matematika sering
juga dinyatakan dalam bentuk berikut.
Misalkan S Í N yang memenuhi sifat
(a)
1 Î S,
dan
(b)
Jika k Î S, maka k + 1 Î S, maka S = N.
Bentuk ini sama dengan bentuk pada
Teorema 1.3.2 dengan mendefinisikan
S = { n Î N ⏐ P(n) benar}.
Prinsip induksi
matematika juga digunakan untuk membuktikan kebenaran pernyataan yang dirumuskan secara rekursif. Misalkan f fungsi dari N ke R yang didefinisikan
sebagai berikut.
dan
Akan diperoleh bahwa
f(1) = 1,
f(n +
1) = (n + 1) f(n), untuk n Î N.
f(1) = 1,
f(2) = 2 f(1) = 2×1, f(3) = 3 f(2) = 3×2×1, f(4) = 4 f(3) = 4×3×2×1.
Berdasarkan pola tersebut diperoleh
dugaan bahwa
f(n) = n!,
n Î N.
Dugaan
ini benar untuk n = 1,
yakni
f(1) = 1 = 1!.
Asumsikan juga benar untuk n = k, yakni f(k) = k!. Maka untuk n = k + 1, diperoleh
f(k + 1) =
(k+1) f(k) = (k+1)k! = (k+1)!.
Sesuai prinsip induksi matematika, maka f(n) = n!, benar untuk
semua n Î N.
Meskipun pada
Teorema 1.3.2 dimulai dari n = 1, pernyataan akan
tetap berlaku jika dimulai dari sebarang bilangan
bulat no Î Z. Hal ini dinyatakan dalam teorema berikut.
Teorema 1.3.3 (Prinsip Induksi Matematika Dimodifikasi) Misalkan
no Î Z. Untuk masing-masing n Î Z, n ³ no, misalkan P(n) adalah pernyataan yang berkaitan de- ngan
n. Jika
(a) P(no) benar, dan
(b)
P(k + 1) benar, jika P(k) benar, k ³ no, maka P(n) benar untuk semua
n Î Z,
n ³ no.
Jika no = 1, maka Teorema 1.3.3 tidak lain adalah Teorema 1.3.2. Pembuktian Teorema
1.3.3 akan mudah dilakukan dengan Teorema 1.3.2 dengan menetapkan
Q(n) = P(no + n –1), n Î N,
yang tidak lain adalah pernyataan yang berkaitan dengan bilangan bulat positif. Penggunaan Teorema 1.3.3
dapat dilihat pada contoh berikut.
2n <
n!, untuk n Î
N, n ³ 4.
Untuk
n = 4, maka
24 = 16 < 24 =
4!
Berarti untuk n = 4, pernyataan tersebut benar.
Asumsikan pernyataan benar untuk n = k ³ 4, artinya 2k < k!. Diperoleh 2k + 1 =
2×2k < 2×k! <
(k + 1)×k! = (k + 1)!.
Berarti jika pernyataan benar untuk n = k ³ 4, maka pernyataan juga bernilai benar untuk
n
= k + 1. Dengan demikian
disimpulkan bahwa 2n < n!,
bernilai benar untuk semua n Î N,
n ³ 4.
Terdapat versi lain dari prinsip induksi matematika yang juga sangat berguna. Ada penulis yang menyebut versi ini dengan prinsip induksi matematika kedua (The Second Principle of Mathematical Induction) dan ada juga yang menyebut dengan prinsip induksi yang kuat (The Principle
of Strong Induction). Versi ini disajikan
dalam teorema berikut.
Teorema 1.3.4 (Prinsip Induksi yang Kuat) Untuk masing-masing n Î N,
misalkan P(n) adalah pernyataan
yang berkaitan dengan n. Jika
(a)
P(1) benar, dan
(b) Untuk k ³ 1, P(k + 1) benar, jika
P(j) benar untuk semua bilangan asli j £ k, maka P(n) benar untuk semua n Î N.
Prinsip Induksi yang Kuat ini dapat juga dinyatakan sebagai berikut.
Misalkan S himpunan bagian
dari N yang memenuhi sifat
(a)
1 Î S, dan
(b) (k + 1) Î S,
jika 1, 2, …, k Î S, maka S = N.
Berikut
ini contoh penggunaan Prinsip Induksi yang Kuat untuk membuktikan kebe-naran suatu
pernyataan yang berkaitan dengan bilangan asli.
Misalkan
f : N ® N yang didefinisikan sebagai berikut. f(1)=1, f(2)=2, dan
f(n) =
Akan
ditunjukkan bahwa 1 £ f(n) £ 2,
1 [f(n -
1) + f(n - 2)], untuk
semua n > 2.
2
untuk semua n Î N. Untuk n = 1, diperoleh bahwa
1 £ f(1) £ 2,
dan untuk
n
= 2, juga diperoleh
Untuk n = k ³ 1,
asumsikan bahwa
1 £ f(2) £ 2.
1 £ f(j) £ 2,
untuk
semua bilangan asli j £k.
Berarti bahwa
1£ f(k) £ 2
dan
Sehingga diperoleh
bahwa
1£ f(k -1) £ 2.
2 £ f(k) + f(k -
1) £ 4.
Jadi,
1 £ 1 [f(k) + f(k - 1)] £ 2.
2
Terbukti
bahwa jika 1 £ f(j) £ 2, untuk semua bilangan asli j
£ k,
k ³ 1, maka
1 £ f(k + 1) £ 2.
Sesuai Prinsip Induksi yang Kuat disimpulkan bahwa 1£ f(n) £ 2, untuk semua
n Î N.
Latihan 1. 3
1. Gunakan prinsip induksi
matematika untuk menunjukkan bahwa
masing- masing pernyataan berikut benar
untuk semua n Î N.
a. 1 + 2 + 3 + × × × + n =
n(n + 1) .
2
b. 1 + 3 + 5 + × × × +
(2n –
1) = n2.
c. 12 + 22 + 32 + × × × + n2 =
n(n + 1)( 2n + 1)
.
6
d. 13 + 23 + 33 + × × × + n3 =
⎡n(n + 1)⎤ 2
.
⎣⎢ 2 ⎥⎦
e. 2 + 22 + 23 + × × × + 2n = 2(2n –
1).
f. 1 +
1(2)
1
2(3)
+ L +
1 =
n(n + 1)
n .
n + 1
2.
Buktikan masing-masing pernyataan berikut
dengan induksi matematika.
a. 2n > n,
untuk semua n Î N.
b. 2n > n2, untuk semua n Î N dan n ³
5.
n 4
c. 13 + 23 + 33 + × × × + n3 <
, untuk semua n Î N dan n ³
3.
2
3.
Untuk masing-masing fungsi f dengan domain N berikut, tentukan rumus
untuk
f(n) dan buktikan kebenaran
rumus tersebut dengan induksi
matematika.
a. f(1) =
1 , dan f(n)
= (n - 1) f(n - 1) - 2
1
n + 1
,
untuk semua n >
1.
b. f(1) =
1, f(2) = 4, dan f(n) = 2f(n - 1) - f(n - 2)], untuk semua n > 2.
c. f(1) =
1, f(2)
= 2, dan f(n) = (n + 1) f(n - 1), untuk semua n > 1.
3n
d. f(1) =
1, f(2) = 0, dan f(n) =
f (n - 2) ,
untuk semua n > 2.
n(n - 1)
4.
Buktikan bahwa r + r2 + r3 + × × × + rn =
r (1 - r n
1 - r
) ,
r ¹ 1, untuk semua n Î N.
5.
Buktikan bahwa n < 2n
untuk setiap n Î N .
6.
Buktikan bahwa 2n < n ! untuk setiap n ³ 4 ,
n Î N .
7.
Misalkan S Ì N maka berlaku 2k Î S
untuk setiap k Î N
8.
Misalkan S Ì N
berlaku jika k Î S
maka k - 1Î S , Buktikan S = N .
No comments:
Post a Comment
you say