1.3. Induksi MatematikaPrinsip dari induksi matematika merupakan alat yang penting untuk

membuktikan hasil dari bilangan bulat. Pertama kita akan menjelaskan prinsip ini kemudian menunjukkan bagaimana prinsip ini digunakan. Setelah itu, kita akan gunakan prinsip keteraturan untuk menunujukkan bahwa teknik induksi matematika adalah benar. Dalam pembelajaran kita pada teori bilangan, kita akan menggunakan keduanya dari sifat keteraturan dan prinsip induksi matematika dalam banyak hal.

Teorema 1.2 Prinsip Induksi Matematika. Jika sebuah himpuana dari bilangan bulat positif memuat 1, dan untuk setiap bilangan bulat positif n, memuat n + 1 jika memuat n, maka himpunan tersebut merupakan himpunan dari semua bilangan bulat positif.

Kita perlu melakukan dua hal untuk melakukan pembuktian menggunakan induksi matematika sehingga hasilnya benar untuk setiap bilangan bulat positif. Pertama, kita harus menunjukkan bahwa hasilnya benar untuk bilangan bulat 1. Hal ini disebut dengan tahap dasar. Kedua, kita harus menunjukkan untuk setiap bilangan bulat positif n maka hasilnya benar untuk bilangan bulat positif n+1 jika hasilnya benar untuk bilangan bulat positif n. Hal ini disebut dengan tahap induksi. Salah satu dari dua tahap tersebut adalah lengkap, melalui prinsip induksi matematika kita akan menyimpulkan bahwa pernyataan bernilai benar untuk himpunan semua bilangan bulat positif.

Kita ilustrasikan bagaimana induksi matematika bekerja melalui beberapa contoh. Pertama kita membuktikan sebuah pertidaksamaan.

Contoh 1.7. kita akan tunjukkan dengan induksi matematika bahwa n! ≤ nn untuk setiap bilangan bulat positif n. Tahap dasar, yaitu bentuk dimana n = 1, terpenuhi karena 1! = 1 ≤ 11 = 1. Sekarang asumsikan bahwa n! ≤ nn ; yang merupakan hipotesis induksi. Untuk melengkapi bukti kita harus menunjukkan, melalui asumsi bahwa hipotesis induksi ini benar, bahwa (n + 1)! ≤ (n + 1)n+1 . Menggunakan hipotesis induksi kita memiliki

(n + 1)! = (n + 1).n!≤ (n + 1)nn

≤ (n + 1)(n + 1)n

≤ (n + 1)n + 1.

Hal ini melengkapi kedua tahap induksi dan terbukti.Satu dari aplikasi yang paling umum pada induksi matematika adalah

pembuktian rumus eksplisit dari penjumlahan. Biasanya kita dapat menduga sebuah rumus dari beberapa bentuk awal, dan kemudian menggunakan induksi matematika untuk memperkuat dugaan kita, jika hal tersebut memang benar. (Catatan bahwa induksi matematika dapat pula hanya digunakan untuk membuktikan rumus penjumlahan dan tidak menemukan beberapa rumus.) Perhatikan contoh berikut.

Contoh 1.8. Dengan menguji penjumlahan dari n bilangan bulat positif ganjil untuk nilai kecil n kita duga sebuah rumus dari penjumlahan. Kita miliki

1 = 1,1 + 3 = 4,

1 + 3 + 5 = 9,1 + 3 + 5 + 7 = 16,

1 + 3 + 5 + 7 + 9 = 25,1 + 3 + 5 + 7 + 9 + 11 = 36.

Dari nilai – nilai tersebut, kita duga bahwa ∑j=1

n

(2 j−1 )=1+3+5+7+…+2n−1=n2

untuk setiap bilangan bulat positif n.Sekarang kita mencoba membuktikan dugaan ini menggunakan induksi matematika. (Jelas percobaan ini akan gugur jika pendapat kita salah.) Berikut tahap dasar

