pembuktian dengan induksi matematik - ... · pdf file... maka kx2 0, sehingga 1+x +kx +kx2 1+x...
Post on 06-Feb-2018
231 Views
Preview:
TRANSCRIPT
Pembuktian dengan Induksi MatematikContoh Soal
Toni Bakhtiar
Departemen Matematika IPB
September 2012
Toni Bakhtiar (m@thipb) PIM September 2012 1 / 24
Example
Dengan induksi matematik, buktikan bahwa untuk setiap bilangan asli nberlaku
(1× 2) +(2× 22
)+(3× 23
)+ · · ·+ (n× 2n) = (n− 1) 2n+1 + 2.
JawabDefinisikan semesta dan predikat berikut: S = N,
P(n) : (1× 2) +(2× 22
)+ · · ·+ (n× 2n) = (n− 1) 2n+1 + 2.
Basis induksi: untuk n = 1 berlaku
P(1) : 1× 21 = (1− 1)21+1 + 2⇔ P(1) : 2 = 2.
P(1) benar.Hipotesis induksi: untuk k ≥ 1, anggap P(k) benar, yaitu berlaku
(1× 2) +(2× 22
)+(3× 23
)+ · · ·+
(k × 2k
)= (k − 1) 2k+1 + 2.
Toni Bakhtiar (m@thipb) PIM September 2012 2 / 24
Langkah induksi: Akan dibuktikan P(k + 1) benar, yaitu berlaku
(1× 2) +(2× 22
)+ · · ·+
((k + 1)× 2k+1
)= ((k + 1)− 1) 2(k+1)+1 + 2= k · 2k+2 + 2.
Bukti
Ruas kiri = (1× 2) +(2× 22
)+ · · ·+
(k × 2k
)+((k + 1)× 2k+1
)= (k − 1) 2k+1 + 2+
((k + 1)× 2k+1
)= 2k+1 [(k − 1) + (k + 1)] + 2= 2k+1 (2k) + 2
= k · 2 · 2k+1 + 2= k · 2k+2 + 2 = ruas kanan.
Terbukti. �Toni Bakhtiar (m@thipb) PIM September 2012 3 / 24
Example
Buktikan n3 − n habis dibagi 3 untuk setiap n bilangan asli.
Misalkan P(n) : n3 − n habis dibagi 3. Akan dibuktikan bahwa:
(∀n ∈N)P(n).
Basis induksi: untuk n = 1 diperoleh 13 − 1 = 0 habis dibagi 3. P(1)benar.Hipotesis induksi: untuk n = k dan k ≥ 1 andaikan P(k) benar, yaituberlaku
k3 − k habis dibagi 3⇔ k3 − k = 3m, m ∈ Z.
Langkah induksi: untuk n = k + 1 akan dibuktikan P(k + 1) benar, yaitu
(k + 1)3 − (k + 1) habis dibagi 3⇔ (k + 1)3 − (k + 1) = 3r , r ∈ Z.
Toni Bakhtiar (m@thipb) PIM September 2012 4 / 24
Bukti
(k + 1)3 − (k + 1) = k3 + 3k2 + 3k + 1− (k + 1)= (k3 − k) + 3k2 + 3k= 3m+ 3(k2 + k)
= 3(m+ k2 + k)
= 3r , r := m+ k2 + k .
Karena m ∈ Z maka r := m+ k2 + k ∈ Z, sehingga terbukti.
Toni Bakhtiar (m@thipb) PIM September 2012 5 / 24
Example
Misalkan x ≥ −1. Gunakan induksi matematik untuk membuktikan bahwa
(1+ x)n ≥ 1+ nx ,
untuk setiap bilangan asli n.
JawabDefinisikan semesta dan predikat berikut: S = N,
P(n) : (1+ x)n ≥ 1+ nx , x ≥ 1.
Basis induksi: untuk n = 1 berlakuRuas kiri: 1+ xRuas kanan: 1+ x
}Benar bahwa 1+ x ≥ 1+ x
Dengan demikian P(1) benar.Hipotesis induksi: untuk k ≥ 1, anggap P(k) benar, yaitu berlaku
(1+ x)k ≥ 1+ kx .
Toni Bakhtiar (m@thipb) PIM September 2012 6 / 24
Langkah induksi: akan dibuktikan P(k + 1) benar, yaitu berlaku
(1+ x)k+1 ≥ 1+ (k + 1)x .
Bukti Dari hipotesis induksi dan karena x ≥ −1 maka
(1+ x)k ≥ 1+ kx ⇔ (1+ x)k (1+ x) ≥ (1+ kx) (1+ x)⇔ (1+ x)k (1+ x) ≥ 1+ x + kx + kx2.
Karena k bilangan asli, maka kx2 ≥ 0, sehingga
1+ x + kx + kx2 ≥ 1+ x + kx .
Ini berarti
(1+ x)k (1+ x) ≥ 1+ x + kx ⇔ (1+ x)k+1 ≥ 1+ (k + 1) x .
Terbukti. �
Toni Bakhtiar (m@thipb) PIM September 2012 7 / 24
Example
Diberikan barisan bilangan real x1, x2, x3, . . . yang didefinisikan oleh
x1 = 2,
xn+1 = 2− 1xn, n = 1, 2, 3, . . . .
Dengan pembuktian induksi matematik, buktikan bahwa
xn =n+ 1n
, n ≥ 2.
JawabDidefinisikan predikat:
P(n) : xn =n+ 1n
.
Akan dibuktikan dengan induksi matematik bahwa
(∀n ≥ 2)P(n).
Toni Bakhtiar (m@thipb) PIM September 2012 8 / 24
Basis induksi: untuk n = 2, dari definisi diperoleh
x2 = 2−1x1= 2− 1
2=32.
Di lain pihak, dari rumus analitik diperoleh
x2 =2+ 12
=32
(benar).
Hipotesis induksi: untuk n = k andaikan benar bahwa
xk =k + 1k
.
Langkah induksi: untuk n = k + 1 akan dibuktikan bahwa
xk+1 =(k + 1) + 1k + 1
=k + 2k + 1
.
Toni Bakhtiar (m@thipb) PIM September 2012 9 / 24
Bukti
xk+1 = 2− 1xk
(dari definisi)
= 2− 1k+1k
(dari hipotesis)
= 2− kk + 1
=k + 2k + 1
.
Terbukti. �
Toni Bakhtiar (m@thipb) PIM September 2012 10 / 24
Example
Gobang adalah mata uang resmi Negeri Artamaya denganpecahan-pecahan yang berlaku adalah suku (= 2 gobang), benggol (= 5gobang), ketip (= 7 gobang), dan kawung (= 10 gobang). Di suatukejadian aneh, seorang penjual barang kelontong yang hanya memilikisejumlah pecahan benggol sebagai uang kembalian kedatangan seorangpembeli yang hanya memiliki sejumlah pecahan ketip. Buktikan bahwasetiap transaksi atas barang kelontong seharga n gobang, dengan n ≥ 25dan n bilangan asli, selalu dapat dilakukan dengan hanya menggunakanpecahan-pecahan benggol dan ketip tanpa menimbulkan utang-piutangantara penjual dan pembeli. Ilustrasi: Jika harga barang 50 gobang makapembeli membayar dengan 10 keping uang ketip dan mendapat kembalian4 keping uang benggol.
Petunjuk: Buktikan dengan induksi matematik bahwa setiap bilangan aslin, dengan n ≥ 25, selalu dapat dituliskan sebagai n = 7x − 5y ,dengan xdan y adalah suatu bilangan bulat positif.
Toni Bakhtiar (m@thipb) PIM September 2012 11 / 24
JawabMasalah di atas ekuivalen dengan masalah berikut: dengan induksimatematik, buktikan bahwa setiap bilangan asli n, dengan n ≥ 25, selaludapat dituliskan sebagai
nharga
= 7xbayar− 5ykembalian
,
dengan x dan y adalah bilangan-bilangan bulat positif.Basis induksi: untuk n = 25 diperoleh
25 = 7 · 5− 5 · 2
sehingga diperoleh x = 5 dan y = 2 (Benar).Hipotesis induksi: untuk n = k anggap benar bahwa
k = 7a− 5b
dengan a dan b suatu bilangan bulat positif.
Toni Bakhtiar (m@thipb) PIM September 2012 12 / 24
Langkah induksi: untuk n = k + 1 akan dibuktikan bahwa
k + 1 = 7p − 5q
dengan p dan q suatu bilangan bulat positif.Bukti
k + 1 = (7a− 5b) + 1 (dari hipotesis induksi)
= 7a− 5b+ (7 · 3− 5 · 4)= 7(a+ 3)− 5(b+ 4)= 7p − 5q, dengan p := a+ 3 dan q := b+ 4.
Karena a dan b bilangan bulat positif maka p := a+ 3 dan q := b+ 4bilangan bulat positif. Terbukti. �
Toni Bakhtiar (m@thipb) PIM September 2012 13 / 24
Example
Buktikan untuk setiap bilangan asli n berlaku
12 + 22 + · · ·+ (n− 1)2 < n3
3.
JawabDidefinisikan predikat:
P(n) : 12 + 22 + · · ·+ (n− 1)2 < n3
3.
Akan dibuktikan dengan induksi matematik bahwa
(∀n ∈N)P(n).
Toni Bakhtiar (m@thipb) PIM September 2012 14 / 24
Basis induksi: untuk n = 1 diperoleh P(1) : (1− 1)2 < 133 ⇔ 0 < 1
3 .P(1) benar.Hipotesis induksi: untuk n = k dan k ≥ 1 andaikan P(k) benar, yaituberlaku
12 + 22 + · · ·+ (k − 1)2 < k3
3.
Langkah induksi: untuk n = k + 1 akan dibuktikan P(k + 1) benar, yaitu
12 + 22 + · · ·+ (k − 1)2 + k2 < (k + 1)3
3.
Toni Bakhtiar (m@thipb) PIM September 2012 15 / 24
Bukti:
12 + 22 + · · ·+ (k − 1)2 + k2 <k3
3+ k2
=k3
3+3k2
3
<k3
3+3k2
3+3k3+13
=k3 + 3k2 + 3k + 1
3
=(k + 1)3
3.
Toni Bakhtiar (m@thipb) PIM September 2012 16 / 24
Example
Buktikan untuk setiap bilangan asli n ≥ 10 berlaku
2n > n3.
JawabDidefinisikan predikat:
P(n) : 2n > n3.
Akan dibuktikan dengan induksi matematik bahwa
(∀n ≥ 10)P(n).
Toni Bakhtiar (m@thipb) PIM September 2012 17 / 24
Basis induksi: untuk n = 10 diperolehP(10) : 210 > 103 ⇔ 1024 > 1000. P(10) benar.Hipotesis induksi: untuk n = k dan k ≥ 10 andaikan P(k) benar, yaituberlaku
2k > k3.
Langkah induksi: untuk n = k + 1 akan dibuktikan P(k + 1) benar, yaitu
2k+1 > (k + 1)3.
Toni Bakhtiar (m@thipb) PIM September 2012 18 / 24
Bukti:
2k+1 = 2 · 2k
> 2 · k3
= k3 + k3
≥ k3 + 10k2 (k ≥ 10⇔ k3 ≥ 10k2)= k3 + 3k2 + 7k2
≥ k3 + 3k2 + 70k (k ≥ 10⇔ k2 ≥ 10k ⇔ 7k2 ≥ 70k)> k3 + 3k2 + 3k + 1
= (k + 1)3.
Toni Bakhtiar (m@thipb) PIM September 2012 19 / 24
ProblemDidefinisikan barisan bilangan a1, a2, a3, . . . dengan
a1 = 1,
a2 = 1+ 12 ,
a3 = 1+ 12 +
13 ,
...
an = 1+ 12 + · · ·+
1n , untuk semua bilangan asli n.
Buktikan untuk semua bilangan asli n berlaku
a1 + a2 + · · ·+ an = (n+ 1)an − n.
Toni Bakhtiar (m@thipb) PIM September 2012 20 / 24
ProblemDiketahui barisan bilangan y1, y2, y3, . . . dengan
y1 = 1,
yn+1 = 14 (2yn + 3) , untuk n = 1, 2, . . . .
Dengan menggunakan induksi matematik, tunjukkan bahwa yn ≤ 2 untuksetiap bilangan asli n.
ProblemDiketahui barisan bilangan x1, x2, x3, . . . dengan
x1 = 1
xn+1 =√2√xn, untuk n = 1, 2, 3, . . . .
Dengan menggunakan induksi matematik buktikan bahwa xn ≤ xn+1untuk setiap bilangan asli n.
Toni Bakhtiar (m@thipb) PIM September 2012 21 / 24
ProblemDiketahui barisan bilangan bulat x1, x2, x3, . . . yang didefinisikan oleh
x1 = 2,
xn = xn−1 + 2n, (untuk n ≥ 2).
Tunjukkan dengan induksi matematik bahwa untuk semua bilangan asli n,berlaku:
xn = n(n+ 1).
ProblemDengan menggunakan induksi matematik, buktikan bahwa
13 + 23 + 33 + · · ·+ n3 > n4
4.
adalah benar untuk setiap bilangan asli n. (Diketahui:(a+ b)4 = a4 + 4a3b+ 6a2b2 + 4ab3 + b4.)
Toni Bakhtiar (m@thipb) PIM September 2012 22 / 24
ProblemDengan induksi matematik, buktikan bahwa untuk bilangan asli n berlaku
42n+1 + 3n+2 habis dibagi 13.
ProblemDengan menggunakan induksi matematik buktikan bahwa untuk setiapbilangan asli n berlaku:
3+ 11+ · · ·+ (8n− 5) = 4n2 − n.
Problem
Misalkan a bilangan real dan a 6= 1. Dengan induksi matematik, tunjukkanbahwa
1+ a+ a2 + · · ·+ an−1 = 1− an1− a
untuk setiap bilangan asli n.
Toni Bakhtiar (m@thipb) PIM September 2012 23 / 24
ProblemPerhatikan deret berikut:
Sn =n
∑i=1
i(i + 1)!
.
1 Hitung S1, S2, dan S3. Dengan memerhatikan pola yang terbentuk,tebaklah bentuk dari Sn.
2 Dengan menggunakan induksi matematik, buktikan tebakan Anda.
Toni Bakhtiar (m@thipb) PIM September 2012 24 / 24
top related