Header Ads

  • Breaking News

    INDUKSI MATEMATIKA

    Prinsip Induksi Matematika

    Sebuah cara pembuktian yang sering dipakai, simple, dan sangat ampuh dalam matematika kombinatorial dan ilmu komputer, dikenal dengan prinsip induksi matematika. Induksi matematika adalah metode pembuktian untuk proposisi bilangan bulat.
    Untuk suatu pernyataan tertentu yang melibatkan sebuah bilangan asli n, jika kita dapat menunjukkan bahwa :
        Pernyataan itu benar untuk n = n0, dan
        Pernyataan itu benar untuk n = k+1, dengan mengasumsikan bahwa pernyataan itu benar untuk n = k, (kn0), 
    maka kita dapat menyimpulkan bahwa pernyataan itu benar untuk semua bilangan asli n n0.
    Langkah (1) dinamakan basis induksi, sedangkan langkah (2) dinamakan langkah induksi. Di samping itu, asumsi bahwa pernyataan tersebut benar untuk n = k di dalam langkah (2) biasanya dinamakan hipotesis induksi.

    Induksi Matematika pada Barisan Bilangan

    Contoh 1 :

    Buktikan bahwa  untuk semua n ≥1.

    Solusi:
    Misalkan P(n) menyatakan  untuk semua n ≥1.

    1. Basis induksi.
    Akan dibuktikan P(1) benar untuk n = 1.

    Perhatikan bahwa:

    Jadi, basis induksi benar.


    2. Langkah induksi.
    Misalkan P(k) benar, yaitu 

    Akan dibuktikan P(k+1) juga benar yaitu 

    Perhatikan bahwa:


    Karena (1) dan (2) benar, maka terbukti bahwa  untuk semua n ≥1, juga benar.

    Atau

    step 1)  untuk n=1
                           =1(1+1)/2
    =1 (benar)

    step 2)  untuk n=k
    1+2+3+...+k=k(k+1)/2 (benar)

    step 3) akan dibuktikan bahwa n=k+1 juga benar
    1 + 2 + 3 +...+ k + ( k + 1) = (k + 1)( k + 1 + 1)/ 2
    k ( k + 1 ) / 2 +(  k + 1) =  (k + 1)( k + 2) / 2
    [ k ( k + 1 )  + 2(  k + 1)] /2 = ( k + 1)( k + 2) / 2  sifat distribusi (a +b)(c+d) = a (c + d) + b ( c + d)
    (k + 1)( k + 2) / 2 =  ( k + 1)( k + 2) / 2  terbukti

    Induksi Matematika pada Ketidaksamaan

    Contoh 2:

    Buktikan bahwa  untuk setiap bilangan bulat n ≥ 5.
    Solusi:
    Misalkan P(n) menyatakan  untuk setiap bilangan bulat n ≥ 5.

    1.) Basis induksi.
    Akan dibuktikan P(5) benar untuk n = 5.
    Perhatikan bahwa:
    Jadi, basis benar.

        2.) Langkah induksi.
    Misalkan P(k) benar, yaitu 
    Akan dibuktikan P(k+1) juga benar yaitu 

    Perhatikan bahwa:
    Karena (1) dan (2) benar, maka terbukti bahwa  untuk setiap bilangan bulat n ≥ 5,  juga benar.

    Induksi Matematika pada Keterbagian

    Contoh 3:

    Buktikan bahwa  habis dibagi 3 untuk semua bilangan bulat n ≥ 1.

    Solusi:

    Misalkan P(n) menyatakan  habis dibagi 3 untuk semua bilangan bulat n ≥ 1.

    Basis induksi.

    Akan dibuktikan P(1) benar untuk n = 1.

    Perhatikan bahwa: 

    Jadi, basis benar.

    Langkah induksi.

    Misalkan P(k) benar, yaitu  habis dibagi 3

    Akan dibuktikan P(k+1) juga benar yaitu  habis dibagi 3

    Perhatikan bahwa:


    Karena (1) dan (2) benar, maka terbukti bahwa  habis dibagi 3 untuk semua bilangan bulat n ≥ 1,

    juga benar.



    LATIHAN:

    1. Gunakan prinsip induksi matematika untuk membuktikan pernyataan berikut adalah benar.
      1. , untuk semua bilangan bulat n ≥ 1.
      2. , untuk setiap bilangan bulat positif n.
      3. habis dibagi 7 untuk semua bilangan bulat n ≥ 1.
      4. , untuk semua bilangan bulat tak negatif n.
    2. Di dalam sebuah pesta, setiap tamu berjabat tangan dengan tamu lainnya hanya sekali saja. Buktikan dengan induksi matematika bahwa jika ada n orang tamu maka jumlah jabat tangan yang terjadi adalah 




    No comments