∑j=1

1

(2 j−1 )=2.1−1=1=12. Pada tahap induksi, kita anggap bahwa rumus berlaku

untuk n. Kita harus menunjukkan bahwa anggapan terhadap rumus ini juga berlaku

untuk n + 1. Kita asumsikan bahwa ∑j=1

n

(2 j−1 )=n2. Menggunakan hipotesis induksi

kita mempunyai

∑j=1

n+1

(2 j−1 )=∑j=1

n

(2 j−1 )+2 (n+1 )−1

¿n2+2 (n+1 )−1¿n2+2n+1¿(n+1)2

Karena tahap dasar dan tahap induksi keduanya terpenuhi, maka rumus di atas memenuhi.

Deret geometri merupakan deretan bilangan bulat yang setiap bentuknya adalah perkalian tetap pada bentuk sebelumnya. Akan sering kita butuhkan bentuk penjumlahan dari deret tersebut. Setelah memberikan definisi formal dari deret geometri, kita akan menggunakan induksi matematika untuk menentukan rumus untuk penjumlahan pada bentuk deret tersebut.Definisi. Diberikan bilangan real a dan r, bilangan real

a, ar2, ar3, ...disebut bentuk deret geometri. Selain itu, a disebut dengan bentuk awal dan r disebut dengan rasio.Contoh 1.9. Bilangan – bilangan 5, -15, 45, -135, ... merupakan sebuah deret geometri dengan bentuk awal 5 dan rasio -3.

Kita berikan sebuah rumus eksplisit penjumlahan n secara berurutan dari deret geometri pada contoh berikut.Contoh 1.10. Akan kita buktikan bahwa jika a dan r adalah bilangan real dan r ≠ 1, maka untuk setiap bilangan bulat positif n

(1.4) ∑j=0

n

ar j=a+ar+a r2+…+ar n=a rn−ar−1

.

Untuk membuktikan bahwa rumus ini benar kita lengkapi dengan tahap dasar, sehingga kita harus menunjukkan terlebih dulu bahwa rumus tersebut berlaku pada n = 1. Selanjutnya kita lengkapi dengan tahap induksi, sehingga kita harus menunjukkan bahwa jika rumus berlaku untuk bilangan bulat positif n , maka rumus juga berlaku pada bilangan bulat positif n + 1.Untuk memulai kita anggap n = 1. Maka pada ruas kiri dari (1.4) adalah a + ar, sedangkan pada ruas kanan dari (1.4) kita mempunyai

ar2−ar−1

=a(r2−1)r−1

=a(r+1)(r−1)r−1

=a (r+1 )=a+ar.

Sehingga rumus tersebut benar saat n = 1.Sekarang kita asumsikan bahwa rumus tersebut berlaku untuk bilangan bulat

positif n. Selanjutnya kita asumsikan bahwa

(1.5) a+ar+a r2+…+a rn=a rn−ar−1

.

Akan kita tunjukkan bahwa rumus juga berlaku pada bilangan bulat positif n + 1. Sehingga kita tunjukkan bahwa

(1.6) a+ar+a r2+…+arn+arn+1=ar (n+1)+1−ar−1

=arn+2−ar−1

.

Untuk menunjukkan bahwa (1.6) valid, kita tambahkan arn+1 pada kedua ruas pada (1.5), untuk memperoleh

(1.7) (a+ar+a r2+…+arn )+a r n+1=arn+1−ar−1

+a r n+1

Pada ruas kiri pada (1.7) sama dengan ruas kiri pada (1.6). untuk menunjukkan bahwa ruas kanan sama, kita perhatikan bahwa

a rn+1−ar−1

+a rn+1=arn+1−a

r−1+

arn+1 (r−1 )r−1

¿ a rn+1−a+a r n+2−a rn+1

r−1

¿ arn+2−ar−1

.

