Wednesday, March 13, 2013

Induksi Matematika

Contoh

$1+2+3+\ldots+n=\frac{n\left(n+1\right)}{2}$

Untuk $n=1$ maka $1=\frac{1\left(1+1\right)}{2}$
Untuk $n=2$ maka $1+2=\frac{2\left(2+1\right)}{2}=3$
Untuk $n=3$ maka $1+2+3=\frac{3\left(3+1\right)}{2}=6$
Untuk $n=4$ maka $1+2+3+4=\frac{4\left(4+1\right)}{2}=10$

Pertanyaannya adalah

Bagaimana membuktikan bahwa rumus diatas berlaku untuk semua $n\in\mathbb{N}$ ?

Tentu saja kita tidak mungkin mengecek satu-persatu bilangan asli. Untuk membuktikannnya kita harus menggunakan induksi matematika

Induksi Matematika

Merupakan metode pembuktian untuk membuktikan pernyataan berbentuk

$P\left(n\right)$ : Untuk suatu bilangan asli $n$ berlaku $P$

bahwa $P\left(n\right)$ berlaku untuk semua $n\in\mathbb{N}$ .

Langkah-langkah pada Induksi Matematika

Ada 2 langkah pada Induksi matematika untuk memebuktikan pernyataan $P\left(n\right)$ berlaku untuk semua $n\in\mathbb{N}$ .

Langkah pertama disebut Langkah dasar. Buktikan untuk $n=1$ berlaku $P\left(1\right)$
Langkah kedua disebut Langkah Induksi. Asumsi berlaku untuk $n=k$ berlaku $P\left(k\right)$ , buktikan untuk $n=k+1$ berlaku $P\left(k+1\right)$ .

Contoh

1. Kita buktikan rumus diatas $1+2+3+\ldots+n=\frac{n\left(n+1\right)}{2}$

Langkah dasar: Untuk $n=1$ berlaku

$1=\frac{1\left(1+1\right)}{2}$

Terbukti untuk $n=1$ , selanjutnya

Langkah Induksi: Asumsi untuk $n=k$ berlaku $1+2+3+\ldots+k=\frac{k\left(k+1\right)}{2}$ .

Akan dibuktikan untuk $n=k+1$ berlaku

$1+2+3+\ldots+k+\left(k+1\right)=\frac{k+1\left(\left(k+1\right)+1\right)}{2}$

Inilah yang akan kita buktikan. Berdasarkan asumsi $n=k$ maka sisi kiri dapat ditulis

$\frac{k\left(k+1\right)}{2}+\left(k+1\right)$

Jabarkan:

$\frac{k\left(k+1\right)}{2}+\left(k+1\right)=\frac{k\left(k+1\right)+2\left(k+1\right)}{2}$

$=\frac{k^{2}+3k+2}{2}$

$=\frac{\left(k+1\right)\left(k+2\right)}{2}$

$=\frac{\left(k+1\right)\left(\left(k+1\right)+1\right)}{2}$

Terbukti untuk $n=k+1$ , langkah induksi telah lengkap maka bisa kita simpulkan

$1+2+3+\ldots+n=\frac{n\left(n+1\right)}{2}$

berlaku untuk semua $n\in\mathbb{N}$

2. Buktikan $5^n-1$ habis dibagi 4 untuk setiap bilangan asli $n$

Langkah dasar: Untuk $n=1$ , jelas $5^1-1$ habis dibagi 4

Langkah Induksi: Asumsi untuk $n=k$ berlaku $5^k-1$ habis dibagi 4. Akan dibuktikan $5^{k+1}-1$ habis dibagi 4

$5^{k+1}-1=5.5^k-1$

$=(1+4).5^k-1$

$=5^k+4.5^k-1$

$=(5^k-1)+4.5^k$

berdasarkan asumsi $5^k-1$ habis dibagi 4, begitupula $4.5k$ habis dibagi 4, itu berarti $5^{k+1}-1$ habis dibagi 4.

Langkah induksi telah lengkap maka bisa kita simpulkan $5^n-1$ habis dibagi 4 untuk setiap bilangan asli $n$

3. Buktikan $n!>3^n$ untuk semua $n\geq7$

Untuk contoh ke-3 saya akan menunjukan langkah dasar tidak harus selalu dimulai dari $n=1$ tapi tergantung kondisi. Pada contoh ini langkah dasar dimulai dari $n=7$ , kenapa? Karena persamaan diatas tidak berlaku untuk $n<7$

Langkah dasar: Untuk $n=7$ berlaku

$7!>3^7$

$5040>2187$

Terbukti berlaku untuk $n=7$

Langkah induksi: Asumsi untuk $n\geq7$ berlaku $k!>3^k$ akan dibuktikan $(k+1)!>3^{k+1}$ :

Diketahui $(k+1)!= (k+1)k!$ dengan $k>7$ serta berdasarkan asumsi $k!>3^k$ diperoleh

$(k+1)!=(k+1)k!>(k+1)3^k>3.3^k>3^{k+1}$

Langkah induksi telah lengkap maka bisa disimpulkan $n!>3^n$ untuk semua $n\geq7$

Induksi Matematika

4/ 5

Oleh Wahyu Eko Nugroho

Ditulis Wahyu Eko Nugroho Pada Wednesday, March 13, 2013 Komentar

Tentang Arlina Fitriyani

Invert Pro adalah template premium yang responsive dan SEO Friendly.

Kutipan

Saya pikir semua orang harus belajar coding, Karena coding mengajarkan anda berpikir.
– Steve Jobs, pendiri Apple.

Kebijaksanaan di Facebook adalah meng-hire coder berkualitas sebanyak mungkin. Tapi pasar saat ini tidak menyediakan stock yang cukup..
– Mark Zuckerberg, pendiri Facebook.

Anda tidak harus menjadi jenius untuk bisa coding. Pertambahan, pengurangan... itu sudah cukup!.
– Bill Gates, pendiri Microsoft.

Coders yang hebat adalah rock star masa kini! Titik!.
– Will.i.am, anggota Black Eyed Peas.

Wahyu Eko Nugroho Pemalang

Komentar Terbaru

Wednesday, March 13, 2013