1

INDUKSI MATEMATIKA

Teori bilangan, setidaknya pada aspek dasarnya, sangat memperhatikan sifat-sifat pada bilangan bulat,

terutama bilangan bulat positif (bilangan asli). Hal ini karena bilangan asli telah dikenal manusia yang

paling lama. Bahkan matematikawan Leopold Kronecker pernah mengatakan “Tuhan hanya

menciptakan bilangan asli, dan bilangan lainnya adalah ciptaan manusia”.

Beberapa fakta dasar tentang bilangan bulat akan disampaikan di sini untuk mengingat kembali, seperti

Prinsip Pengurutan yang baik (Well-Ordering Principle).

Setiap himpunan bilangan bulat positif yang tidak kosong memuat setidaknya sebuah elemen

sedemikian hingga untuk seluruh

Karena prinsip ini memainkan peran penting dalam pembuktian di sini dan selanjutnya, marilah kita

menggunakannya untuk menunjukkan bahwa himpunan bilangan bulat positif memiliki apa yang dikenal

sebagai Teorema Archimedes.

Teorema 1. Sifat Archimedes. Jika dan bilangan bulat positif, maka terdapat sebuah bilangan positif

sedemikian sehingga

Bukti. Diasumsikan bahwa pernyataan pada teorema tersebut tidak benar, sehingga untuk beberapa

nilai dan , untuk setiap bilangan positif . Didapat himpunan bilangan bulat positif:

.

Dengan Prinsip Pengurutan yang baik, akan mempunyai elemen terkecil, sebut saja

Selanjutnya maka akan terdapat , memuat bilangan bulat. Lebih lanjut diperoleh:

Hal ini bertentangan dengan penentuan sebagai elemen terkecil dalam Kontradiksi ini timbul

karena asumsi bahwa sifat Archimedes tidak berlaku. Jadi, sifat Archimedes ini terbukti benar.

Di dalam matematika, banyak teorema yang menyatakan bahwa benar untuk semua bilangan bulat

positif . Dalam hal ini yang disebut juga sebagai fungsi proposisi, harus dapat dibuktikan benar

untuk setiap bilangan bulat positif .

Contoh 1. Bagaimana menentukan untuk jumlah dari bilangan ganjil positif yang pertama ?

Misalkan maka jumlah bilangan ganjil positif pertama adalah:

2

Dari nilai-nilai tersebut diperoleh dugaan bahwa jumlah dari bilangan ganjil positif yang pertama

adalah . Namun demikian, dugaan tersebut masih perlu dibuktikan bahwa itu berlaku untuk setiap

bilangan bulat positif .

Contoh 2. Dinyatakan : Jumlah bilangan bulat positif dari 1 sampai adalah .

Umumnya langkah pembuktian sederhana dilakukan dengan mencoba beberapa nilai . Misalkan:

Dst.

Namun sayangnya mencoba beberapa nilai tersebut belum dapat membuktikan bahwa teorema

berlaku untuk setiap bilangan bulat positif .

Untuk pembuktian proposisi-proposisi dalam konteks bilangan bulat (umumnya bilangan bulat positif

atau bilangan asli ) tersebut dapat dibuktikan dengan Induksi Matematika. Induksi matematika

merupakan teknik pembuktian yang baku di dalam matematika. Melalui induksi matematika kita dapat

melakukan pembuktian pada rumus matematika yang memuat himpunan bilangan bulat hanya dalam

sejumlah langkah. Induksi matematika pertama kali diperkenalkan oleh Francesco Maurolico (1494-

1575) pada bukunya Arithmeticorum Libri Duo. Pada bukunya tersebut, induksi matematika digunakan

untuk membuktikan jumlah dari bilangan ganjil positif yang pertama adalah . Pembahasan kali ini

akan meliputi Induksi matematika sederhana dan induksi matematika yang diperumum.

Prinsip Induksi Matematika sederhana dinyatakan sbb:

Fungsi proposisi bernilai benar untuk seluruh jika memenuhi dua langkah berikut:

1. Langkah inisial : verifikasi bahwa bernilai benar.

2. Langkah induksi : jika diasumsikan bernilai benar, maka juga bernilai benar untuk

setiap

Penyelesaian contoh 1. Digunakan induksi matematika untuk membuktikan bahwa jumlah dari

bilangan ganjil positif yang pertama adalah . Fungsi proposisinya sbb:

Perlu pembuktian kebenaran dari proposisi tersebut melalui dua langkah induksi matematika sebagai

berikut:

1.

2. Jika yaitu bernilai benar, maka

juga

