Erwin Harahap

do Now or Never

Induksi Matematika

Posted by Erwin on April 2, 2008

<br /> Kuliah 02 – Metode Pembuktian – Induksi Matematika – 2008.nb<br />

MATEMATIKA DISKRIT
Metoda Pembuktian
(Induksi Matematika)

Erwin Harahap

Perkuliahan ke 2, Rabu 2 April 2008

Pendahuluan (preface)

Andaikan bahwa terdapat serangkaian balok bernomor 1, 2, 3, … dimana setiap balok, selain diberi nomor juga ditandai dengan huruf  "x"

HTMLFiles/kuliah2_2.gif]

Kita akan misalkan bahwa :

RowBox[{Balok pertama ditandai          &nbs ... p;            ...,  , RowBox[{(, 2.1, )}]}]

RowBox[{Jika semua balok sebelum balok ke - n ditandai, ,, maka balok ke - n ditandai, ,, &nbs ...             ...,  , RowBox[{(, 2.2, )}]}]}]

Selanjutnya akan diperlihatkan bahwa (2.1) dan (2.2) akan mengakibatkan semua balok ditandai, dengan memeriksa balok satu persatu. Pernyataan (2.1) secara eksplisit  menyatakan balok 1 ditandai. Perhatikan balok 2. Semua balok sebelum balok ke-2, katakanlah balok 1, ditandai; sehingga menurut (2.2) balok 2 juga ditandai. Perhatikan balok 3. Semua balok sebelum balok ke-3, katakanlah balok 1 dan 2, ditandai; sehingga menurut (2.2), balok 3 juga ditandai. Melalui cara ini, dapat diperlihatkan bahwa setiap balok ditandai. Sebagai contoh, telah diketahui bahwa balok ke-1 s/d ke-3, ditandai. Untuk menunjukkan bahwa balok ke-4 ditandai, kita nyatakan bahwa semua balok sebelum balok ke-4 ditandai. Dengan demikian, menurut (2.2), balok ke-4 juga ditandai.
Prinsip pada uraian diatas dinamakan Induksi Matematika, yaitu menyimpulkan sesuatu hal secara umum dari hal yang khusus.     

Barisan Bilangan Ganjil

Dapatkah ditemukan suatu rumus untuk menentukan jumlah n bilangan bulat ganjil pertama ?
Jumlah n bilangan bulat ganjil pertama adalah :

1 = 1 1 + 3 = 4 1 + 3 + 5 = 9 1 + 3 + 5 + 7 = 16 1 + 3 + 5 + 7 + 9 = 25 .  .  .

Dari bilangan-bilangan tersebut diatas, sangatlah mungkin apabila ditebak bahwa jumlah n bilangan bulat ganjl pertama adalah n^2.
Diperlukan suatu metoda untuk membuktikan bahwa tebakan ini adalah benar dan berlaku untuk semua bilangan bulat ganjil.
INDUKSI MATEMATIKA adalah salah satu metoda pembuktian paling penting yang dapat digunakan untuk membuktikan pernyataan-pernyataan model diatas.
Induksi Matematika digunakan secara ekstensif untuk membuktikan hasil sejumlah objek-objek diskrit yang sangat luas dan beragam. Diantaranya, induksi matematika digunakan untuk membuktikan hasil kompleksitas dari suatu algoritma, pembenaran tipe-tipe tertentu pada berbagai program komputer, pembuktian pada teorema-teorema graf dan tree, dan lain sebagainya.  

Induksi Matematika (mathematical induction)

Beberapa teorema menetapkan bahwa S(n) adalah benar untuk setiap bilangan bulat positif n, dimana P(n) adalah sebuah fungsi proposisional, seperti misalnya suatu pernyataan bahwa  

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

atau suatu pernyataan bahwa

n ≤2^n

Induksi Matematika merupakan satu metoda untuk membuktikan suatu teorema dengan model seperti pada dua pernyataan diatas. Dengan kata lain, induksi matematika digunakan untuk membuktikan suatu proposisi dengan bentuk

∀n, S (n)

dimana n adalah bagian dari himpunan bilangan buat positif.

Pembuktian dengan metoda induksi matematika menyatakan bahwa S(n) adalah benar untuk setiap bilangan bulat n terdiri dari dua langkah, yaitu :
1. Langkah Dasar. Proposisi S(1) harus ditunjukkan benar atau berlaku
2. Langkah Induktif. Implikasi S(n) →S(n + 1) harus ditunjukkan benar untuk n setiap bilangan bulat positif

Contoh Aplikasi

Contoh 1 : The Sum of The Natural Numbers

Gunakan Induksi matematika untuk membuktikan bahwa jumlah n bilangan asli pertama adalah :

1 + 2 + 3 + 4 + … + n = n(n + 1)/2, ∀ n ∈ Ν

Solution

Langkah dasar : akan ditunjukkan bahwa S(n) benar untuk n = 1, dimana S(n) = n(n + 1)/2

S (1) = 1

untuk n = 1 dapat ditunjukkan bahwa

n(n + 1)/2 = (1 (1 + 1))/2 = 1

untuk n = 1, S(n) benar. Dengan demikian langkah dasar dipenuhi.

Langkah Induktif : akan ditunjukkan bahwa  S(n) → S(n + 1)
Misal S(n) berlaku untuk suatu bilangan asli n sedemikian sehingga

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

Maka akan dibuktikan untuk n = n +1 berlaku S(n) = S(n +1)

1 + 2 + 3 +... + n + (n + 1) = (n (n + 1))/2 + (n + 1) = (n (n + 1))/2 + (2 (n + 1))/2 = (n^2  ...  + 2n + 2)/2 = (n^2 + 3n + 2)/2 = ((n + 1) + (n + 2))/2 = ((n + 1) + ((n + 1) + 1))/2 = S (n + 1)

