induksi matematika

BAB II

PEMBAHASAN

A.    Ide Awal Induksi Matematika

Induksi matematika (mathematical induction) adalah metode pembuktian yang sering digunakan untuk menentukan kebenaran dari suatu pernyataan yang diberikan dalam bentuk bilangan asli. Akan tetapi sebelum membahas mengenai induksi matematika, kita akan membahas suatu prinsip yang digunakan untuk membuktikan induksi matematika, yaitu prinsip terurut rapi (well-ordering principle) dari bilangan asli.

Induksi matematika adalah suatu teknik yang sederhana, kuat dan bagus untuk membuktikan berbagai pernyataan mengenai bilangan asli. Induksi matematika dikatakan sederhana karena pemikiran yang mendasarinya bersifat intuitif dan menarik, kuat karena penggunaannya yang luas, bagus karena menyajikan kerangka kerja yang sama atau seragam untuk mempelajari sifat-sifat bilangan asli.

Untuk lebih memahami induksi matematika, misalkan kita mempunyai lima anggota bilangan yaitu 10, 5, 7, 3, 6. Pada langkah pertama kita membandingkan 10 dan 5 bilangan yang kecil adalah 5, kemudian angka 5 dibandingkan dengan 7 diperoleh angka yang kecil adalah 5, 5 dibandingkan dengan angka ke empat yaitu 3 diperoleh angka yang kecil 3 selanjutnya angka 3 dibandingkan dengan 6 dan yang lebih kecil adalah 3. Dengan langkah ini bahwa 3 adalah bilangan terkecil dalam daftar tersebut. Pada langkah kedua, kita menerapkan proses yang sama pada daftar empat bilangan  10, 5, 7, 6dan diperoleh bahwa 5 adalah angka terkecil. Dengan menerapkan proses yang sama pada langkah-langkah berikutnya, akhirnya diperoleh daftar urutan : 3, 5, 6, 7, 10.

Hal yang penting adalah keefisienan dari algoritma ini, yaitu sejumlah perbandingan yang dibuat dalam pemilihan bilangan-bilangan tersebut. Banyaknya perbandingan pada langkah pertama adalah n-1, pada langkah kedua adalah n-2dan seterusnya hingga pada langkah akhir diperoleh perbandingannya adalah nol.

Jadi, banyaknya perbandingan dalam pengurutan daftar dari n bilangan semula adalah 1+2+3+….+(n-1). Misalkan S(n)=1+2+…+n= , sehingga kita mengetahui bahwa S(n)=n+S(n-1).

Dalam menentukan suatu rumus untuk S(n) ada dua persoalan utama, yaitu memperkirakan suatu rumus dan membuktikan bahwa rumus tersebut adalah benar. Polya (1945) memuat suatu pembahasan yang bagus tentang teknik yang digunakanuntuk memperkiraan (menebak) rumus. Salah satu kemungkinan adalah dengan mengamati suatu pola.

Suatu permainan yang terdiri dari susunan kartu domino sedemikian hingga jatuhnya domino yang pertama, mengakibatkan raaksi berantai pada jatuhnya kartu domino yang lain. Permainan sederhana ini membuat pemikiran dasar ” Prinsip Induksi Matematika”. Dapat kita buktikan penyataan untuk setiap n jika kita menunjukkan setiap domino bisa menjatuhkan semua domino. Bila domino bernomor k jatuh, domino  bernomor k+1 juga akan jatuh untuk setiap nilai k. jika dua kondisi terpenuhi: (1) kartu domino yang pertama jatuh dan (2) jika kartu domino ke k jatuh maka kartu domino ke k+1 juga jatuh. Jika kita mengidentifikasi jatuhnya suatu domino tertentu dengan kasus percobaan yang bersesuaian, maka pemikiran seperti ini menunjukkan dua hal. Pertama, bahwa kasus pertama itu benar. Kedua, bahwa jika kasus k benar, maka kasus k+1 juga benar. Karena tidak ada kasus khusus pada label kartu domino yang pertama, maka kita peroleh “prinsip induksi matematika lemah” dan ”prinsip induksi matematika kuat”.

B.     Induksi Matematika Lemah

Induksi Matematika adalah cara standar dalam membuktikan bahwa sebuah pernyataan tertentu berlaku untuk setiap bilangan asli. Pembuktian dengan cara ini terdiri dari dua langkah, yaitu:

a.       Menunjukkan bahwa pernyataan itu berlaku untuk bilangan n=1.

b.      Menunjukkan bahwa jika pernyataan itu berlaku untuk bilangan n, maka pernyataan itu juga berlaku untuk bilangan n + 1.

