Pembuktian dengan Induksi Matematik

Pembuktian dengan Induksi Matematik Contoh 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 n berlaku

(1

22 + 3

2) + 2

23 +

+ (n

2n ) = (n

1) 2n +1 + 2.

Jawab De…nisikan 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

P (1) benar. Hipotesis induksi: untuk k

(1

2) + 2

22 + 3

Toni Bakhtiar (m@thipb)

1)21 +1 + 2 , P (1) : 2 = 2. 1, anggap P (k ) benar, yaitu berlaku

23 +

+ k PIM

2k

= (k

1) 2k +1 + 2. 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

= (k = = = =

2) + 2

22 +

+ k

1) 2k +1 + 2 + (k + 1)

2k +1 [(k

2k + (k + 1)

2k +1

2k +1

1) + (k + 1)] + 2

k +1

(2k ) + 2 k 2 2k +1 + 2 k 2k +2 + 2 = ruas kanan. 2

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:

(8n 2 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, yaitu berlaku k 3 k habis dibagi 3 , k 3 k = 3m, m 2 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

Toni Bakhtiar (m@thipb)

PIM

(k + 1) = 3r , r 2 Z. September 2012

4 / 24

Bukti

(k + 1)3

(k + 1) = = = = =

k 3 + 3k 2 + 3k + 1 3

(k + 1)

2

(k k ) + 3k + 3k 3m + 3(k 2 + k ) 3(m + k 2 + k ) 3r , r := m + k 2 + k.

Karena m 2 Z maka r := m + k 2 + k 2 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. Jawab De…nisikan semesta dan predikat berikut: S = N, P (n ) : (1 + x )n

1 + nx, x

1.

Basis induksi: untuk n = 1 berlaku Ruas kiri: 1 + x Benar bahwa 1 + x 1 + x Ruas kanan: 1 + x Dengan demikian P (1) benar. Hipotesis induksi: untuk k 1, anggap P (k ) benar, yaitu berlaku

(1 + x )k Toni Bakhtiar (m@thipb)

1 + kx. 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 + x )k

1 + kx

1 maka

, (1 + x )k (1 + x ) k

, (1 + x ) (1 + x )

Karena k bilangan asli, maka kx 2

(1 + kx ) (1 + x ) 1 + x + kx + kx 2 .

0, sehingga

1 + x + kx + kx 2

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 dide…nisikan oleh x1 = 2, 1 , xn

xn +1 = 2

n = 1, 2, 3, . . . .

Dengan pembuktian induksi matematik, buktikan bahwa xn =

n+1 , n

n

2.

Jawab Dide…nisikan predikat:

n+1 . n Akan dibuktikan dengan induksi matematik bahwa P (n ) : xn =

(8n Toni Bakhtiar (m@thipb)

2)P (n ). PIM

September 2012

8 / 24

Basis induksi: untuk n = 2, dari de…nisi diperoleh x2 = 2

1 =2 x1

1 3 = . 2 2

Di lain pihak, dari rumus analitik diperoleh x2 =

3 2+1 = 2 2

(benar).

Hipotesis induksi: untuk n = k andaikan benar bahwa xk =

k +1 . k

Langkah induksi: untuk n = k + 1 akan dibuktikan bahwa xk +1 =

Toni Bakhtiar (m@thipb)

(k + 1) + 1 k +2 = . k +1 k +1 PIM

September 2012

9 / 24

Bukti xk + 1 = 2

= 2

1 (dari de…nisi) xk 1 (dari hipotesis) k +1 k

k k +1 k +2 . k +1

= 2 = Terbukti.

Toni Bakhtiar (m@thipb)

PIM

September 2012

10 / 24

Example Gobang adalah mata uang resmi Negeri Artamaya dengan pecahan-pecahan yang berlaku adalah suku (= 2 gobang), benggol (= 5 gobang), ketip (= 7 gobang), dan kawung (= 10 gobang). Di suatu kejadian aneh, seorang penjual barang kelontong yang hanya memiliki sejumlah pecahan benggol sebagai uang kembalian kedatangan seorang pembeli yang hanya memiliki sejumlah pecahan ketip. Buktikan bahwa setiap transaksi atas barang kelontong seharga n gobang, dengan n 25 dan n bilangan asli, selalu dapat dilakukan dengan hanya menggunakan pecahan-pecahan benggol dan ketip tanpa menimbulkan utang-piutang antara penjual dan pembeli. Ilustrasi: Jika harga barang 50 gobang maka pembeli membayar dengan 10 keping uang ketip dan mendapat kembalian 4 keping uang benggol. Petunjuk: Buktikan dengan induksi matematik bahwa setiap bilangan asli n, dengan n 25, selalu dapat dituliskan sebagai n = 7x 5y ,dengan x dan y adalah suatu bilangan bulat positif. Toni Bakhtiar (m@thipb)

PIM

September 2012

11 / 24

