Induksi matematika

Misalkan saya punya rumus

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

mari kita lihat

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

Nah pertanyaannya adalah

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

Tentu saja kita mustahil 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}.

  1. Langkah pertama disebut Langkah dasar. Buktikan untuk n=1 berlaku  P\left(1\right)
  2. 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).

Keabsahan dari 2 langkah dari induksi matematika dijamin oleh Postulate Peano (PP). Karena sebenarnya induksi matematika merupakan postulate ke-3 dari PP.

Contoh

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

Langkah dasar: Untuk n=1 berlaku

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

Terbukti untuk n=1, selanjutnya

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

Akan dibuktikan untuk n=k+1 berlaku

{\displaystyle 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

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

Jabarkan:

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

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

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

{\displaystyle =\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

  {\displaystyle 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^kdiperoleh

(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

2 thoughts on “Induksi matematika

Silahkan, tinggalkan komentar

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s