Karena kita telah menunjukkan bahwa (1.5) berimplikasi dengan (1.6), kita dapat menyimpulkan bahwa (1.4) berlaku untuk semua bilangan bulat n.

Contoh berikutnya mengilustrasikan penggunaan dari penggunaan rumus pada contoh 1.10.Contoh 1.11. Misalkan n bilangan bulat positif. Tentukan jumlah dari

∑k=0

n

2k=1+2+22+…+2n .

Kita gunakan contoh 1.10 dengan a=1 dan r=2, untuk memperoleh

1+2+22+…+2n=2n+1−12−1

=2n+1−1.

Karena itu, jumlah dari pangkat tak negatif berurutan dari 2 adalah satu kurangnya dari pangkat terbesar dari 2 berikutnya.

Sekarang kita berikan bukti bahwa prinsip induksi matematika mengikuti prinsip keteraturan.Bukti. Misalkan S merupakan himpunan bilangan bulat positif yang memuat bilangan bulat 1 dan bilangan bulat n + 1 sedemikian hingga S memuat n. Asumsikan bahwa S adalah himpunan tak kosong dari semua bilangan bulat positif. Oleh karena itu, ada suatu bilangan bulat positif yang tidak berada pada S. Menggunakan sifat keteraturan, karena himpunan bilangan bulat positif yang tidak berada pada S tidak kosong, maka ada bilangan bulat positif terkecil n yang tidak ada dalam S. Perhatikan bahwa n ≠ 1, karena 1 berada pada S. Sekarang karena n > 1 (ada bilangan bulat tak positif n dengan n < 1; perhatikan latihan 8 pada subbab 1.1), maka bilangan bulat n – 1 adalah bilangan bulat positif yang lebih kecil dari n, sehingga n – 1 berada pada S. Tetapi karena S memuat n – 1, maka S juga memuat (n – 1) + 1 = n, yang mengakibatkan kontradiksi, karena menurut dugaan n adalah bilangan bulat positif terkecil yang tidak berada pada S. Hal ini menunjukkan bahwa S merupakan himpunan semua bilangan bulat positif.Sedikit perbedaan pada prinsip induksi matematika adalah terkadang juga berguna dalam pembuktian.Teorema 1.3. Prinsip Kedua dari Induksi Matematika. Sebuah himpunan dari bilangan bulat positif yang memuat bilangan bulat 1, dan yang memiliki sifat bahwa untuk setiap bilangan bulat positif n jika himpunan tersebut memuat semua bilangan bulat positif 1, 2, ..., n, maka himpunan tersebut juga memuat bilangan bulat n + 1, maka himpunan tersebut merupakan himpunan semua bilangan bulat positif.

Sebelum membuktikan bahwa prinsip kedua dari induksi matematika valid, akan kita berikan sebuah contoh untuk mengilustrasikan penggunaan prinsip tersebut.Contoh 1.12. Akan kita tunjukkan bahwa setiap perangko lebih dari satu sen dapat dibentuk oleh tanda dua-sen dan tiga-sen. Untuk tahap dasar, perhatikan bahwa perangko tanda dua-sen dapat dibentuk oleh satu tanda dua-sen dan perangko tiga-sen dapat dibentuk oleh satu tanda tiga-sen. Pada tahap induksi, asumsikan bahwa setiap perangko yang tidak melebihi n sen, n ≥ 3, dapat dibentuk oleh tanda dua-sen dan tiga-sen. Sehingga sebuah perangko n + 1 sen dapat dibentuk dengan membentuk sebuah perangko n – 1 sen dan sebuah tanda dua-sen. Sehingga kasus di atas terbukti. (Kasus ini juga dapat di buktikan dengan menggunakan prinsip induksi matematika yang dapat dibuktikan oleh pembaca).

