Induksi matematika

Induksi matematika adalah cara khusus untuk membuktikan kebenaran matematika. Ini dapat digunakan untuk membuktikan bahwa sesuatu itu benar untuk semua bilangan asli (semua bilangan bulat positif). Idenya adalah bahwa

Sesuatu yang benar untuk kasus pertama
Hal yang sama selalu berlaku untuk kasus berikutnya

kemudian

Hal yang sama berlaku untuk setiap kasus

Dalam bahasa matematika yang cermat:

Nyatakan bahwa pembuktian akan dilakukan dengan induksi atas n {\displaystyle n} . ( n {\displaystyle n} adalah variabel induksi).
Tunjukkan bahwa pernyataan tersebut benar bila n {\displaystyle n} adalah 1.
Asumsikan bahwa pernyataan tersebut benar untuk setiap bilangan asli n {\displaystyle n} . (Ini disebut langkah induksi).

Tunjukkan bahwa pernyataan itu benar untuk bilangan berikutnya, n + 1 {\displaystyle n+1} $n+1$ .

Karena benar untuk 1, maka benar untuk 1+1 (=2, dengan langkah induksi), kemudian benar untuk 2+1 (=3), kemudian benar untuk 3+1 (=4), dan seterusnya.

Contoh pembuktian dengan induksi:

Buktikan bahwa untuk semua bilangan asli n:

1 + 2 + 3 + . . . . + ( n - 1 ) + n = 1 2 n ( n + 1 ) {\displaystyle 1+2+3+....+(n-1)+n={\tfrac {1}{2}}n(n+1)} $1+2+3+....+(n-1)+n={\tfrac {1}{2}}n(n+1)$

Bukti:

Pertama, pernyataannya bisa ditulis: untuk semua bilangan asli n

2 ∑ k = 1 n k = n ( n + 1 ) {\displaystyle 2\sum _{k=1}^{n}k=n(n+1)} $2\sum _{k=1}^{n}k=n(n+1)$

Dengan induksi pada n,

Pertama, untuk n=1:

2 ∑ k = 1 1 k = 2 ( 1 ) = 1 ( 1 + 1 ) {\displaystyle 2\sum _{k=1}^{1}k=2(1)=1(1+1)} $2\sum _{k=1}^{1}k=2(1)=1(1+1)$ ,

jadi ini benar.

Selanjutnya, asumsikan bahwa untuk beberapa n=n₀ pernyataan tersebut benar. Artinya,:

2 ∑ k = 1 n 0 k = n 0 ( n 0 + 1 ) {\displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1)} $2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1)$

Kemudian untuk n=n₀ +1:

2 ∑ k = 1 n 0 + 1 k {\displaystyle 2\sum _{k=1}^{{n_{0}}+1}k} $2\sum _{k=1}^{{n_{0}}+1}k$

dapat ditulis ulang

2 ( ∑ k = 1 n 0 k + ( n 0 + 1 ) ) {\displaystyle 2\kiri(\sum _{k=1}^{n_{0}}k+(n_{0}+1)\kanan)} $2\left(\sum _{k=1}^{n_{0}}k+(n_{0}+1)\right)$

Karena 2 ∑ k = 1 n 0 k = n 0 ( n 0 + 1 ), {\displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1),} $2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1),$

2 ∑ k = 1 n 0 + 1 k = n 0 ( n 0 + 1 ) + 2 ( n 0 + 1 ) = ( n 0 + 1 ) ( n 0 + 2 ) {\displaystyle 2\sum _{k=1}^{n_{0}+1}k=n_{0}(n_{0}+1)+2(n_{0}+1)=(n_{0}+1)(n_{0}+2)} $2\sum _{k=1}^{n_{0}+1}k=n_{0}(n_{0}+1)+2(n_{0}+1)=(n_{0}+1)(n_{0}+2)$

Oleh karena itu, buktinya benar.

Bukti serupa

Induksi matematika sering dinyatakan dengan nilai awal 0 (bukan 1). Pada kenyataannya, induksi matematika akan bekerja sama baiknya dengan berbagai nilai awal. Berikut ini adalah contoh ketika nilai awalnya adalah 3. Jumlah sudut-sudut interior dari poligon bersisi n {\displaystyle n} adalah ( n - 2 ) 180 {\displaystyle (n-2)180} $(n-2)180$ derajat.