Pada contoh , pengurutan P(n) merupakan suatu pernyataan bahwa S(n)= .  Langkah pertama biasa disbut langkah dasar dan langkah kedua disebut langkah induksi. Asumsipada langkah kedua yaitu bahwa kasus ke-k adalah benar disebut hipotesis induksi. Bentuk induksi ini disebut betuk lemah karena hipotesis induksi hanyamengasumsikan satu kasus sebelumnya.

Prinsip induksi matematika merupakan akibat langsung dari definisi bilangan asli. Misalkan suatu himpunan bilangan S yang mempunyai sifat:

a.       Bilangan asli qada di dalam S

b.      Jika bilangan asli k ada di dalam S maka bilangan asli k+1 juga ada di dalam S, (k≥q).

Memahami pemikiran yang ada di balik prinsip ini adalah penting. Langkah dasar secara eksplisit membuktikan bawa P(q) adalah benar. Sebuah aplikasi langkah induksi dengan p=q menghasilkan kebenaran untuk  P(q+1). Setelah kita mnegetahui kebenaran P(q+1), kita dapat mengaplikasikan lagi bentuk induksi untuk memperoleh kebenaran P(q+2)dan seterusnya. Langkah induksi secara sederhana mengatakan bahwa jika proses telah mencapai suatu taha, maka proses tersebut akan melangkah ketahap selanjutnya. Tentu saja, proses haruslah diawali dan hal tersebut merupakan fungsi dari langkah dasar. Langkah induksi mengasumsikan dalil yang harus dibuktikan. Kita berupaya membuktikan kebenaran sejumlah kasusyang tidak terhingga banyaknya, dan langkah induksi memperbolehkan kita untuk mengasumsikan satu kasus sebelumnya untuk membuktikan satu kasus tertentu. Untuk menjelaskan pemikiran ini, perhatikan contoh:

Misalkan akan dibuktikan suatu pernyataan bahwa jumlah n bilangan asli pertama, yaitu 1+2+:::+n, adalah sama dengan .

Untuk membuktikan bahwa pernyataan itu berlaku untuk setiap bilangan asli, langkah-langkah yang dilakukan adalah sebagai berikut:

a.    Menunjukkan bahwa pernyataan tersebut benar untuk n = 1. Jelas sekali bahwa jumlah 1 bilangan asli pertama adalah  Jadi pernyataan tersebut adalah benar untuk n = 1

b.      Menunjukkan bahwa jika pernyataan tersebut benar untuk n = k, maka pernyataan tersebut juga benar untuk n = k+1. Hal ini bisa dilakukan

dengan cara:

·         Mengasumsikan bahwa pernyataan tersebut benar untuk n = k, yaitu:

1+ 2 + … + k =

·         Menambahkan k + 1 pada kedua ruas, yaitu:

1 + 2 + … + k + (k + 1) =  + (k+1)

·         Dengan menggunakan manipulasi aljabar, diperoleh

 + (k+1) =   +

                        =

                                                =

·         Dengan demikian

1     + 2 + ::: + k + (k + 1) =

·         Jadi pernyataan tersebut benar untuk n = k + 1.

c.       Dengan induksi matematika dapat disimpulkan bahwa pernyataan tersebut berlaku untuk setiap bilangan asli n.

Conto soal:

C.    Induksi Matematika Kuat

Misalkan bahwa P(n) adalah suatu pernyataan mengenai bilangan asli n dan bahwa q adalah suatu bilangan asli tertentu. Untuk membuktikan bahwa P(n) adalah benar untuk semua k≥q cukup dengan menunjukkan dua hal berikut:

a.       Kasus P(q) yang pertama adalah benar

b.      Jika k≥q dan kasus-kasus  P(q),…P(k) benar,  maka kasus berikut yaitu P(k+1) adalah benar.