Sekarang akan kita buktikan bahwa prinsip kedua induksi matematika merupakan teknik yang valid.Bukti. Misalkan T merupakan himpunan bilangan bulat yang memuat 1 dan demikian pula dengan semua bilangan bulat positif n jika T memuat 1, 2, ..., n., maka T juga memuat n + 1. Misalkan S merupakan himpunan semua bilangan bulat positif n sedemikian sehingga semua bilangan bulat positif kurang dari atau sama dengan n berada pada T. Maka 1 berada pada S, dan dengan hipotesis, kita perhatikan bahwa jika n berada pada S, maka n + 1 berada pada S. Akibatnya, dengan menggunakan prinsip induksi matematika, S merupakan himpunan semua bilangan bulat positif, sehingga jelas bahwa T juga himpunan semua bilangan bulat positif, karena S merupakan subset dari T.

Definisi BerulangPrinsip dari pembuktian induksi matematika merupakan sebuah metode yang

menggambarkan nilai dari fungsi pada bilangan bulat positif. Lebih spesifiknya nilai fungsi pada n kita berikan nilai fungsi pada 1 dan memberikan kebenaran dari penemuan pada setiap bilangan bulat positif n nilai fungsi pada n + 1 dari nilai fungsi pada n.Definisi. Kita katakan bahwa fungsi f didefinisikan secala berulang jika nilai dari f pada 1 tetap dan jika untuk setiap bilangan bulat positif n sebuah aturan dibuktikan untuk menentukan f(n + 1) dari f(n).

Prinsip induksi matematika dapat digunakan untuk menunjukkan bahwa fungsi yang didefinisikan secara berulang didefinisikan secara khusus pada setiap bilangan bulat positif. (Perhatikan latihan 29 pada akhir subbab ini.) Kita ilustrasikan bagaimana mendefinisikan sebuah fungsi berulang dengan definisi sebelumnya.

Contoh 1.13. Akan kita ulangi definisi fungsi faktorial f(n) = n!. Pertama, kita tetapkan bahwa

f(1) = 1.Maka kita berikan ketentuan untuk menemukan f(n + 1) dari f(n) untuk setiap bilangan bulat positif, yaitu

f(n + 1) = (n + 1).f(n).Dua pernyataan ini secara khusus didefinisikan dengan n!

Untuk menemukan nilai dari f(6) = 6! dari definisi berulang, gunakan sifat kedua berturut – turut, seperti berikut:f(6) = 6.f(5) = 6.5.f(4) = 6.5.4.f(3) = 6.5.4.3.f(2) = 6.5.4.3.2.f(1).Selanjutnya gunakan pernyataan pertama dari definisi untuk merubah f(1) dengan menyatakan nilai 1, untuk memperoleh

6! = 6.5.4.3.2.1 = 720.Prinsip kedua dari induksi matematika juga berfungsi sebagai dasar dari

definisi berulang. Kita dapat definisikan sebuah fungsi yang domainnya himpunan bilangan bulat positif dengan menetapkan nilai fungsi tersebut pada 1 dan diberikan sebuah peraturan untuk setiap bilangan bulat positif n untuk menemukan f(n) dari nilai f(j) dari 1 ≤ j ≤ n – 1. (Latihan 32 pada akhir subbab ini dapat dibuktikan bahwa suatu fungsi dirumuskan dengan baik.)Bilangan Fibonacci. Kita ilustrasikan bagaimana sebuah definisi induksi bekerja dengan definisi barisan finobacci, menurut Fibonacci, seorang matematikawan Italia pada abad ke-14 yang menggunakan barisan ini untuk memecahkan sebuah permasalahan tentang populasi kelinci (Perhtaikan Latihan 46 pada akhir subbab ini.)Contoh 1.14. Barisan fibonacci f1, f2, ... , fn didefinisikan secara berulang dengan f1 = 1, f2 = 1, dan fn = fn-1 + fn – 2 untuk n ≥ 3. Dari definisi ini kita perhatikan bahwa

f3 = f2 + f1 = 1 + 1 = 2f4 = f3 + f2 = 2 + 1 = 3f5 = f4 + f3 = 3 + 2 = 5f6 = f5 + f4 = 5 + 3 = 8

