Matematiksel Tümevarım İlkesi

Rings 5 Minutes

Selam. Hanoi Kulesi yazısından sonra ortaya çıkan ihtiyaçtan dolayı, matematiksel tümevarım ilkesinden kısaca bahsetmek ve Hanoi kulesi probleminin çözümünü tümevarım ile de doğrulamak amacıyla bu yazıyı yazıyorum. Bir diğer motivasyon da internetteki Türkçe matematiksel içerik eksikliğini gidermeye biraz katkıda bulunmak. Doğal sayıların sıralama özelliklerinden bahsettikten sonra, benim en sevdiğim kanıtlardan biri olan tümevarım ilkesinin de kanıtını vermiş olacağız.

Öncelikle tümevarım nedir, nasıl çalışır bundan bahsedelim. Her n doğal sayısı için P_n önermesi verilmiş olsun. Her n doğal sayısı için verilmiş

P_{n}: \quad 1’den n‘e kadar olan sayıların toplamı \frac{n(n+1)}{2}‘dir

gibi. Tümevarım ilkesi bu tür önermelerin kanıtlanmasında işimize yarıyor. Tümevarım ilkesi net bir şekilde aşağıdaki gibi verilebilir:

Teorem (Tümevarım İlkesi). m sabit bir tamsayı olmak üzere, her n \geq m tamsayısı için P(n) önermeleri verilmiş olsun. Eğer

  1. P(m) doğru,
  2. P(n) doğru iken P(n+1) de doğru,

ise P(n) bütün n \geq m tamsayılari için doğrudur.

Bu teoremin kanıtını birazdan vereceğiz. Ancak önce tümevarımı kullanarak yukarıda örnek olarak verdiğim ifadeyi kanıtlayalım:

Öncelikle P(1)’in doğru olduğunu söylememiz lazım. Hatırlarsak, P(1)  “1’den 1’e kadar olan sayıların toplamı \frac{1 \times 2}{2} olur” demekti. Bu işlemin sonucu da 1’i verdiği için P(1) doğrudur diyebiliriz. İkinci adımda da herhangi bir n doğal sayısı için P(n)’in doğru olmasının, P(n+1)’in de doğru olmasını gerektirdiğini göstereceğiz. Yani

\sum_{i=1}^{n} i = \frac{n(n+1)}{2}

olduğunu kabul edip,

\sum_{i=1}^{n+1}i=\frac{(n+1)(n+2)}{2}

olduğunu göstereceğiz.

Öncelikle

\sum_{i=1}^{n+1} i = \sum_{i=1}^{n}i + n+1

yazar ve \sum_{i=1}^{n}i yerine \frac{n(n+1)}{2} yazarsak,

\sum_{i=1}^{n+1}i = \frac{n(n+1)}{2} + (n+1)

elde ederiz. Burada da eşitliğin sağ tarafında payda eşitleyip, (n+1) parantezine alırsak

\sum_{i=1}^{n+1}i = \frac{(n+1)(n+2)}{2}

elde ederiz, ve yukarıdaki tümevarım ilkesine dayanarak, \sum_{i=1}^{n}i = \frac{n(n+1)}{2} ifadesinin her n

doğal sayısı için doğru olduğu sonucuna varabiliriz.

Umarım tümevarımın nasıl kullanıldığı anlaşılmıştır. Şimdi de tümevarım ilkesinin kanıtına geçiyoruz. Öncelikle doğal sayıların sıralama özellikleri hakkında çok kısa bir kaç şey söylemek gerekli.

Doğal sayılarda sıralama

Doğal sayıların aralarında (büyüklük-küçüklük ilişkisi ile) nasıl sıralandıklarını sezgisel olarak biliyoruz. Bunun matematiksel ifadesi de şu şekilde. Herhangi iki m ve n doğal sayısı için, m = n + l olacak şekilde bir l doğal sayısı varsa, “m sayısı n’den büyük veya n’ye eşittir” diyoruz ve bu durumu m \geq n ile gösteriyoruz.

Bu sıralamaya göre doğal sayılar önemli bir özelliğe sahip: doğal sayılar kümesinin boş olmayan herhangi bir alt kümesi bir en küçük elemana sahiptir. Yani doğal sayıların boştan farklı bir alt kümesi S için, bu kümede öyle bir m elemanı vardır ki, her n \in S için m \leq n doğru olur. Doğal sayıların bu özelliğine “iyi sıralama ilkesi” diyoruz (well-ordering principle). Sezgisel olarak “e ne var bunda, çok basit” deseniz de, lakin ki durum öyle değildir. Ancak bu konuda daha fazla detaya girmek istemiyorum.

