Tümevarım

Tümevarım Yöntemi Nedir ?

Bilim adamlarının yüzyıllardır kullandığı bir yöntem olan tümevarım en basit tanımla, yeni varsayımlara deneyler ve gözlemlerle ulaşmak demektir. Temsil, tümden gelim ve mantık yürütme olarak üç temel dayanağı olan tümevarım, bir “düşünme yöntemi” olduğu için kuşkusuz yalnızca bilim adamlarının tekelinde olan bir sistem de değildir. Her insan tümevarım yöntemi ile yeni varsayımlarda bulunabileceği gibi, akıl yürüterek bir takım olayların işleyiş mekanizmalarının etkileri ve sonuçları hakkında da bir hükme varılması mümkündür.

P(n) bir açık önerme, a önermeyi doğrulayan en küçük sayma sayısı olmak üzere, P(n) nin doğruluğunu göstermek için;

P(a) nın doğru olduğu gösterilir.

P(n) nin doğru olduğu kabul edilir.

P(n+1) in doğru olduğu gösterilir.

P(n) önermesinin doğruluğunu ispatlamak için kullanılan bu yönteme, tümevarım yöntemi adı verilir.

Örnek ;

 P(n) : 2+4+6...+ 2n=n(n+1) olduğunu tümevarım ispat yöntemi ile gösterelim.

n=1 için, P(1): 2.1=1.(1+1)→ 2=2→ P(1) doğrudur.

n=k için, P(k):2+4+6...+2k=k(k+1) önermesinin doğru olduğunu kabul edelim.

n=(k+1) için, P(k+1): 2+4+6+...+2k+2(k+1)=(k+1)(k+2) olduğunu gösterelim.

2+4+6...+2k=k(k+1) eşitliğinin her iki tarafına 2(k+1) ekleyelim.

2+4+6...+2k+2(k+1)=k.(k+1)+2(k+1)→P(k+1) doğrudur.

P(k+1) doğru olduğundan P(n) önermesi doğru olur.

Tümevarım İle İspat Tekniği : En çok bilinen ve kullanılan ispat tekniklerinden biridir. Bu teknikte, ispatın yapılacağı kümede, eleman sayısının sayılabilir sonsuzlukta olması durumunda, bir p özelliğinin "1" için var olduğu gösterilir. Sonra k için özelliğin var olduğu kabul edilir ve k+1 için özelliğin ispatı yapılır.

k yı en kötü durumda 1 olarak düşündüğümüzde ve 1 için ispatın sağlandığını ilk adımda göstermiş olduğumuzdan, önermenin k için doğru olduğunu kabul etmemiz yanlış bir kabul olmayacaktır. Sonra k+1 için sağlandığını ispatladığımızdan 2 için de sağlandığı gösterilmiş olur. Bu sefer 2 için sağlandığından, k yı 2 gibi düşünürsek k+1 yani 3 için de ispat sağlanacak, 3 için sağlandığından yine aynı mantıkla 4 için de sağlanacak ... ve bu şekilde genel bir ispat yapılmış olacaktır. İlk başlangıç adımının her zaman "1" olması zorunlu değildir, "3 ten büyük tamsayılar için önermenin sağlandığını

gösterin" gibi bir durumda başlangıç adımını 3 gibi bir sayı da seçebiliriz. Sonra yine aynı şekilde k için doğru olduğunu kabul edip, k+1 için doğruluğunu göstererek ispatı genelleriz. Bu tekniği kullanarak ispatı yapılan bir çok önerme bulunmaktadır. Şimdi bunlara bir kaç örnek verelim.

Örnek 1 : 1 + 3 + 5 + ... + 2n-1 biçimindeki sayıların toplamının n=1,2,3,4,5,... tamsayılarının her biri için n2 olduğunu gösteriniz.

İspat 1 : Tümevarım tekniği ile ispatı yapılabilen toplam serileri üzerine iyi bilinen

örneklerden biridir. Tekniğe göre ilk adım olarak "1" için önermenin doğruluğunu

görelim;

n=1 için : n=1 için bakacak olursak serinin toplamı 1 olacaktır. Sonuçta

1 = 12 olduğundan n=1 için önerme doğrudur.

n=k için önerme doğru olsun : Yani 1 + 3 + 5 + ... + 2k-1 = k2 olsun.

n=k+1 için : n=k+1 için önermenin doğru olduğunu göstermek için;

15

1 + 3 + 5 + ... + 2(k+1)-1 = (k+1)2 olduğunu göstermeliyiz. Burada eşitliğin sol

tarafındaki en son terimden bir önceki terim de yazılacak olursa;

1 + 3 + 5 + ... + 2k-1 + 2(k+1)-1 = (k+1)2 olduğunu göstermek istiyoruz. Bir önceki adımdaki kabulümüzden dolayı;