dan seterusnya. (Catatan: Sebuah barisan adalah sebuah fungsi dari himpunan bilangan bulat positif hingga himpunan bilangan real. Akibatnya hal ini memberikan pengertian untuk mendefinisikan barisan secara berulang.)

Kita juga mendefinisikan nilai barisan Fibonacci pada n = 0 dengan ketentuan f0 = 0. Dengan definisi ini, kita tentukan bahwa f2 = f1 + f0. Kita dapat definisikan fn dimana n adalah suatu bilangan negatif sehingga sama dengan definisi berulang memenuhi. (Perhatikan Latihan 5.5.)

Bilangan Fibonacci memenuhi banyak identitas. Kita buktikan salah satunya pada contoh berikut dan berikan contoh lain sebagai latihan pada akhir subbab .

Contoh 1.15. Kita dapa menduga sebuah rumus dari ∑j=1

n

f j dengan menguji

penjulahan ini untuk nilai kecil dari n. Kita mempunyaif1 = 1,

f1 + f2 = 1 + 1 = 2,f1 + f2 + f3 = 1 + 1 + 2 = 4,

f1 + f2 + f3 + f4 = 1 + 1 + 2 + 3 = 7,f1 + f2 + f3 + f4 + f5 = 1 + 1 + 2 + 3 + 5 = 12.

Merupakan penjumlahan dari semua satu kurangnya dari bilangan Fibonacci yang bentuk keduanya keluar dari barisan. Sehingga dapat diperkirakan bahwa

∑j=1

n

f j=f n+2−1 .

Sekarang kita coba membuktikan dugaan ini dengan induksi matematika. Tahap dasar

adalah sebagai berikut karena ∑j=1

1

f j=1 dan ini juga sama dengan

f 1+2−1=f 3−1=2−1=1. Pada hipotesa induksi ∑j=1

n

f j=f n+2−1 . Kita tunjukkan bahwa

pada dugaan ini berlaku ∑j=1

n+1

f j=f n+3−1 . Untuk membuktikannya, dengan

menggunakan hipotesa induksi kita peroleh bahwa

∑j=1

n+1

f j=(∑j=1

n

f j)+ f n+1

¿ ( f n+2−1 )+f n+1

¿ ( f n+1+ f n+2 )−1¿ f n+3−1.

Ketidaksamaan pada bilangan Fibonacci akan berguna pada bab 2.Contoh 1.16. Kita dapat menggunakan prinsip kedua dari induksi matematika untuk membuktikan bahwa f n>α n−2 untuk n ≥ 3 dimana α=(1+√5)/2. Tahap dasar konsisten terhadap pembuktian pada ketidaksamaan ini untuk n = 3 dan n = 4. Kita memiliki

α <2=f 3, sehingga dalil ini benar untuk n = 3. Karena α 2=1+√52

<3=f 4, maka dalil

benar untuk n = 4.

Hipotesa induksi konsisten pada perumpamaan bahwa α k−2<f kuntuk semua bilangan bulat k dengan k ≤ n. Karena α=(1+√5)/2 merupakan solusi dari x2−x−1=0, kita memiliki α 2=α +1. Sehingga

α n−1=α 2 . α n−3=(α +1 ) . αn−3=αn−2+α n−3.Menggunakan hipotesa induksi, kita memiliki ketidaksamaan

α n−2< f n , α n−3< f n−1 .Dengan menambahkan dua ketidaksamaan, kita peroleh bahwa

α n−1< f n ,+ f n−1= f n−1 .Ini berarti pembuktian selesai.

Kita memiliki beberapa hal penting pada hasil pembuktian bilangan Fibonacci. Hal ini merupakan sebuah literatur luas tentang bilangan – bilangan Fibonacci dan bilangan ini banyak diaplikasikan dalam botani, ilmu komputer, geografi, fisika, dan bidang lainnya.