Matematiksel Tümevarım

Mathematical induction, sonuçları ispatlamak veya doğal sayılar için ifadeler oluşturmak için bir tekniktir. Bu bölüm, yöntemi çeşitli örneklerle açıklamaktadır.

Tanım

Mathematical Induction her doğal sayı için bir ifade, formül veya teoremin doğru olduğunu kanıtlamak için kullanılan matematiksel bir tekniktir.

Teknik, aşağıda belirtildiği gibi bir ifadeyi kanıtlamak için iki adım içerir -

Step 1(Base step) - Bir ifadenin başlangıç ​​değeri için doğru olduğunu kanıtlar.

Step 2(Inductive step)- Eğer ifade n'inci yineleme (veya n sayısı ) için doğruysa, o zaman (n + 1) inci yineleme (veya n + 1 sayısı ) için de geçerli olduğunu kanıtlar .

Nasıl yapılır

Step 1- İfadenin doğru olduğu bir başlangıç ​​değeri düşünün. İfadenin n = başlangıç ​​değeri için doğru olduğu gösterilecektir.

Step 2- Herhangi bir n = k değeri için ifadenin doğru olduğunu varsayın . Ardından, ifadenin n = k + 1 için doğru olduğunu kanıtlayın . Aslında n = k + 1'i iki parçaya ayırıyoruz, bir parça n = k (zaten kanıtlanmıştır) ve diğer parçayı ispatlamaya çalışıyoruz.

Problem 1

$ 3 ^ n-1 $, n = 1, 2, ... için 2'nin katıdır

Solution

Step 1 - $ n = 1 için, 3 ^ 1-1 = 3-1 = 2 $ 2'nin katıdır

Step 2 - $ n = k $ için $ 3 ^ n-1 $ 'ın doğru olduğunu varsayalım, Dolayısıyla, $ 3 ^ k -1 $ doğrudur (Bu bir varsayımdır)

$ 3 ^ {k + 1} -1 $ 'ın da 2'nin katı olduğunu kanıtlamalıyız

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

Birinci kısım $ (2 \ times 3k) $ kesinlikle 2'nin katıdır ve ikinci kısım $ (3k -1) $ da önceki varsayımımız gibi doğrudur.

Dolayısıyla, $ 3 ^ {k + 1} - 1 $, 2'nin katıdır.

Yani 3 ^ n - 1 $ 'ın 2'nin katı olduğu kanıtlanmıştır.

Problem 2

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

Solution

Step 1 - $ n = 1, 1 = 1 ^ 2 $ için, 1. adım yerine getirilmiştir.

Step 2 - İfadenin $ n = k $ için doğru olduğunu varsayalım.

Dolayısıyla, $ 1 + 3 + 5 + \ dots + (2k-1) = k ^ 2 $ doğrudur (Bu bir varsayımdır)

$ 1 + 3 + 5 + ... + (2 (k + 1) -1) = (k + 1) ^ 2 $ 'ın da geçerli olduğunu kanıtlamalıyız

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

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

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

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

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

$ = (k + 1) ^ 2 $

Dolayısıyla, 2. adımı karşılayan $ 1 + 3 + 5 + \ dots + (2 (k + 1) - 1) = (k + 1) ^ 2 $ tutma.

Dolayısıyla $ 1 + 3 + 5 + \ dots + (2n - 1) = n ^ 2 $ ispatlanmıştır.

Sorun 3

$ (Ab) ^ n = a ^ nb ^ n $ değerinin her $ n $ doğal sayısı için doğru olduğunu kanıtlayın

Solution

Step 1 - $ n = 1 için, (ab) ^ 1 = a ^ 1b ^ 1 = ab $, Dolayısıyla 1. adım yerine getirilmiştir.

Step 2 - İfadenin $ n = k $ için doğru olduğunu varsayalım. Dolayısıyla, $ (ab) ^ k = a ^ kb ^ k $ doğrudur (Bu bir varsayımdır).

$ (Ab) ^ {k + 1} = a ^ {k + 1} b ^ {k + 1} $ değerinin de

$ (Ab) ^ k = a ^ kb ^ k $ verildiğinde

Veya $ (ab) ^ k (ab) = (a ^ kb ^ k) (ab) $ [Her iki tarafı da 'ab' ile çarparak]

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

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

Bu nedenle, 2. adım kanıtlanmıştır.

Dolayısıyla, $ (ab) ^ n = a ^ nb ^ n $ , her n doğal sayısı için doğrudur.

Güçlü İndüksiyon

Güçlü Tümevarım, matematiksel tümevarımın başka bir şeklidir. Bu tümevarım tekniğiyle, aşağıdaki adımları kullanarak tüm pozitif tamsayılar $ n $ için bir önermesel fonksiyon olan $ P (n) $ 'nın doğru olduğunu kanıtlayabiliriz -

  • Step 1(Base step) - İlk önerme $ P (1) $ doğru olduğunu kanıtlıyor.

  • Step 2(Inductive step) - $ [P (1) \ land P (2) \ land P (3) \ land \ dots \ land P (k)] → P (k + 1) $ koşullu ifadesinin pozitif tamsayılar $ için doğru olduğunu kanıtlıyor k $.