1 + 3 + 5 + ... + 2k-1 = k2 olduğunu biliyoruz. Bunu yerine yazarsak

1 + 3 + 5 + ... + 2k-1 + 2(k+1)-1 = k2 + 2(k+1)-1 olacaktır. Bunun da (k+1)2 ye eşit olduğunu göreceğiz.

k2 + 2(k+1)-1 = k2 + 2k + 1 = (k+1)2 dir.

Böylece önermenin k için doğru olduğunu kabul ederek k+1 için de sağlandığını göstermiş ve genel anlamda ispatlamış oluyoruz.

Örnek 2 : Bazı pozitif n tamsayıları için 22n -1 in 3 ün katı olduğunu gösterin.

İspat 2 : Bu önerme de tümevarım ile kolaylıkla gösterilebilir.

n=1 için : 22n -1 = 22.1 -1 = 22 -1 = 4 - 1 = 3 olur. Yani 3 ün bir katıdır. Öyleyse n=1 için

önerme sağlanır. Şimdi n=k için sağlandığını kabul edip, n=k+1 için inceleyelim;

n=k için önerme doğru olsun : Yani n=k için 22n -1, 3 ün bir katı olmuş olsun. Bunu öyle

bir m tamsayısı için 22k -1 = 3m (*) olarak gösterelim.

n=k+1 için : 22(k+1) -1 ifadesinin 3 ün bir katı olduğunu göstermemiz gerekiyor. Bu ifadeyi

açacak olursak;

22(k+1) -1 = 22k+2 -1 = 22k.22 -1 = 4.22k -1 (**) elde ederiz. Kabulümüzden, yani (*) dan 22k

yı çekersek;

22k -1 = 3m dediğimizden 22k = 3m + 1 elde ederiz. Bunu (**) ifadesinde yerine

yazarsak;

16

22(k+1) -1 = 4.22k -1 = 4.(3m+1) - 1 = 12m + 4 - 1 = 12m + 3

12m + 3 ifadesini de 3 parantezine alırsak 3(4m+1) elde edilir. Burada 4m+1 ifadesi bir

tamsayı olacağına göre, buna p gibi bir tamsayı dersek;

22(k+1) -1 = 12m + 3 = 3p olacaktır. Öyleyse 22(k+1) -1 ifadesi 3 ün bir katıdır. Böylece

n=k+1 için de önermenin doğruluğunu ispatlamış olduk. O zaman tümevarım ile bu

önermenin genel olarak sağlandığını söyleyebiliriz.

Tümevarım tekniğinin kullanımı üzerine başta açıklama yaparken her ispatta ilk adım

olarak n=1 almak zorunda olmadığımıza, n=2 , 3 veya önermeye göre başlangıç için

farklı tamsayılar alabileceğimize deyinmiştik. Şimdi bunun üzerine bir önermenin ispatını

verelim.

Örnek 3 : 2 den büyük ve eşit tamsayılar için n2 > n+1 eşitsizliğinin sağlandığını

gösterin.

İspat 3 : Burada başlangıç adım olarak 2 seçmemiz gerekiyor, çünkü önermemizin 2

den büyük tamsayılar için sağlandığını ispat etmemiz isteniyor.

n=2 için : n2 > n+1 olduğunu görmeliyiz.

n2 = 22 = 4 > 3 = 2+1 = n+1 olduğundan n2 > n+1 eşitsizliği n=2 için sağlanır.

n=k için önerme doğru olsun : n=k için n2 > n+1 özelliği sağlanıyor olsun, yani k2 > k+1

eşitsizliğinin sağlandığını kabul edelim.

n=k+1 için : (k+1)2 > (k+1)+1 sağlandığını göstermeliyiz. Eşitsizliğin sol tarafındaki kare

ifadeyi açalım;

(k+1)2 = k2 + 2k + 1 elde edilir. Kabulümüzden k2 > k+1 olduğundan, k2 yerine ondan

daha küçük olan k+1 yazarsak;

17

(k+1)2 > k2 + 2k + 1 > (k+1) + 2k + 1 = 3k + 2 elde ederiz. Burada k değişkenimiz, 2 den

büyük veya eşit bir tamsayı olduğundan 3k yerine k yazdığımızda ifademiz küçülecektir.

Öyleyse;

(k+1)2 > 3k + 2 > k + 2 = (k+1) + 1 elde ederiz. Böylece n=k+1 için de aradığımız özellik

olan (k+1)2 > (k+1)+1 özelliği sağlanmış olur, ispat tamamlanır.

Görüldüğü gibi tümevarım kullanılarak, bize verilen önermenin genel olarak sağlanıp

sağlanmadığını ispatlayabiliyoruz.