Prinsip Induksi Kuat

Selain Prinsip Induksi Matematika ‘biasa’ yang telah dibahas pada hari Sabtu yang lalu, ada Prinsip Induksi Kuat. Misalkan P(n) adalah pernyataan yang terkait dengan bilangan asli n. Prinsip Induksi Kuat berbunyi sebagai berikut: Jika

  • P(1) benar, dan
  • jika P(1),\dots, P(k) benar, maka P(k+1) benar,

maka P(n) benar untuk setiap bilangan asli n.

Baik Prinsip Induksi Matematika maupun Prinsip Induksi Kuat dapat diperumum untuk pernyataan P(n) dengan n\ge n_0 (alih-alih n\ge 1.) Persisnya, jika

  • P(n_0) benar, dan
  • jika P(k) benar, maka P(k+1) benar,

maka P(n) benar untuk setiap bilangan asli n\ge n_0.

Demikian juga jika

  • P(n_0) benar, dan
  • jika P(n_0),\dots, P(k) benar, maka P(k+1) benar,

maka P(n) benar untuk setiap bilangan asli n\ge n_0.

Contoh aplikasi Prinsip Induksi Kuat adalah dalam pembuktian Teorema Dasar Aritmetik, yang menyatakan bahwa setiap bilangan asli n \ge 2 dapat dinyatakan secara tunggal sebagai hasil kali bilangan-bilangan prima.

Jelas bahwa pernyataan di atas benar untuk n=2, karena 2 adalah bilangan prima dan 2 = 2. Selanjutnya misalkan pernyataan benar untuk n=2,\dots,k. Kita akan menyelidiki kebenaran pernyataan untuk n=k+1. Jika k+1 adalah bilangan prima, maka pernyataan tentu saja benar. Jadi, misalkan k+1 bukan bilangan prima. Dalam hal ini, k+1 mempunyai faktor prima, sebutlah p, sehingga k+1=pq, dengan p, q<k+1. Di sini q mungkin merupakan bilangan komposit, tetapi — menurut hipotesis — q dapat ditulis sebagai hasil kali bilangan-bilangan prima. Jadi, k+1 pun dapat dinyatakan sebagai hasil kali bilangan-bilangan prima.

*

Bandung, 09-02-2019

Advertisements

Leave a Reply

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s