Ringkasan Induksi & Rekursif

INDUKSI

    Induksi adalah salah satu teknik pembuktian (proofing) dalam matematika. Dengan induksi kita dapat membuktikan suatu pernyataan itu benar atau tidak. 

Teknik-teknik pembuktian dengan induksi:

-          Kasus dasar (Base Case(s)): 

                                                    - tunjukkan pernyataan itu benar untuk sebuah elemen saja.

-                                                                                                     - Inductive hypothesis: asumikan itu benar untuk k elemen.

-                                                                                                     - Buktikan untuk k+1 elemen bahwa pernyataa itu benar.

Dalam Induksi yang ditunjukkan adalah

-         -  Base case: P(1)

-         -  Jika P(k) benar maka untuk P(k+1) juga benar

-         -  Jika P(k+1) benar maka sudah dapat dipastikan pernyataan itu benar

Contoh 1 Induksi:

Let P(n) be the statement that 1² + 2²+ … + n² = n(n+1)(2n+1)/6 for the positive integer n.

Jawaban:  _{zigma i=1 sampai n (} i² ) = n(n+1)(2n+1)/6

Base case:                                                                                

1² = 1(1+1)(2+1)/6

1 = 6/6   

1=1

                        Assume k: zigma i=1 sampai k ( i² )= k(k+1)(2k+1)/6

                        Assume k+1:

                   zigma i=1 sampai k+1 ( i² )= (k+1)(k+2)(2k+3)/6

                   proofing:

P(k+1)=   

= k(k+1)(2k+1)/6+ (k+1) ²                                            

= k(k+1)(2k+1)/6 + 6(k+1)²/6 

= (k+1)(2k²  + 7k +6)/6

=  (k+1)(k+2)(2k+3)/6

Strong Induction

-         Biasanya dalam matematika, pembuktian induksi hanya mengasumsikan P(k) adalah benar dan langsung menggunakannya (dan hanya itu saja!) untuk menunjukkan p(k+1) itu benar. Sedangkan strong induction mengasumsikan P(1), P(2), …, P(k) itu benar, dan menggunakannya untuk menunjukkan P(k+1) adalah benar. [P(1) Ù P(2) Ù p(3) Ù … Ù P(k) ] ® P(k+1)

REKURSIF

Definisi dari rekursif itu sendiri adalah suatu fungsi yang dapat memanggil dirinya sendiri atau termnya adalah dirinya sendiri. Pembuktian dengan rekursi biasanya berdasar pada premis-premis yang diperlukan. Algoritma kadang juga bisa disebut sebagai rekursif ketika perulangan algoritma itu memanggil dirinya sendiri

Rekursif juga dibedakan menjadi 2:

-         -   Base case : 1 € S

-         -  Rekursif : if x € S, then x+1 € S

Contoh 1:

-               - F(a)= a!

-               - Kita juga dapat mengartikannya f(a)= a . f(a-1)

Contoh 2:

-                     - Semua anak x adalah keturunan x.

-                     - Jika y adalah seorang anak x, maka semua keturunan y merupakan keturunan dari x

-                     - Tidak ada orang lain yang merupakan keturunan dari x.

Untuk menentukan apakah orang tertentu merupakan salah satu keturunan dari x, kita perlu menerapkan definisi kalimat ini secara rekursif. 

Diasumsikan bahwa rekurisif ini selalu mencapai akhir. Jawabannya bisa positif, dalam hal ini seseorang itu adalah keturunan x, atau negative, yang berarti tidak ada orang yang sesuai dengan definisi tersebut.

Struktur:

-                -Kasus dasar (Base Case(s)): tunjukkan pernyataan itu benar untuk sebuah elemen saja.

-                -Inductive hypothesis: asumikan itu benar untuk k elemen

-                 -Rekrusif Step :Buktikan recursive definition allows the creation untuk elemen k+1