Sabtu, 17 Desember 2011

contoh soal matematika diskrit tentan induksi, strong induksi, dan rekursif


Induction Mathematic
1.      Proof with induction Mathematic
1+4+7+ ……. + ( 3n -2) = ½ n(3n-1)

a.      Base case : Show that p(1) is true
  P(n) : 1+4+7+ ……. + ( 3n -2) = ½ n(3n-1)
  P(1) : (3.1 – 2) = ½ 1 ( 3.1 -1 )
  1  = 1   true …

b.      Induction Hypothesis
  Assume that p (k) is correct
( 3k -2) = ½ k(3k-1)

C.  Prove that p (k+1) is correct

( 3(k+1) -2 ) = ½ (k+1) ( 3(k+1)-1 )
                                 = ½(k+1)( 3k+2)
                     = ½ (3k2+5k+2 )   is it true ??

We try add 3k + 1, because the pattern of the question is Plus 3 every it up.
( 3k -2)+ ( 3k+1)  = ½ k(3k-1) + ( 3k+1 )
            ½ (3k2-k)+ (3k+1)
            ½ (3k2-k+6k+2)
            ½ ( 3k2+5k+2 )                                          Proven
"Matematika Diskrit dan Aplikasinya pada Ilmu komputer", 4th edition, Jong Jek Siang, ANDI, 2009, (hal 127)

2.      Buktikan menggunakan induksi matematika untuk setiap bilangan bulat positif n, misalkan p(n) adalah kalimat : 4n -1 habis dibagi 3

a.      Base case :                               show that p(1) is true
P(n) : 3 | 4n -1
P(1) : 3 | 41 – 1    true .                               

b.      Induction Hypothesis
Assume that p(k) is correct
P(k) : 4k – 1

C.     Prove that p (k+1) is correct.
        Will be proofing that 4k+1  -1 habis dibagi 3

        4k+1  – 1 =  4k.4 – 1
                      =  4. 22k -1
                   = ( 3.22k + 22k ) – 1
                   = 3.22k + (22k – 1)

Seperti yang kita tahu, 3.22k bisa habis di bagi 3 karena kelipatnya, sedangkan ( 22k – 1 ) juga habis dibagi 3 menurut hypothesis di atas.
Jadi 
              4k+1  – 1 = 3.22k + (22k – 1) juga habis dibagi 3.
              Its proven that p(k+1) is correct
"Matematika Diskrit dan Aplikasinya pada Ilmu komputer", 4th edition, Jong Jek Siang, ANDI, 2009, (hal 127)

Strong Induction

1.      Prove that (n+2)! Is even
Base Step
For P(0) is  (0+2)!=2,  is even
       P(1) is (1+2)!=6, is even
       P(2) is (2+2)!=24, is even
Induction Hypothesis
Assume (n+2)! Is even
Induction Step
((n+1)+2)! = (n+2)! (n+3) is even



2.      Prove that 2n  n2 for n  4
Base Step
For P(4),
24
For P(5),
Induction Hypotesis
Assume 2n  n2
Induction Step
For

Logic  And Discrete Mathematics”, 1th Edition, Winfried Karl GrassMam, Prentice Hall, 1998, Page 131-132


3.Use the strong form of mathematical induction to prove that every natural number n 2 is either prime or product of prime numbers.
Solution : all integer n 2. N0  = 2 is prime. So we assume that the teory is true . now let K.2 and suppose that is true for all positive integer L, 2  L < K; in other words, suppose that integer L in interval , 2  L < K is either prime or product of primes. We must prove that k has this same property. If k is prime, there is nothing to do. On the other hand, if k is not prime, then k can be factored k =ab, where a and b are integer satisfying 2  a,b < k. by the induction Hypohesis, each of a and b is either prime or product of primes. Then, k is required. We conclude that every n  2 is prime or product of primes.
 
" Discrete Mathematics with Graph.Theory", second edition, Edgar G. Goodairem michael Darmenter.

Recursive.

1.      Tentukan 4 buah suku pert ama dari sk=sk-1 + 2 sk-2 untuk k  2 dengan kondisi awal s0 = 1 dan s1 =1

Solution : for answer the question above, we can make a recursive to answer that.  We find s2, s3 with use the first condition.

S2 = s2-1 + 2 s2-2 = 1 + 2 = 3
S3 = s3-1 + 2 s3-2  = 3 + 2 = 5

It means, the first sequence of four is : 1, 1 ,3,5

"Matematika Diskrit dan Aplikasinya pada Ilmu komputer", 4th edition, Jong Jek Siang, ANDI, 2009,( hal 418 )

2.      Tentukan 4 buah suku pertama dari uk = k uk-1 – uk-2 untuk k 3 dengan kondisi awal u1=1, u2 =1

Solution : we find out the u3 and u4
U3 = 3 u3-1 – u3-2 =  3.1 – 1 = 2 
U4 = 4 u4-1 – u4-2 =  4.2 – 1 = 7

It means, the first sequence of four is, 1,1,2,7 .

"Matematika Diskrit dan Aplikasinya pada Ilmu komputer", 4th edition, Jong Jek Siang, ANDI, 2009,( hal 418 )







2 komentar: