Induksi matematika

Posted on October 6, 2011 by Nursatria

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

About Nursatria

Seorang Alumnus Matematika UGM, dengan ilmu yang didapat ketika kuliah (Padahal sering bolos kuliah :p ), saya menyebarkan virus matematika
This entry was posted in pembuktian and tagged , , . Bookmark the permalink.

5 Responses to Induksi matematika

  1. Pingback: Pembuktian Prinsip Pengurutan yang Baik | Blog Matematika Pak Satria

  2. Pingback: Semua orang Indonesia berumur sama | Aria Turns

  4. zibul says:
    November 8, 2011 at 06:56

    wah induksi math di matkul anreal ni,, mas aria mau nanya utk rumus2 math anda make software apa supaya bisa diupload di blog? mksh

    Reply

Silahkan, tinggalkan komentar

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

Gravatar
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 )

Cancel

Connecting to %s