Matematika Diskrit 02

MATEMATIKA DISKRIT (Catatan Kuliah 07 November 2009 )

INDUKSI MATEMATIKA Induksi Matematika adalah membuat kesimpulan umum dari kesimpulan khusus Rumus : (a) 1 + 3 + ... + (2m – 1) = m2 (b) 2 + 4 + ... + 2m = m (m+1) Bukti : (a) 1 + 3 + ... + (2m – 1) = m2 Dibuktikan dengan cara induksi Matematika 1. Periksa untuk m = 1 1 = 12 = 1 Pernyataan benar 2. Andaikan peryataan benar untuk m = k 1 = 3 + ... + (2k – 1) = k2 3. Periksa pernyataan untuk m = k + 1 1 + 3 + ... + {2 (k + 1) – 1 } = ( k + 1)2 ? 1 + 3 + 5 + 7 + ... + (2k – 1) + { 2 (k + 1) – 1 } = (k + 1) 2 ? K2 + ( 2k – 1 ) = (k + 1) 2 ? (k + 1) 2 = (k + 1) 2 Pernyatan benar untuk m = k + 1 ⇒

Pernyataan benar

Rumus untuk semua bilangan asli : 1 + 3 + ... + ( 2m – 1 ) = m2 Simbol-simbol Matematika : ∀ = Setiap ∃ = Ada ) = Sehingga ∈ = Anggota

⇒ = Maka ⇔ = Jika dan hanya jika R = Kumpulan bilangan Real

Contoh : 1). 1 + 3 + 5 + 7 + ... + 999 = 5002 = 250000 Cara : Cari dulu M 2M – 1 = 999 2M = 1000 M = 500 Page 1 of 6

www.joshaxis.co.cc

MATEMATIKA DISKRIT (Catatan Kuliah 07 November 2009 )

2). 1 + 3 + 5 + ... + 999999 = 5000002 = 250000000000 Cara : Cari dulu M 2M – 1 = 999999 2M = 1000000 M = 500000

Segitiga Pascal : (a + b)1 = a + b

1 1 1 4

1 1 1

6

3

15

10 20

(a + b)3 = a3 + 3a2b + 3ab2 + b3

1 4

6 10

5

1

2 3

1

(a + b)2 = a2 + 2ab + b2

1

1

5 15

(1 + b)4 = a4 + 4a3b + b a2b2 + 4ab3 + b4

1 6

dst...

1

1=1 ⎛ 1⎞ 1 1⎜1 − ⎟ = ⎝ 2⎠ 2

⎛ 1 ⎞⎛ 1 ⎞ 1 2 1 1⎜1 − ⎟⎜1 − ⎟ = ⋅ = ⎝ 2 ⎠⎝ 2 ⎠ 2 3 3 ⎛ 1 ⎞⎛ 1 ⎞⎛ 1 ⎞ 1 3 1 1⎜1 − ⎟⎜1 − ⎟⎜1 − ⎟ = ⋅ = ⎝ 2 ⎠⎝ 3 ⎠⎝ 4 ⎠ 3 4 4 1 ⎞ 1 ⎛ 1 ⎞⎛ 1 ⎞⎛ 1 ⎞ ⎛ ? 1⎜1 − ⎟⎜1 − ⎟⎜1 − ⎟ K ⎜1 − ⎟= ⎝ 2 ⎠⎝ 3 ⎠⎝ 4 ⎠ ⎝ 1000 ⎠ 1000

Buktikan : 1 ⎞ 1 ⎛ 1 ⎞⎛ 1 ⎞ ⎛ 1⎜1 − ⎟⎜1 − ⎟ K ⎜1 − ⎟ = ⎝ 2 ⎠⎝ 3 ⎠ ⎝ M ⎠ M

Page 2 of 6

www.joshaxis.co.cc

MATEMATIKA DISKRIT (Catatan Kuliah 07 November 2009 )

Langkah : i) Periksa untuk M = 1 1 1 = = 1 Pernyataan benar 1

Kalau misalnya M = 2 ⎛ 1⎞ 1 1⎜1 − ⎟ = ⎝ 2⎠ 2

Kalau misalnya M = 3 ⎛ 1 ⎞⎛ 1 ⎞ 1 1⎜1 − ⎟⎜1 − ⎟ = ⎝ 3 ⎠⎝ 3 ⎠ 3

1 1 = 2 2

ii) Andaikan pernyataan benar untuk M = k Periksa pernyataan untuk M = k + 1

