|
|
MATHEMATICAL
INDUCTION
Ini adalah
satu lagi jenis pembuktian yang sangat penting dalam matematik.
Saya
berada di bahagian akhir satu siri permainan dominoes. Setiap dominoes adalah
berjarak 2 inci dari jirannya yang lain, dan didepan dominoes ialah ‘pea
shooter’. Saya menembak ‘pea shooter’ pada dominoes yang pertama. Adakah semua
baris dominoes itu akan jatuh?
Ada dua
persoalan yang perlu ditanya disini: iaitu adakah ‘pea shooter’ itu mengenai
dominoes pertama itu dan adakah jarak antara
dominoes itu cukup untuk menyebabkan dominoes yang jatuh akan
menyebabkan dominoes yang lain juga jatuh ?
Teknik
yang penting dalam pembuktian matematik adalah bergantung kepada dua idea ini:
1.
Bolehkah
anda mendapatkan peringkat petama itu?
2.
Bolehkah
anda mendapatkan dari sebarang peringkat untuk
ke peringkat seterusnya?
Contoh 1
Berikut
adalah beberapa pernyataan dengan
beberapa bukti sebagai sokongan:
(a)
12
+ 22 + 32 + ... + n2 = 1 {n(n+1)(2n+1) }
6
Pernyataan di atas adalah benar untuk n = 1, n = 2 dan n = 3.
(b)
n2
³ 2n – 1
Kita boleh semak dengan mudah bahawa pernyataan di atas adalah
benar untuk n = 1, n = 2, n = 3.
(c)
1 + 2
+ 3 ... + n = 1 { n( n + 1 ) }
2
Pernyataan ini juga benar bila n =1, 2 atau 3.
Yang manakah dari
3 pernyataan di atas adalah benar untuk semua nilai n? Berapakah banyak nilai n
yang diperlukan untuk menyemaknya? Sebenarnya contoh (a) dan (c) adalah benar
untuk semua integer n tetapi contoh (b) adalah palsu untuk n ³ 7.
Pertimbangkan
contoh 1(a). Andaikan kita tahu untuk sebarang nilai n yang tertentu,
12 + 22 + 32 + . . . + n2 = 1 {n(n+1)(2n+1) }
................. (1)
6
Apakah
yang boleh kita katakan tentang
12 + 22 + 32 + . . . + n2 + ( n + 1 )2 ? jika kita tambahkan kedua-dua belah
persamaan (1) dengan ( n + 1 )2 kita akan dapat
12 + 22 + 32
+ . . . + n2 + ( n + 1 )2 = 1
{n(n+1)(2n+1) } +
( n + 1 )2
6
=
1 ( n + 1 ) {n(2n + 1) + 6(n + 1) }
6
=
1 (n + 1)(2n2 + 7n + 6)
6
=
1 (n + 1)(n + 2)(2n + 3)
6
=
1 (n + 1) {(n + 1) + 1 }{2 (n + 1) + 1 }
6
Jadi ,
12 + 22 + 32
+ . . . + n2 + ( n + 1 )2 = 1 (n + 1) {(n + 1) + 1 }{2 (n + 1) + 1 }
6
dimana adalah sama dengan persamaan (1) di atas, tetapi dengan (n+1) menggantikan tempat n. Jadi sekarang kita telah tunjukkan bahawa jika pernyataan itu benar untuk n maka ia juga adalah benar untuk (n + 1). Tetapi kita juga tahu bahawa ia adalah benar untuk 3 maka ia juga mestilah benar untuk 4. Jika ia benar untuk 4, maka ia mestilah juga benar untuk 5, ...., dan seterusnya.
THE
PRINCIPLE OF MATHEMATICAL INDUCTION
Untuk
setiap integer positif n, katakan P(n) adalah suatu pernyataan yang boleh jadi
benar atau palsu. Andaikan bahawa
(i)
P(1)
adalah benar
(ii)
Untuk
semua integer positif n, jika P(n) adalah benar maka
P(n + 1)
juga adalah benar.
Maka, P(n)
adalah benar untuk semua n ³ 1 .
Syarat (i)
di atas adalah dipanggil ‘ the basis for the induction’ dan syarat (ii)
pula dipanggil ‘inductive step’.
Contoh 2
Tunjukkan
bahawa, untuk sebarang integer n ³ 1,
1 + 2 + 3 + 4 + . . .
+ n = 1 n(n + 1)
2
Penyelesaian:
Kita akan
buktikan dengan menggunakan prinsip induksi matematik.
Katakan
P(n) adalah suatu usulan
1 + 2 + 3 + 4 + . . .
+ n = 1 n(n + 1)
2
(i)
P(1)
bermakna 1 = 1 (1)(1 + 1). Ini adalah benar dan kita telah
2
tunjukkan ‘the basis for the induction’.
(ii)
Jika
P(n) adalah benar maka
1 + 2 + . . . +
n = 1 n(n + 1), dan
dengan menambahkan (n + 1) untuk
2
kedua-dua
belah persamaan ini kita akan dapat
1 + 2 + . . . + n + n + 1 =
1 n(n + 1) + (n + 1)
2
= (n + 1)( 1 n + 1)
2
= (n + 1) {1 (n + 2) }
2
= 1 (n + 1)(n + 2)
2
Oleh itu
P(n +1) adalah benar. Kita telah tunjukkan ‘the inductive step’.