Nilai awal awal adalah 3, dan sudut-sudut interior sebuah segitiga adalah ( 3 - 2 ) 180 {\displaystyle (3-2)180} $(3-2)180$ derajat. Asumsikan bahwa sudut-sudut interior dari sebuah n {\displaystyle n} -sisi poligon adalah ( n - 2 ) 180 {\displaystyle (n-2)180} $(n-2)180$ derajat. Tambahkan pada sebuah segitiga yang membuat gambar tersebut menjadi n + 1 {\displaystyle n+1} $n+1$ poligon bersisi, dan itu meningkatkan jumlah sudut sebesar 180 derajat ( n - 2 ) 180 + 180 = ( n + 1 - 2 ) 180 {\displaystyle (n-2)180+180=(n+1-2)180} $(n-2)180+180=(n+1-2)180$ derajat. Terbukti.

Ada banyak sekali objek matematika yang pembuktiannya dengan induksi matematika bekerja. Istilah teknisnya adalah himpunan yang tersusun dengan baik.

Definisi induktif

Gagasan yang sama bisa berfungsi untuk mendefinisikan, serta membuktikan.

Definisikan n {\displaystyle n} derajat ke-i sepupu:

Sepupu derajat 1 {\displaystyle 1} $1$ adalah anak dari saudara kandung orang tua
Sepupu berderajat n+1 {\displaystyle n+1} $n+1$ adalah anak dari sepupu berderajat n {\displaystyle n} orang tua.

Ada seperangkat aksioma untuk aritmatika bilangan asli yang didasarkan pada induksi matematika. Ini disebut "Aksioma Peano". Simbol-simbol yang tidak terdefinisi adalah | dan =. Aksioma-aksioma tersebut adalah

| adalah bilangan alami
Jika n {\displaystyle n} adalah bilangan asli, maka n | {\displaystyle n|} $n|$ adalah bilangan asli
Jika n | = m | {\displaystyle n|=m|} $n|=m|$ maka n = m {\displaystyle n=m} $n=m$

Seseorang kemudian dapat mendefinisikan operasi penjumlahan dan perkalian dan seterusnya dengan induksi matematika. Sebagai contoh:

m + | = m | {\displaystyle m+|=m|} $m+|=m|$
m + n | = ( m + n ) | {\displaystyle m+n|=(m+n)|} $m+n|=(m+n)|$

Pertanyaan dan Jawaban

T: Apa itu induksi matematika?

J: Induksi matematika adalah cara khusus untuk membuktikan kebenaran matematika yang dapat digunakan untuk membuktikan sesuatu itu benar untuk semua bilangan asli atau bilangan positif dari titik tertentu dan seterusnya.

T: Bagaimana pembuktian dengan induksi berlangsung?

J: Pembuktian dengan induksi biasanya dilakukan dengan menyatakan bahwa pembuktian akan dilakukan terhadap n, menunjukkan bahwa pernyataan tersebut benar ketika n adalah 1, mengasumsikan bahwa pernyataan tersebut benar untuk setiap bilangan asli n, dan kemudian menunjukkan bahwa pernyataan tersebut benar untuk bilangan berikutnya (n+1).

T: Apa artinya mengasumsikan sesuatu dalam langkah induktif?

J: Mengasumsikan sesuatu dalam langkah induktif berarti menerimanya sebagai benar tanpa memberikan bukti atau pembuktian. Ini berfungsi sebagai titik awal untuk penyelidikan lebih lanjut.

T: Jenis bilangan apa yang digunakan dalam induksi matematika?

J: Induksi matematis biasanya menggunakan bilangan asli atau bilangan positif dari titik tertentu dan seterusnya.

T: Bagaimana Anda menunjukkan bahwa sesuatu itu benar untuk bilangan berikutnya (n+1)?

J: Untuk menunjukkan bahwa sesuatu itu benar untuk bilangan berikutnya (n+1), pertama-tama Anda harus membuktikan bahwa hal itu benar ketika n = 1, dan kemudian menggunakan asumsi Anda dari langkah induktif untuk menunjukkan bahwa hal itu juga benar untuk n+1.