1 ⎞ 1 ⎛ 1 ⎞⎛ 1 ⎞ ⎛ 1⎜1 − ⎟⎜1 − ⎟L⎜1 − ⎟= ? ⎝ 2 ⎠⎝ 3 ⎠ ⎝ k + 1 ⎠ k + 1 1 ⎞ 1 ⎛ 1 ⎞⎛ 1 ⎞ ⎛ 1 ⎞⎛ ? 1⎜1 − ⎟⎜1 − ⎟ L ⎜1 − ⎟⎜1 − ⎟= ⎝ 2 ⎠⎝ 3 ⎠ ⎝ k ⎠⎝ k + 1 ⎠ k + 1 1⎛ 1 ⎞ 1 ? ⎜1 − ⎟= k ⎝ k +1⎠ k +1 1 ⎛ (k + 1) − 1 ⎞ 1 ? ⎟= ⎜ k ⎝ k +1 ⎠ k +1 1⎛ k ⎞ 1 ? ⎜ ⎟= k ⎝ k +1⎠ k +1

Pernyataan tersebut benar untuk ∀ M bilangan asli 1 ⎛ 1 ⎞⎛ 1 ⎞ ⎛ 1⎜1 − ⎟⎜1 − ⎟ K ⎜1 − ⎝ 2 ⎠⎝ 3 ⎠ ⎝ M

Page 3 of 6

⎞ 1 ⎟= ⎠ M

www.joshaxis.co.cc

MATEMATIKA DISKRIT (Catatan Kuliah 07 November 2009 )

(b) 2 + 4 + ... + 2m = m (m+1) Dibuktikan dengan cara induksi Matematika 1. Periksa untuk m = 1 2 = 1(1 + 1) = 2 Pernyataan benar 2. Andaikan peryataan benar untuk m = k 2 + 4 + ... + 2k = k(k + 1) 3. Periksa pernyataan untuk m = k + 1 2 + 4 + ... + 2 (k + 1) = ( k + 1) (k + 2) ?

2 + 4 + 6 + ... + 2k + 2 (k + 1) = (k + 1) (k + 2) ?

k ( k + 1) + 2(k + 1) = (k + 1) (k + 2) ? (k + 1) ( k + 2) = (k + 1) (k + 2) Pernyatan benar untuk m = k Rumus untuk semua bilangan asli :

⇒

Pernyataan benar

2 + 4 + ... + 2m = m (m+1) Contoh : 1). 2 + 4 + 6 + ... + 100 = 50 . 51 = 2550 Cara : Cari dulu M 2M = 100 M = 50

2). 2 + 4 + 6 + ... + 1000000 = 500000 . 500001 = 250000500000 Cara : Cari dulu M 2M – 1 = 999999 2M = 1000000 M = 500000

Page 4 of 6

www.joshaxis.co.cc

MATEMATIKA DISKRIT (Catatan Kuliah 07 November 2009 )

TUGAS : Coba periksa arithmetic komputer Anda dengan cara menghitung : 1⎞ ⎛ 1 ⎞⎛ 1 ⎞ ⎛ 1. ⎜1 − ⎟⎜1 − ⎟ L ⎜1 − ⎟ ⎝ 2 ⎠⎝ 3 ⎠ ⎝ m ⎠ 2.

1 + 3 + 5 + L + (2m − 1)

(Beri nilai m sebesar mungkin) Flowchart untuk menghitung : 1.

1⎞ ⎛ 1 ⎞⎛ 1 ⎞ ⎛ ⎜1 − ⎟⎜1 − ⎟ L ⎜1 − ⎟ ⎝ 2 ⎠⎝ 3 ⎠ ⎝ m ⎠

Simbol – simbol Flowchart : = Terminal

Start

= i/o input/ output N, s = 1, m=2

= decision (pilihan) 1⎞ ⎛ S = S ⎜1 − ⎟ ⎝ m⎠

m≥n

ya

= proses

tidak

m=m+1

Misalnya : S =

S=

1 2 1 ⋅ = 2 3 3

S=

1 1 1 ⋅ = 3 4 4

1 2

Hasilnya = S

Stop

N = 1000000

S=

1 1000000

= 0,0000009

Page 5 of 6

www.joshaxis.co.cc

MATEMATIKA DISKRIT (Catatan Kuliah 07 November 2009 )

2.

1 + 3 + 5 + L + (2m − 1) = S (Disini nilai N harus ganjil) Misalnya : S = 1 S=1+3=4 =4+5=9 = 9 + 7 = 16

Start

n, m = 1

Misalnya : n = 7 S=1 =1+3=4 =4+5=9 = 9 + 7 = 16

s=s+m

m≥n

S = 16

tidak

m=m+2

ya Hasilnya = s

Stop

[ Terima kasih \

Page 6 of 6

www.joshaxis.co.cc