PRINSIP INDUKSI MATEMATIKA 
                                                                           
                  Prinsip Induksi Matematika (Principle of Mathematical Induction)  
                  P (n) adalah pernyataan tentang n ε N.  
                  misalkan bahwa :  
                  (i)  P (1) benar  
                  (ii) Jika P (k) benar, maka P (k + 1) benar  
                        P (n) benar, n ε N.  
                  Contoh:  
                  1. Buktikan P (n) = (n + 2)2 = n2 + 4n + 4, n ε N dengan menggunakan prinsip induksi 
                      matematika 
                      Penyelesain: 
                      (i)  untuk n = 1  
                           (1 + 2)2 = 12 + 4.1 + 4  
                           (3)2   = 9        (benar) 
                      (ii)  Asumsi benar untuk n = k  
                           (k + 2)2 = k2 + 4k + 4, n ε N (benar) 
                           akan dibuktikan bahwa  
                           P (k + 1) = (k + 3)2 = (k + 1)2 + 4(k + 1) + 4  benar, 
                      Bukti,  
                                  (k + 3)2 = k2 + 6k + 9  
                                            = k2 + 2k +  4k +1 + 4 + 4 
                                            = (k2 + 2k + 1) + (4k + 4) + 4 
                                            = (k + 1)2 + 4(k + 1) + 4  
                      Jadi  (k + 3)2 = (k + 1)2 + 4(k +1) + 4, terbukti benar.  
                      Dari (i) dan (ii) berdasarkan prinsip induksi matematika kita simpulkan pernyataan diatas 
                      benar untuk n εN. 
                  2. Buktikan dengan prinsip induksi matematika bahwa jumlah bilangan asli  
                                              
                      1 + 2 + 3 + ... + n =   n (n + 1), n ε N  
                                              
                      Penyelesaian:  
                      (i)   untuk n = 1  
                           1 =     1 . 2  = 1 (Benar) 
                                 
                      (ii)  asumsi benar untuk n = k  
                  Matematika Diskrit                                                                                             1 
                                                                     
                                    1 + 2 + 3 + ... + k =   k (k + 1), n ε N  
                                                                     
                                    akan dibuktikan bahwa P (k + 1) benar 
                                                                                    
                                    1 + 2 + 3 + ... + k + (k + 1) =   (k + 1) (k + 2)  
                                                                                    
                             Bukti,  
                                                                                   
                                    1 + 2 + 3 + ... + k + (k + 1) =  k (k + 1) + (k + 1)  
                                                                                   
                                                                                                      
                                                                               =  k (k + 1) +   . 2 .(k + 1) 
                                                                                                      
                                                                                       2             
                                                                               =  (k  + k) +    (2k + 2) 
                                                                                                     
                                                                               =  (k2 + k + 2k + 2) 
                                                                                  
                                                                               =  (k2 + 3k + 2) 
                                                                                  
                                                                                   
                                                                               =   (k + 1) (k + 2)  
                                                                                   
                             Jadi    1  +  2  +  3  +  ...  +  k  +  (k  +  1)  =     (k  +  1)  (k  +  2),  terbukti  benar.  
                                                                                                                 
                             Dari (i) dan (ii) berdasarkan prinsip induksi matematika kita simpulkan pernyataan diatas 
                             benar untuk n εN. 
                          Induksi matematik merupakan teknik pembuktian yang baku di dalam matematika.  
                          Melalui  induksi  matematik  kita  dapat  mengurangi  langkah-langkah  pembuktian  bahwa 
                             semua  bilangan  bulat  termasuk  ke  dalam  suatu  himpunan  kebenaran  dengan  hanya 
                             sejumlah langkah terbatas. 
                        Prinsip Induksi Sederhana. 
                        Misalkan p(n) adalah pernyataan perihal bilangan bulat positif dan kita ingin membuktikan 
                        bahwa p(n) benar untuk semua bilangan bulat positif n. Untuk membuktikan pernyataan ini, 
                        kita hanya perlu menunjukkan bahwa: 
                           1.     p(1) benar, dan 
                           2.     untuk semua bilangan bulat positif n  1, jika p(n) benar maka p(n + 1) juga benar. 
                          Langkah 1 dinamakan basis induksi, sedangkan langkah 2 dinamakan langkah induksi.  
                          Langkah  induksi  berisi  asumsi  (andaian)  yang  menyatakan  bahwa  p(n)  benar.  Asumsi 
                             tersebut dinamakan hipotesis induksi.  
                          Bila kita sudah menunjukkan kedua langkah tersebut benar maka kita sudah membuktikan 
                             bahwa p(n) benar untuk semua bilangan bulat positif n.  
                         
                         
                        Gambar : Efek domino  
                        Matematika Diskrit                                                                                                                                    2 
                   
                  Prinsip Induksi Kuat 
                  Misalkan p(n) adalah pernyataan perihal bilangan bulat dan kita ingin membuktikan bahwa 
                  p(n) benar untuk semua bilangan bulat  n  n . Untuk membuktikan ini, kita hanya perlu 
                                                                          0
                  menunjukkan bahwa: 
                  1.   p(n ) benar, dan 
                          0
                  2.   untuk semua bilangan bulat  n  n , jika p(n  ), p(n +1), …, p(n) benar maka p(n+1) juga 
                                                              0           0       0
                  benar. 
                  Contoh . 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:   
                  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. 
                  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  yang 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 
                  1.   Misalkan P adalah preposisi bahwa jumlah n  bilangan ganjil pertama adalah   ; yaitu, 
                       P(n):1+3+5+…+(2n-1)=    
                  Matematika Diskrit                                                                                         3 
                               (Bilangan ganjil ke-n adalah 2n-1, dan bilangan ganjil berikutnya adalah 2n+1. Buktikan 
                               P  berlaku untuk setiap bilangan bulat positip n   N. 
                                                                       2              
                               Karena : [2 . (1) – 1] = 1   1=  , maka P(1) BENAR.  
                               Asumsikan P(n) BENAR.  
                               Kita tambahkan 2n+1 pada kedua sisi P(n), di dapat 
                                                                                                                       (          ) 
                                                1+3+5+…+ (2n-1) +(2n+1) =   +(2n+1) =       
                               Yang mana adalah P(n+1). Sehingga, P(n+1) benar bilamana P(n) BENAR. 
                               Menurut prinsip induksi matematika, P berlaku untuk setiap n 
                        2.     Buktikan proposisi P, jumlah n bilangan bulat positip pertama adalah 
                                  n (n+1); yaitu, 
                                 
                                                                  
                               P(n):1+2+3+…+n =   n (n+1) 
                                                                  
                                                                                                
                               Proposisi berlaku untuk n=1 karena 1=   (1) (1+1), sehingga P (1) BENAR. 
                                                                                                
                               Asumsikan P(n) BENAR,  
                               kita tambahkan (n+1) pada kedua sisi P(n), didapat  
                                                                     
                               1+2+3+…+n+(n+1) =   n (n+1) + (n+1) 
                                                                     
                                                                 =   [(n(n+1) + 2(n+1)] 
                                                                     
                                                                 =   [(n+1) (n+2)] 
                                                                     
                               Yang mana adalah P(n+1). Sehingga, P(n+1) benar bilamana P(n) BENAR. 
                               Menurut prinsip induksi, P berlaku untuk setiap n. 
                                                                                                                 (   )(    )
                        3.     Buktikan preposisi berikut : P(n):  +  +…+   =                                                        
                                                                                                                          
                                                     (     )(      )      ( )( )
                                                                             
                               Karena   =                            =             = 1, maka P(1) BENAR.  
                                                                             
                               Asumsikan P(n) BENAR,  
                               kita tambahkan (     )  pada kedua sisi P(n), didapat 
                                                                                (          )(             )
                                                                                        
                                                      (             )                                           (          )
                                                                                                                    
                                                                                             
                                                                              (          )(             )        (          ) 
                                                                                            
                                                                                                     
                                                                            (          )[(               )      (             )]
                                                                                             
                                                                                                      
                                                                            (          )(                        )
                                                                                        
                                                                                               
                        Matematika Diskrit                                                                                                                                    4