Langkah dasar, langkah induksi dan hipotesis induksi digunakan dalam cara yang jelas. Langkah dasar menunjukkan bahwa P(q) adalah benar. Aplikasi dari langkah induksi dengan k=q menghasilkan kebenaran untuk P(q+1). Sekarang, kita mengetahui kebenaran P(q) dan P(q+1), kita dapat menerapkan langkah induksi lagi untuk memperoleh P(q+2) dan seterusnya. Apabila langkah (1) dan (2) telah dilakukan dengan benar, dapat disimpulkan bahwa P(n) benar untuk setiap bilangan asli n.

            Perhatikan bahwa apabila langkah (2) telah terbukti dan langkah (1) sudah ditunjukkan bahwa P(1) adalah benar, maka akan diperoleh rangkaian pernyataan yang benar yaitu: P(1)→P(2) benar,  P(2)→P(3) benar, P(3)→P(4) benar dan seterusnya. Dengan demikian diperoleh bawa P(2) benar, P(3) benar, P(4) benar dan seterusnya. Jadi P(n) benar untuk setiap bilangan asli n.

            Kata kuat mengacu pada kenyataan bahwa hipotesis induksinya mempunyai lebih banyak informasi dibanding dengan informasi dari hipotesis induksi lemah. Sebenarnya dua bentuk induksi tersebut adalah equivalen, karena masing-masing dapat diperoleh dari yang lainnya, dan untuk suatu masalah yang ada, kita menggunakan bentuk yang paling tepat, dengan kata lain prinsip induksi matematika kuat memungkinkan kita mencapai kesimpulan yang sama meski pun memberlakukan asumsi yang lebih banyak.

            Pada prinsipnya, induksi matematika adalah metode pembuktian untuk membangun kesahihan pernyataan matematika yang berhubungan dengan bilangan asli. Prinsip induksi matematika dibangun atas suatu sifat fundamental himpunan bilangan asli, yang biasa disebut dengan Well Ondering Property. Well Ondering Property  (WOP) menyatakan bahwa setiap himpunan bilangan tidak kosong dari himpunan bilangan asli N  mempunyai anggota terkecil.

Contoh soal

Bilangan bulat positif disebut prima jika dan hanya jika bilangan bulat tersebut habis dibagi dengan 1 dan dirinya sendiri. Kita ingin membuktikan bahwa setiap bilangan bulat positif n (n ³ 2) dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima. Buktikan dengan prinsip induksi kuat.

Penyelesaian:

a.       Basis induksi. Jika n = 2, maka 2 sendiri adalah bilangan prima dan di sini 2 dapat dinyatakan sebagai perkalian dari satu buah bilangan prima, yaitu dirinya sendiri.

b.      Langkah induksi. Misalkan pernyataan bahwa bilangan 2, 3, …, n dapat dinyatakan sebagai perkalian (satu atau lebih) bilangan prima adalah benar (hipotesis induksi). Kita perlu menunjukkan bahwa n + 1 juga dapat dinyatakan sebagai perkalian bilangan prima.

Ada dua kemungkinan nilai n + 1:

a)      Jika n + 1 sendiri bilangan prima, maka jelas ia dapat dinyatakan sebagai perkalian satu atau lebih bilangan prima.

b)      Jika n + 1 bukan bilangan prima, maka terdapat bilangan bulat positif a yang membagi habis n + 1 tanpa sisa. Dengan kata lain, (n + 1)/ a = b   atau (n + 1) = ab

Dalam hal ini, 2 £ a £ b £ n. Menurut hipotesis induksi, a dan b dapat dinyatakan sebagai perkalian satu atau lebih bilangan prima. Ini berarti, n + 1 jelas dapat dinyatakan sebagai perkalian bilangan prima, karena n + 1 = ab.

Karena langkah (i) dan (ii) sudah ditunjukkan benar, maka terbukti bahwa setiap bilangan bulat positif n (n ³ 2) dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima.

Contoh soal

Buktikan 1 + 2 + 3 + . . . + n = ½ n (n + 1) untuk setiap n bilangan asli.

Penyelesaian:

Pernyataan yang akan dibuktikan adalah

1 + 2 + 3 + . . . + n = ½ n (n + 1)

a.       Basis induksi. Dengan demikian, P(1) adalah 1 = ½ .1.(1+1), P(2) = 1 + 2 =½.2.(2+1)  dan seterusnya.

b.       Untuk membuktikan pernyataan itu, perhatikan bahwa P(1) adalah benar.

Kemudian, misalkan bahwa 1 + 2 + 3 + . . . + n = ½ n (n + 1) adalah benar, dan kita harus membuktikan bahwa P(n+1) adalah benar. Untuk ini, kita tambahkan kedua ruas pernyataan P(n) dengan (n + 1) dan diperoleh

1+ 2 + . . . + n + (n + 1) = ½ n (n+1) (n+1)

= ½ [n(n+1)+ 2(n+1)]

= ½ (n² + 3n + 2)

= ½ (n+1)( n +2)

= ½ (n+1)[( n+1)+1]

Dari sini kita peroleh bahwa Pn+1 adalah benar. Hal ini menunjukkan bahwa pernyataan

1 + 2 + 3 + . . . + n = ½ n (n + 1)

adalah benar untuk setiap n bilangan asli.