Jawab Masalah di atas ekuivalen dengan masalah berikut: dengan induksi matematik, buktikan bahwa setiap bilangan asli n, dengan n 25, selalu dapat dituliskan sebagai n = 7x

harga

bayar

5y

,

kembalian

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 + 4 bilangan 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

Jawab Dide…nisikan predikat: P (n ) : 12 + 22 +

+ (n

1)2 <

n3 . 3

Akan dibuktikan dengan induksi matematik bahwa

(8n 2 N)P (n).

Toni Bakhtiar (m@thipb)

PIM

September 2012

14 / 24

3

Basis induksi: untuk n = 1 diperoleh P (1) : (1 1)2 < 13 , 0 < 13 . P (1) benar. Hipotesis induksi: untuk n = k dan k 1 andaikan P (k ) benar, yaitu berlaku k3 12 + 22 + + (k 1)2 < . 3 Langkah induksi: untuk n = k + 1 akan dibuktikan P (k + 1) benar, yaitu 12 + 22 +

Toni Bakhtiar (m@thipb)

+ (k

1)2 + k 2 <

PIM

(k + 1)3 . 3

September 2012

15 / 24

Bukti: 12 + 22 +

+ (k

1)2 + k 2 <

= < = =

Toni Bakhtiar (m@thipb)

PIM

k3 + k2 3 k3 3k 2 + 3 3 k3 3k 2 3k 1 + + + 3 3 3 3 k 3 + 3k 2 + 3k + 1 3 (k + 1)3 . 3

September 2012

16 / 24

Example Buktikan untuk setiap bilangan asli n

10 berlaku

2n > n3 . Jawab Dide…nisikan predikat: P ( n ) : 2n > n 3 . Akan dibuktikan dengan induksi matematik bahwa

(8n

Toni Bakhtiar (m@thipb)

10)P (n ).

PIM

September 2012

17 / 24

Basis induksi: untuk n = 10 diperoleh P (10) : 210 > 103 , 1024 > 1000. P (10) benar. Hipotesis induksi: untuk n = k dan k 10 andaikan P (k ) benar, yaitu berlaku 2k > k 3 . 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 k 3 + 10k 2 (k 10 , k 3 10k 2 ) = k 3 + 3k 2 + 7k 2 k 3 + 3k 2 + 70k (k 10 , k 2 10k , 7k 2 > k 3 + 3k 2 + 3k + 1 = (k + 1)3 .

Toni Bakhtiar (m@thipb)

PIM

70k )

September 2012

19 / 24

Problem Dide…nisikan barisan bilangan a1 , a2 , a3 , . . . dengan a1 = 1, a2 = 1 + 12 , a3 = 1 + .. . an

1 2

+ 13 ,

= 1 + 12 +

+ n1 , untuk semua bilangan asli n.

Buktikan untuk semua bilangan asli n berlaku a 1 + a2 +

Toni Bakhtiar (m@thipb)

+ an = ( n + 1 ) an

PIM

n.

September 2012

20 / 24

Problem Diketahui barisan bilangan y1 , y2 , y3 , . . . dengan y1 = 1, yn +1 =

1 4

(2yn + 3) , untuk n = 1, 2, . . . .

Dengan menggunakan induksi matematik, tunjukkan bahwa yn setiap bilangan asli n.

2 untuk

Problem Diketahui barisan bilangan x1 , x2 , x3 , . . . dengan x1 = 1 p p xn +1 = 2 xn , untuk n = 1, 2, 3, . . . . Dengan menggunakan induksi matematik buktikan bahwa xn untuk setiap bilangan asli n. Toni Bakhtiar (m@thipb)

PIM

xn +1

September 2012

21 / 24

Problem Diketahui barisan bilangan bulat x1 , x2 , x3 , . . . yang dide…nisikan 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). Problem Dengan menggunakan induksi matematik, buktikan bahwa 13 + 23 + 33 +

+ n3 >

n4 . 4

adalah benar untuk setiap bilangan asli n. (Diketahui: (a + b )4 = a4 + 4a3 b + 6a2 b2 + 4ab3 + b4 .) Toni Bakhtiar (m@thipb)

PIM

September 2012

22 / 24

Problem Dengan induksi matematik, buktikan bahwa untuk bilangan asli n berlaku 42n +1 + 3n +2 habis dibagi 13. Problem Dengan menggunakan induksi matematik buktikan bahwa untuk setiap bilangan asli n berlaku: 3 + 11 +

+ (8n

5) = 4n2

n.

Problem Misalkan a bilangan real dan a 6= 1. Dengan induksi matematik, tunjukkan bahwa 1 an 1 + a + a2 + + an 1 = 1 a untuk setiap bilangan asli n. Toni Bakhtiar (m@thipb)

PIM

September 2012

23 / 24

Problem Perhatikan deret berikut: n

Sn =

i

∑ (i + 1) ! .

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