Metoda Pembuktian: Induksi Matematika
Julan HERNADI
1
Program Studi Pendidikan Matematika Universitas Muhammadiyah, Ponorogo
January 14, 2011
Julan HERNADI
Induksi Matematika
ILUSTRASI
Figure: Ilustrasi Induksi
Julan HERNADI
Induksi Matematika
Reaksi Berantai
Pada ilustrasi di atas, kartu-kartu disusun dalam jarak tertentu. Agar terjadi reaksi berantai, yaitu jatuhnya sebuah kartu akan menyebabkan robohkan kartu-kartu setelahnya maka haruslah memenuhi syarat berikut Minimal 1 kartu didorong sampai roboh Tinggi kartu tidak kurang dari jarak antar kartu, yaitu
Julan HERNADI
Induksi Matematika
x < h.
Fungsi proposisi dengan domain Misalkan
N
P (n) fungsi proposisi dengan n ∈ N
0
⊆ N:
himpunan
bilangan asli. Example
P (n): n ≥ 2n . Perhatikan P (2), P (3) dan P (4) TRUE, tetapi P (n) FALSE untuk n lainnya. Kes: P (n) tidak bernilai benar untuk setiap bil asli n . 2
Perhatikan contoh berikut ini. Example
P (n) : 1 + 2 + · · · + n = n (n + 1). Coba periksa P (1), P (2), P (3), · · · semua bernilai TRUE. Bagaimana kita dapat menyimpulkan bahwa P (n ) TRUE untuk semua n ∈ N ? Tidak 2
mungkin dicoba satu per satu untuk semua bil asli.
Julan HERNADI
Induksi Matematika
Prinsip Induksi Matematika (PIM) Jika
P (n ) TRUE untuk suatu bilangan asli n ∈ N. P (k ) TRUE untuk sebarang k ≥ n →P (k + 1) TRUE maka P (n ) TRUE untuk setiap n ≥ n . 0
0
0
0
Example Buktikan 1 + 2 + · · · +
n = n (n + 1) berlaku untuk setiap bil asli n. 2
Proof. Di sini kita mempunyai
P (n) : 1 + 2 + · · · + n = n (n + 1) 2
n = 1 → P (1) : 1 = (1 + 1) ↔ 1 = 1 sehingga P (1) true. k Asumsikan P (k ) : 1 + 2 + · · · + k = (k + 1) true. Untuk n = k + 1, 1
2
2
Julan HERNADI
Induksi Matematika
Lanj...
P (k + 1) : |1 + 2 +{z· · · + k} +(k + 1) = k (k +1) 2
=
k 2
(k + 1) + (k + 1)
(k + 1 ) 2
(k + 1),
yaitu P (k + 1) True. Kesimpulan: Perhatikan ketika membuktikan
P (n) benar untuk setiap bil asli n. P (k + 1) salah satu ruas, mis ruas
kiri dijabarkan sehingga sama dengan ruas kanan. Example Buktikan bahwa untuk setiap bil asli 1(1!) + 2(2!) + · · · +
Julan HERNADI
n, berlaku
n(n!) = (n + 1)! − 1 Induksi Matematika
Lanj· · ·
P (n) : 1(1!) + 2(2!) + · · · + n(n!) = (n + 1)! − 1. kiri
Untuk
n = 1, ruas
= 1(1!) = 1, dan ruas kanan= (1 + 1)! − 1 = 1. Krn kedua ruas P (1) true. Skrg, asumsikan P (k ) true untuk seb k ;
sama maka
yaitu kita mempunyai 1(1!) + 2(2!) + · · · + Untuk
k (k !) = (k + 1)! − 1
n = k + 1, kita tunjukkan bahwa P (k + 1) true.
Ruas kiri = 1(1!) + 2(2!) + · · · + k (k !) +(k + 1)(k + 1)! |
{z
}
(k +1)!−1
= (k + 1)! − 1 + (k + 1)(k + 1)!
= (k + 1)!(1 + k + 1) − 1
= (k + 1)!(k + 2) − 1 = (k + 2)! − 1 = Ruas
Julan HERNADI
Induksi Matematika
kanan
Prinsip Induksi Kuat
Jika
P (1) true P (1), P (2), · · · , P (k ) true →P (k + 1) true maka P (n ) true untuk setiap bil asli n . Example Diberikan barisan yang dide nisikan secara rekursif
x
1
xn+
1
1
Buktikan 1
≤ xn ≤ 2
: = 1, x2 := 2, : = (xn + xn−1 ) 2
untuk
untuk setiap bil asli
Julan HERNADI
n>1
n.
Induksi Matematika
Bukti ...
Proof. Di sini P (n ) : 1 ≤ xn ≤ 2. Untuk n = 1, diperoleh x = 1 sehingga P (1) true. Selanjutnya diasumsikan P (1), P (2), · · · , P (k ) semuanya true, yaitu 1 ≤ xn ≤ 2 untuk n = 1, 2, · · · , n . Untuk n = k + 1 1
diperoleh
2
≤ xk + xk −1 ≤ 4 → 1 ≤
yaitu berlaku
1 2
(xk + xk −1 ) ≤ 2 ↔ 1 ≤ xk +1 ≤ 2
P (k + 1).
Julan HERNADI
Induksi Matematika
Soal Latihan 1 2
n − 1 selalu habis dibagi 6 untuk setiap bil asli
Buktikan 7
x > −1maka berlaku (1 + x setiap bil asli n . Buktikan jika
1
+ 21.3 + ... + n(n1+1) =
3
Buktikan
4
Buktikan bahwa 2
1
≥ 1 + nx
n.
untuk
n n+1 untuk setiap bil asli
− 22 + 32 + ... + (−1)n+1 n2 = (−1)n+1 n(n2+1)
bil asli 5
.
1 2
)n
n.
n.
untuk setiap
Berikan konjektur untuk rumus jumlah dari 1
·
1 3
+ 31·5 + · · · + (2n−1)(1 2n+1) ,
kemudian buktikan konjektur tsb
dengan induksi matematika. 6 7 8
n
Buktikan 2
n
< n!
untuk setiap
n ≥ 4.
n ≥ 5. Temukan bil asli terbesar m sehingga n − n dapat dibagi oleh m untuk setiap bil asli n. n−2 untuk setiap Buktikan 2 − 3 ≤ 2
3
Julan HERNADI
Induksi Matematika
Bukti Ekuvalensi (Dua arah)
To prove a theorem that is a biconditional statement, that is, a statement of the form
p ↔ q , we show that p → q and q → p are
both true. The validity of this approach is based on the tautology
(p ↔ q ) ≡ [(p → q ) ∧ (q → p )] . When we prove that a group of statements are equivalent, we can establish any chain of conditional statements we choose as long as it is possible to work through the chain to go from anyone of these statements to any other statement. For example, we can show that
p , p and p p →p . 1
2
2
3
are equivalent by showing that
p
1
→ p3 ,
1
Julan HERNADI
Induksi Matematika
p
3
→ p2 ,
and
Contoh...
Example Buktikan Teorema jika bila
n
2
n bulat positif, maka n ganjil bila hanya
ganjil.
Proof.
n bulat positif. Mis p : ”n ganjil”dan q : ”n ganjil". Pertama, dibuktikan p → q . Diketahui n ganjil, yaitu dapat ditulis n = 2k − 1, k ∈ N. Diperoleh n = (2k − 1) = 4k − 4k + 1 = 2 (2k − 2k ) +1 adalah ganjil. 2
Diketahui
2
2
2
2
|
{z
}
ganjil →n ganjil. Ini dapat n genap →n genap. Tulis n = 2m maka diperoleh n = 4m juga genap. Terbukti p ↔ q . Sebaliknya dibuktikan
q → p, yaitu n
m
2
dibuktikan via kontraposisinya, yaitu 2
Julan HERNADI
2
Induksi Matematika
2
Contoh Lanj . . .
Example
p1 ↔ p2 ↔ p3 dimana : ”n genap, p2 : ”n − 1 ganjil"
Buktikan
p
1
dan
p
3
: ”n2 genap.
Proof. Cukup ditunjukkan dengan rute sbb:
p
3 → p1 .
p
1
→ p2 ,
p
2
→ p3
dan
Atau dengan menggunakan rute lainnya. Prinsipnya,
subrute mudah dibuktikan dan semua terminal terakses. Terminal yang dimaksud adalah pernyataan.
Julan HERNADI
Induksi Matematika
Soal Latihan 1
Buktikan suatu bil bulat positif habis dibagi 9 bila hanya bila jumlah angka-angka pembangunnya habis dibagi 9.
2 3
m = n or m = −n. Show that these statements about the real number x Prove that
m
2
= n2
if and only if
are
equivalent: 1 2 3 4
x is rational, x /2 is rational, and 3x − 1 is rational.
Show that these statements about the real number
x
are
equivalent:
5
1
x
2
3
3
x /2
is irrational,
x +2
is irrational,
is irrational.
Prove that these four statements about the integer equivalent: (i)
n
2
+1
n
2
is odd, (ii) 1 −
n is even, (iii) n
is even. Julan HERNADI
Induksi Matematika
3
n are
is odd, (iv)