bernilai benar. Hal ini dapat dibuktikan sebagai berikut:

3

=

=

=

Langkah 1 dan 2 telah terbukti benar, maka terbukti juga benar bahwa jumlah dari bilangan ganjil

positif yang pertama adalah untuk setiap bilangan asli .

Penyelesaian contoh 2. Jumlah bilangan bulat positif dari 1 sampai adalah . Fungsi

proposisinya dinyatakan sebagai berikut:

Langkah induksi matematika sebagai berikut:

1.

,

2. Jika yaitu

bernilai benar, maka

juga bernilai

benar. Untuk membuktikannya, maka ditunjukkan bahwa:

=

=

=

=

=

=

Jika langkah 1 dan 2 sudah dapat dibuktikan benar, maka untuk setiap bilangan bulat positif terbukti

jumlah bilangan bulat positif dari 1 sampai adalah .

Selain pembuktian untuk rumus matematika yang mengandung unsur deret, induksi matematika juga

dapat digunakan untuk pembuktian rumus matematika dalam unsur kelipatan.

Contoh 3. Untuk setiap bilangan bulat , dapat dibuktikan dengan induksi matematika bahwa

adalah kelipatan 3.

Bukti. Misalkan adalah kelipatan 3 untuk setiap bilangan bulat

1.

2. Jika yaitu merupakan kelipatan 3 bernilai benar, maka juga bernilai benar,

yaitu merupakan kelipatan 3.

Pembuktian ini dapat dilihat pada cara berikut.

4

=

=

=

Diperoleh hasil yaitu jumlah dua bilangan yang merupakan kelipatan 3. Jadi,

untuk setiap bilangan bulat , terbukti adalah kelipatan 3.

Selanjutnya akan ditunjukkan Induksi matematika dapat digunakan dalam pembuktian pertidaksamaan.

Contoh 4. Untuk setiap bilangan asli , dapat dibuktikan bahwa .

Bukti. Misalkan untuk setiap bilangan asli

1.

2. Jika yaitu bernilai benar, maka : juga bernilai

benar. Pembuktiannya sebagai berikut.

.

Pembuktian pada dua langkah induksi matematika telah terbukti benar, maka untuk setiap bilangan asli

terbukti benar.

Terkadang kita perlu membuktikan pernyataan bernilai benar untuk setiap bilangan bulat ,

jadi tidak hanya bilangan bulat yang dimulai dari 1 saja. Maka induksi matematika berikut diperumum

agar mengatasi masalah ini.

Prinsip Induksi Matematika yang Diperumum dinyatakan sbb:

Fungsi proposisi bernilai benar untuk seluruh bilangan bulat nonnegatif melalui dua langkah

berikut:

1. Verifikasi bernilai benar.

2. Jika bernilai benar, maka juga bernilai benar untuk setiap

Sehingga benar untuk setiap bilangan bulat

Contoh 5. Buktikan bahwa untuk setiap bilangan bulat nonnegatif

!

Bukti. Misalkan : untuk setiap bilangan bulat nonnegatif .

1.

,

5

2. Jika : bernilai benar, maka :

juga bernilai benar. Hal ini ditunjukkan sebagai berikut.

Karena kedua langkah sudah diperlihatkan benar, maka untuk setiap bilangan bulat nonnegatif ,

terbukti bahwa

Contoh 6. Buktikan bahwa untuk setiap bilangan bulat !.

Bukti. Misalkan : untuk setiap bilangan bulat .

1.

,

2. Jika : bernilai benar, maka : juga bernilai benar.

Hal ini ditunjukkan sebagai berikut.

Untuk , maka ruas kiri

jelas akan lebih kecil nilainya dari pada ruas kanan . Karena langkah

1 dan 2 sudah ditunjukkan benar, jadi terbukti bahwa untuk setiap bilangan bulat

Latihan

1. Jika terdapat daftar berikut.

Buktikan rumus yang tepat dari daftar deret untuk bilangan bulat !

2. Buktikan bahwa

untuk setiap bilangan bulat

3. Buktikan bahwa

untuk setiap bilangan bulat

4. Buktikan bahwa

untuk setiap bilangan bulat

5. Buktikan bahwa

untuk setiap bilangan bulat

6. Buktikan bahwa habis dibagi 5, untuk setiap bilangan bulat

6

7. Buktikan bahwa habis dibagi 7, untuk setiap bilangan bulat

8. Buktikan bahwa , untuk setiap bilangan bulat

9. Buktikan bahwa , untuk setiap bilangan bulat

10. Buktikan bahwa

, untuk setiap bilangan bulat