Induksi matematika

Mathematical induction, adalah teknik untuk membuktikan hasil atau membuat pernyataan untuk bilangan asli. Bagian ini mengilustrasikan metode melalui berbagai contoh.

Definisi

Mathematical Induction adalah teknik matematika yang digunakan untuk membuktikan pernyataan, rumus atau teorema benar untuk setiap bilangan asli.

Teknik ini melibatkan dua langkah untuk membuktikan pernyataan, seperti yang dinyatakan di bawah ini -

Step 1(Base step) - Ini membuktikan bahwa pernyataan benar untuk nilai awal.

Step 2(Inductive step)- Ini membuktikan bahwa jika pernyataan tersebut benar untuk n th iterasi (atau nomor n ), maka itu juga berlaku untuk (n + 1) th iterasi (atau nomor n + 1 ).

Bagaimana cara melakukannya

Step 1- Pertimbangkan nilai awal yang pernyataannya benar. Ini akan ditunjukkan bahwa pernyataan itu benar untuk n = nilai awal.

Step 2- Asumsikan pernyataan itu benar untuk setiap nilai n = k . Kemudian buktikan bahwa pernyataan tersebut benar untuk n = k + 1 . Sebenarnya kita memecah n = k + 1 menjadi dua bagian, satu bagian adalah n = k (yang telah dibuktikan) dan mencoba membuktikan bagian lainnya.

Masalah 1

$ 3 ^ n-1 $ adalah kelipatan 2 untuk n = 1, 2, ...

Solution

Step 1 - Untuk $ n = 1, 3 ^ 1-1 = 3-1 = 2 $ yang merupakan kelipatan 2

Step 2 - Mari kita asumsikan $ 3 ^ n-1 $ benar untuk $ n = k $, Oleh karena itu, $ 3 ^ k -1 $ benar (Ini adalah asumsi)

Kita harus membuktikan bahwa $ 3 ^ {k + 1} -1 $ juga merupakan kelipatan 2

$ 3 ^ {k + 1} - 1 = 3 \ kali 3 ^ k - 1 = (2 \ times 3 ^ k) + (3 ^ k - 1) $

Bagian pertama $ (2 \ times 3k) $ pasti kelipatan 2 dan bagian kedua $ (3k -1) $ juga benar seperti asumsi kita sebelumnya.

Karenanya, $ 3 ^ {k + 1} - 1 $ adalah kelipatan 2.

Jadi, terbukti bahwa $ 3 ^ n - 1 $ adalah kelipatan 2.

Masalah 2

$ 1 + 3 + 5 + ... + (2n-1) = n ^ 2 $ untuk $ n = 1, 2, \ dots $

Solution

Step 1 - Untuk $ n = 1, 1 = 1 ^ 2 $, Oleh karena itu, langkah 1 terpenuhi.

Step 2 - Mari kita asumsikan pernyataan itu benar untuk $ n = k $.

Karenanya, $ 1 + 3 + 5 + \ dots + (2k-1) = k ^ 2 $ benar (Ini adalah asumsi)

Kita harus membuktikan bahwa $ 1 + 3 + 5 + ... + (2 (k + 1) -1) = (k + 1) ^ 2 $ juga berlaku

$ 1 + 3 + 5 + \ titik + (2 (k + 1) - 1) $

$ = 1 + 3 + 5 + \ titik + (2k + 2 - 1) $

$ = 1 + 3 + 5 + \ titik + (2k + 1) $

$ = 1 + 3 + 5 + \ titik + (2k - 1) + (2k + 1) $

$ = k ^ 2 + (2k + 1) $

$ = (k + 1) ^ 2 $

Jadi, $ 1 + 3 + 5 + \ dots + (2 (k + 1) - 1) = (k + 1) ^ 2 $ hold yang memenuhi langkah 2.

Oleh karena itu, $ 1 + 3 + 5 + \ dots + (2n - 1) = n ^ 2 $ terbukti.

Masalah 3

Buktikan bahwa $ (ab) ^ n = a ^ nb ^ n $ benar untuk setiap bilangan asli $ n $

Solution

Step 1 - Untuk $ n = 1, (ab) ^ 1 = a ^ 1b ^ 1 = ab $, Oleh karena itu, langkah 1 terpenuhi.

Step 2 - Mari kita asumsikan pernyataan itu benar untuk $ n = k $, Oleh karena itu, $ (ab) ^ k = a ^ kb ^ k $ benar (Ini adalah asumsi).

Kita harus membuktikan bahwa $ (ab) ^ {k + 1} = a ^ {k + 1} b ^ {k + 1} $ juga memegang

Diketahui, $ (ab) ^ k = a ^ kb ^ k $

Atau, $ (ab) ^ k (ab) = (a ^ kb ^ k) (ab) $ [Mengalikan kedua sisi dengan 'ab']

Atau, $ (ab) ^ {k + 1} = (aa ^ k) (bb ^ k) $

Atau, $ (ab) ^ {k + 1} = (a ^ {k + 1} b ^ {k + 1}) $

Oleh karena itu, langkah 2 dibuktikan.

Jadi, $ (ab) ^ n = a ^ nb ^ n $ benar untuk setiap bilangan asli n.

Induksi Kuat

Induksi Kuat adalah bentuk lain dari induksi matematika. Melalui teknik induksi ini, kita dapat membuktikan bahwa fungsi proposisional, $ P (n) $ benar untuk semua bilangan bulat positif, $ n $, menggunakan langkah-langkah berikut -

  • Step 1(Base step) - Ini membuktikan bahwa proposisi awal $ P (1) $ benar.

  • Step 2(Inductive step) - Ini membuktikan bahwa pernyataan bersyarat $ [P (1) \ land P (2) \ land P (3) \ land \ dots \ land P (k)] → P (k + 1) $ benar untuk bilangan bulat positif $ k $.