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 )
Wes Ren jadi asisten matdis ae
BalasHapusberkunjung lah ke blog saya
BalasHapushttp://ernie-p.blogspot.com/
tks
:)