Şimdi, iyi sıralama ilkesine dayanarak, sıfırdan küçük olması da muhtemel herhangi bir m tam sayısı için, m’den büyük veya eşit tamsayılardan oluşan boş olmayan her tam sayı kümesinin de bir en küçük elemana sahip olduğunu çıkarabiliriz. Bunu doğrulamayı size bırakıyorum.

Şimdi artık tümevarım ilkesini kanıtlamaya hazırız, ihtiyacımız olan tek şey yukarıda değindiğimiz iyi sıralama ilkesiydi. Şimdi gelelim kanıta.

Tümevarım ilkesinin kanıtı

Bir an için teoremin doğru olmadığını varsayalım. Bu durumda, S = \{n \geq m: P(n)\ dogru\ degil\} kumesi boştan farklidir. Yukarıda bahsettiğimiz iyi siralama ilkesine gore, S kumesinin bir en kuçuk elemana sahip olması gerekir. Buna s diyelim. Yani, P(s) doğru değildir. Teoremin 1 numarali varsayimina gore P(m) doğru olmalı ve bu da s > m olmasını gerektirir. Buradan da P(s-1) önermesinin var olduğunu soyleyebiliriz. Ancak s-1 sayısı s’den kucuk olduğu icin P(s-1) doğru olmak zorunda, çunku s’nin P(s)’in doğru olmadığı en kuçuk sayi olduğunu kabul ettik. Yani s - 1 \notin S. Bu da P(s-1)’in dogru olmasi demek. Ancak teoremin ikinci varsayimina gore P(s) = P((s-1)+1) doğru olmali ve bu da s \in S olmasıyla çelişir. □

Hanoi Probleminin Dogrulanmasi

Hanoi problemi ve cozumunden daha once bahsetmiştik. Hatırlarsanız, n tane diskli bir Hanoi kulesi oyununun çozumu icin en az 2^{n}-1 hamle gerektiğini bulmuştuk. Simdi bunu tümevarımla kanitlayalim. Bu durumda, P(1) önermesinin doğru olduğu sanirim cok acik: bir tane diski tasimak icin bir tane hamle yapmamız gerekli. 2^{1}-1 = 1 olduğu icin de P(1)’in doğru olduğunu soyleyebiliriz. Simdi P(n)’in doğru olduğunu kabul edelim. Elimizde n+1 tane disk olduğunda, aynen problemin çozumundeki gibi asagidaki adimlari takip edeceğiz:

1) ustteki n tane diski bos bir cubuga aktaralim

2) en buyuk diski diger bos cubuga aktaralim

3) diger n tane diski en buyuk diskin uzerine tasiyalim.

Butun bu islemler iki kere n tane diskin tasinmasi ve bir kere de tek bir diskin tasinmasindan ibaret. P(n)’in dogru oldugunu kabul ettigimiz icin, toplamda bize gereken hamle sayisi 2(2^{n}-1) + 1 = 2^{n+1}-1 olur, yani P(n+1) onermesi de dogru demektir. Boylece Hanoi probleminin cozumunu tumevarimla da dogrulamis olduk.

Gauss hakkinda kisa bir dip not:

Oil painting of Carl Friedrich Gauss by G. Bie...

Yaziyi bitirip kontrol ederken, birden herhangi bir tamsayiya kadar olan sayilarin toplami formulune bakarken Gauss aklima geldi. Alman matematikci Carl-Friedrich Gauss (1777-1855) hakkinda gelmis gecmis en buyuk matematikcilerden oldugu konusunda tum matematik camiasi hem fikirdir. Kendisi hakkinda anlatilan hikayelerden birine gore, ilkokul ogrencisi Gauss derste yaramazlik yapar ve ogretmeni tarafindan birden yuze kadar olan sayilari toplamakla cezalandirilir. Gauss bu durur mu, birkac saniyede yapistirmis hemen cevabi. Gauss’un bu soruya hizlica cevap verebilmesinin sebebinin, birden yuze kadar olan sayilari bir bastan bir sondan toplandigi zaman hep ayni sonucu verdigini farketmesi oldugu soylenir: 1 + 100 = 101, 2 + 99 = 101, 3 + 98 = 101 gibi. Sonuc olarak birden yuze kadar olan sayilarin toplaminin elli adet 101 sayisinin toplamina esit oldugunu ve cevabin 50 x 101 = 5050 oldugunu bulur.

Lutfen yorumlarinizi ve elestirilerinizi bildirin.

Até logo!

Bilinmeyen adlı kullanıcının avatarı

Can Hatipoglu tarafından yayınlandı

Matematikçi.

Yayımlanmış

Yorum bırakın