Dengan demikian terbukti bahwa S(n) = n(n + 1)/2berlaku untuk semua bilangan asli

Contoh 2 : The Sum of Francesco Maurolico

Gunakan Induksi matematika untuk membuktikan bahwa jumlah n bilangan bulat ganjil positif pertama adalah :

1 + 3 + 5 + 7 + … + (2n + 1) = n^2, ∀ n ∈ Ν

Solution

Langkah dasar : akan ditunjukkan S(n) benar untuk n = 1, dimana S(n) = n^2

S (1) = 1

untuk n = 1 dapat ditunjukkan bahwa

n^2 = 1^2 = 1

untuk n = 1, S(n) benar. Dengan demikian langkah dasar dipenuhi.

Langkah Induktif : akan ditunjukkan bahwa  S(n) → S(n + 1)
Misal S(n) berlaku untuk suatu bilangan bulat positif n sedemikian sehingga

1 + 3 + 5 +... + (2n - 1) = n^2

Selanjutnya akan dibuktikan untuk n = n +1 berlaku S(n) = S(n +1)

1 + 3 + 5 +... + (2n - 1) + (2 (n + 1) - 1) = n^2 + (2n + 2 - 1) = n^2 + 2n + 2 - 1 = n^2 + 2n + 1 = (n + 1)^2  = S (n + 1)

Dengan demikian terbukti bahwa S(n) berlaku untuk semua bilangan bulat positif.

Contoh 3 : Inequality

Gunakan Induksi matematika untuk membuktikan pertidaksamaan

n < 2^n

Berlaku untuk semua bilangan bulat positif.

Solution

Misal S(n) adalah proposisi   n < 2^n
Langkah dasar : akan ditunjukkan S(n) benar untuk n = 1

S (1) = 1

untuk n = 1 dapat ditunjukkan bahwa

2^n = 2^1 = 2

maka

1<2^n ≡1<2

untuk n = 1, S(n) benar. Dengan demikian langkah dasar dipenuhi.

Langkah Induktif : akan ditunjukkan bahwa  S(n) → S(n + 1)
Misal S(n) berlaku untuk suatu bilangan bulat positif n sedemikian sehingga

n<2^n

Selanjutnya akan dibuktikan untuk  n = n +1 berlaku S(n) = S(n +1)

n + 1<2^n + 1< (2^n + 2^1 = 2^(n + 1)) jadi, n + 1<2^(n + 1)

Dengan demikian terbukti bahwa S(n) berlaku untuk semua bilangan bulat positif.

Contoh 4 : Divisibility

Gunakan Induksi matematika untuk membuktikan bahwa

n^3 - n

dapat dibagi 3 untuk n adalah bilangan bulat positif

Solution

Misal S(n) adalah proposisi  n^3 - n dapat dibagi 3
Langkah dasar : akan ditunjukkan S(n) benar untuk n = 1

S (1) = 1^3 - 1 = 0

untuk n = 1, S(n) = 0 dapat dibagi 3. Dengan demikian langkah dasar dipenuhi.

Langkah Induktif : akan ditunjukkan bahwa  S(n) → S(n + 1)
Misal S(n) berlaku untuk suatu bilangan bulat positif n sedemikian sehingga

n^3 - n  dapat dibagi 3

Selanjutnya akan dibuktikan untuk n = n +1 berlaku S(n) = S(n +1)

(n + 1)^3 - (n + 1) = (n^3 + 3n^2 + 3n + 1) - (n + 1)       &nbs ... nbsp;            = (n^3 - n) + 3 (n^2 + n)

(n^3 - n)dapat dibagi 3 berdasarkan asumsi induksi. begitu pula dengan 3 (n^2 + n)dapat dibagi 3. Dengan demikian terbukti bahwa S(n) berlaku untuk semua bilangan bulat positif.

Contoh 5 : Sums of Geometric Progressions

Gunakan Induksi matematika untuk membuktikan bahwa

Underoverscript[∑, j = 1, arg3] ar^(j - 1) = a + ar + ar^2 +... + ar^(n - 1) = (ar^n - a)/(r - 1)    ... (*)

dimana r ≠ 1

Solution

Misal S(n) adalah proposisi (*)
Langkah dasar : akan ditunjukkan S(n) benar untuk n = 1

a = (ar - a)/(r - 1)    = (a (r - 1))/(r - 1)    = a

untuk n = 1, S(n) benar. Dengan demikian langkah dasar dipenuhi.

Langkah Induktif : akan ditunjukkan bahwa  S(n) → S(n + 1)
Misal S(n) berlaku untuk suatu bilangan bulat positif n sedemikian sehingga

Underoverscript[∑, j = 1, arg3] ar^(j - 1) = a + ar + ar^2 +... + ar^(n - 1) = (ar^n - a)/(r - 1)

Selanjutnya akan dibuktikan untuk n = n +1 berlaku S(n) = S(n +1)

a + ar + ar^2 +... + ar^(n - 1) + ar^((n + 1) - 1) = (ar^n - a)/(r - 1) + ar^((n + 1) - 1) = ( ... (r - 1) = (ar^n - a)/(r - 1) + (ar^(n + 1) - ar^n)/(r - 1) = (ar^(n + 1) - a)/(r - 1) = S (n + 1)

Dengan demikian S(n) berlaku untuk semua bilangan asli n


Created by
Mathematica
 (April 2, 2008)

2 Responses to “Induksi Matematika”

  1. The CC said

    menarik sekali..
    Matematika da dalam kehidupan kita

  2. samiyawati said

    thanks atas infonya mengenai induksi matematika, saran saya sebaiknya induksi dan deduksi dikumpulkan dalam satu data aja untuk memudahkan membedakan

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: