Metoda Pembuktian: Induksi Matematika

Julan HERNADI1

Program Studi Pendidikan Matematika

Universitas Muhammadiyah, Ponorogo

January 14, 2011

Julan HERNADI Induksi Matematika

ILUSTRASI

Figure: Ilustrasi Induksi

Julan HERNADI Induksi Matematika

Reaksi Berantai

Pada ilustrasi di atas, kartu-kartu disusun dalam jarak tertentu.

Agar terjadi reaksi berantai, yaitu jatuhnya sebuah kartu akan

menyebabkan robohkan kartu-kartu setelahnya maka haruslah

memenuhi syarat berikut

Minimal 1 kartu didorong sampai roboh

Tinggi kartu tidak kurang dari jarak antar kartu, yaitu x < h.

Julan HERNADI Induksi Matematika

Fungsi proposisi dengan domain N

Misalkan P(n) fungsi proposisi dengan n N0 N: himpunanbilangan asli.

Example

P(n): n2 2n. Perhatikan P(2), P(3) dan P(4) TRUE, tetapiP(n) FALSE untuk n lainnya. Kes: P(n) tidak bernilai benar untuksetiap bil asli n.

Perhatikan contoh berikut ini.

Example

P(n) : 1+2+ +n = n2(n+1). Coba periksa

P(1), P(2), P(3), semua bernilai TRUE. Bagaimana kita dapatmenyimpulkan bahwa P(n) TRUE untuk semua n N ? Tidakmungkin dicoba satu per satu untuk semua bil asli.

Julan HERNADI Induksi Matematika

Prinsip Induksi Matematika (PIM)

Jika

P(n0) TRUE untuk suatu bilangan asli n0 N.P(k) TRUE untuk sebarang k n0P(k+1) TRUE

maka P(n) TRUE untuk setiap n n0.

Example

Buktikan 1+2+ +n = n2(n+1) berlaku untuk setiap bil asli n.

Proof.

Di sini kita mempunyai P(n) : 1+2+ +n = n2(n+1)

n = 1 P(1) : 1= 12(1+1) 1= 1 sehingga P(1) true.

Asumsikan P(k) : 1+2+ +k = k2(k+1) true. Untuk

n = k+1,

Julan HERNADI Induksi Matematika

Lanj...

P(k+1) : 1+2+ +k k

2(k+1)

+(k+1) =k

2(k+1)+(k+1)

=(k+1)

2(k+1),

yaitu P(k+1) True. Kesimpulan: P(n) benar untuk setiap bil asli n.Perhatikan ketika membuktikan P(k+1) salah satu ruas, mis ruaskiri dijabarkan sehingga sama dengan ruas kanan.

Example

Buktikan bahwa untuk setiap bil asli n, berlaku

1(1!)+2(2!)+ +n(n!) = (n+1)!1

Julan HERNADI Induksi Matematika

Lanj

P(n) : 1(1!)+2(2!)+ +n(n!) = (n+1)!1. Untuk n = 1, ruaskiri = 1(1!) = 1, dan ruas kanan= (1+1)!1= 1. Krn kedua ruassama maka P(1) true. Skrg, asumsikan P(k) true untuk seb k ;yaitu kita mempunyai

1(1!)+2(2!)+ +k(k!) = (k+1)!1

Untuk n = k+1, kita tunjukkan bahwa P(k+1) true.

Ruas kiri = 1(1!)+2(2!)+ +k(k!) (k+1)!1

+(k+1)(k+1)!

= (k+1)!1+(k+1)(k+1)!= (k+1)!(1+k+1)1= (k+1)!(k+2)1= (k+2)!1= Ruas kanan

Julan HERNADI Induksi Matematika

Prinsip Induksi Kuat

Jika

P(1) true

P(1),P(2), ,P(k) true P(k+1) truemaka P(n) true untuk setiap bil asli n.

Example

Diberikan barisan yang didenisikan secara rekursif

x1 : = 1,x2 := 2,

xn+1 : =1

2(xn+ xn1) untuk n > 1

Buktikan 1 xn 2 untuk setiap bil asli n.

Julan HERNADI Induksi Matematika

Bukti ...

Proof.

Di sini P(n) : 1 xn 2. Untuk n = 1, diperoleh x1 = 1 sehinggaP(1) true. Selanjutnya diasumsikan P(1), P(2), , P(k) semuanyatrue, yaitu 1 xn 2 untuk n = 1,2, , n. Untuk n = k+1diperoleh

2 xk + xk1 4 11

2(xk + xk1) 2 1 xk+1 2

yaitu berlaku P(k+1).

Julan HERNADI Induksi Matematika

Soal Latihan

1 Buktikan 7n1 selalu habis dibagi 6 untuk setiap bil asli n.2 Buktikan jika x >1maka berlaku (1+ x)n 1+nx untuk

setiap bil asli n.

3 Buktikan 11.2 +

12.3 + ...+

1n(n+1) =

n

n+1 untuk setiap bil asli n.

4 Buktikan bahwa

1222+32+ ...+(1)n+1n2 = (1)n+1 n(n+1)2

untuk setiap

bil asli n.

5 Berikan konjektur untuk rumus jumlah dari113 +

135 + +

1(2n1)(2n+1) , kemudian buktikan konjektur tsb

dengan induksi matematika.

6 Buktikan 2n < n! untuk setiap n 4.7 Buktikan 2n3 2n2 untuk setiap n 5.8 Temukan bil asli terbesar m sehingga n3n dapat dibagi oleh

m untuk setiap bil asli n.

Julan HERNADI Induksi Matematika

Bukti Ekuvalensi (Dua arah)

To prove a theorem that is a biconditional statement, that is, a

statement of the form p q, we show that p q and q p areboth true. The validity of this approach is based on the tautology

(p q) [(p q) (q p)] .

When we prove that a group of statements are equivalent, we can

establish any chain of conditional statements we choose as long as

it is possible to work through the chain to go from anyone of these

statements to any other statement. For example, we can show that

p1,p2 and p3 are equivalent by showing that p1 p3, p3 p2, andp2 p1.

Julan HERNADI Induksi Matematika

Contoh...

Example

Buktikan Teorema jika n bulat positif, maka n ganjil bila hanya

bila n2ganjil.

Proof.

Diketahui n bulat positif. Mis p : n ganjildan q : n2 ganjil".Pertama, dibuktikan p q. Diketahui n ganjil, yaitu dapat ditulisn = 2k1, k N. Diperolehn2 = (2k1)2 = 4k24k+1= 2(2k22k)

m

+1 adalah ganjil.

Sebaliknya dibuktikan q p, yaitu n2 ganjil n ganjil. Ini dapatdibuktikan via kontraposisinya, yaitu n genap n2 genap. Tulisn = 2m maka diperoleh n2 = 4m2 juga genap. Terbukti p q.

Julan HERNADI Induksi Matematika

Contoh Lanj . . .

Example

Buktikan p1 p2 p3 dimanap1 : n genap, p2 : n1 ganjil" dan p3 : n2 genap.

Proof.

Cukup ditunjukkan dengan rute sbb: p1 p2, p2 p3 danp3 p1. Atau dengan menggunakan rute lainnya. Prinsipnya,subrute mudah dibuktikan dan semua terminal terakses. Terminal

yang dimaksud adalah pernyataan.

Julan HERNADI Induksi Matematika

Soal Latihan

1 Buktikan suatu bil bulat positif habis dibagi 9 bila hanya bila

jumlah angka-angka pembangunnya habis dibagi 9.2 Prove that m2 = n2 if and only if m = n or m =n.3 Show that these statements about the real number x are

equivalent:

1 x is rational,2 x/2 is rational, and3 3x1 is rational.

4 Show that these statements about the real number x are

equivalent:

1 x is irrational,2 3x+2 is irrational,3 x/2 is irrational.

5 Prove that these four statements about the integer n are

equivalent: (i) n2 is odd, (ii) 1n is even, (iii) n3 is odd, (iv)n2+1 is even.

Julan HERNADI Induksi Matematika