Matematiksel Tümevarım

Matematiksel tümevarım, matematikte sık kullanılan bir ispat yöntemidir; en çok pozitif tam sayılarla ya da başka bir dizi ile çalışırken kullanılır.

İlke

Temel ilke şudur: verilen önermeyi bir ilk eleman için ispatlarız; pozitif tam sayılarda bu çoğunlukla n = 1 olur. Bunu doğrudan yerine yazarak ispatlarız. Sonraki adımda, yani tümevarım adımında, “önerme n = a için doğruysa n = a + 1 için de doğrudur” koşullu önermesini ispatlarız.

Bu iki adımdan, ifadenin tüm n değerleri için (o an üzerinde çalıştığımız kümeden) doğru olduğu sonucunu çıkarabiliriz. Bu neden böyledir? Başlangıçta ifadenin n = 1 için doğru olduğunu ispatladık. Aynı zamanda ifade n = a için doğruysa n = a + 1 için de doğru olduğunu biliyoruz. O hâlde a = 1 seçelim. İfadenin a = 1 için doğru olduğunu biliyoruz, ayrıca a + 1 = 2 için de doğru olduğunu biliyoruz. Bu noktada ifadenin a = 2 için doğru olduğunu biliyoruz. Ama a + 1 için de doğru olduğundan 2 + 1 = 3 için de doğru olmalıdır. Ve böyle devam eder.

İlk Örnek

İlk örnek çok basit olacak. Herhangi bir çift sayıya 2 eklersek yine çift sayı elde ettiğimizi ispatlayalım. Pozitif tam sayılarla çalıştığımız için genel bir çift sayıyı 2n biçiminde yazarız; burada n bir pozitif tam sayıdır. n yerine hangi pozitif tam sayıyı yazarsak yazalım sonuçta çift bir sayı elde ederiz, bu ilk bakışta görülür. Bölünebilme dikey çizgi ile şöyle yazılır:

$$2\mid 2n$$

Bu yazılış, 2 sayısının 2n ifadesini kalansız böldüğünü gösterir. Bölünebilmeyi yazmayı bildiğimize göre matematiksel tümevarımla ispatlamamız gereken şeyi de yazabiliriz.

$$2\mid 2n+2;n\in {\mathbb{Z}}^{+}$$

İlk örnekte ispatlamamız gereken budur, yani 2 sayısının 2n + 2 ifadesini böldüğü — bu, “herhangi bir çift sayıya 2 eklersek yine çift sayı elde ederiz” biçimindeki sözel ifadeye tam olarak karşılık gelir.

Tümevarımın başlangıç adımında bunu ilk eleman, yani 1 için ispatlarız. İfadede n = 1 yazarız:

$$\begin{array}{rcl}2& \mid & 2\cdot 1+2\\ 2& \mid & 4\end{array}$$

2, 4’ü kalansız böler, yani önerme ilk eleman için doğrudur. Sonra sıra tümevarım adımına gelir; burada önerme a. eleman için doğruysa (a + 1). eleman için de doğru olduğunu ispatlamalıyız. Başlangıçta hipotezimizin doğru olduğunu, yani önermenin n = a için sağlandığını varsayarız:

$$2\mid 2a+2$$

Bu ifadenin doğru olduğunu varsayıyoruz — ispatı kurarken bunu kullanacağız. Şimdi şunu ispatlamak istiyoruz:

$$2\mid 2(a+1)+2.$$

Ne yaptık? a yerine (a + 1) yazdık. Parantezler önemlidir, şu ifade yanlış olurdu: 2a + 1 + 2. 1’i bütün ifadeye eklemiyoruz, gerçekten a yerine ondan 1 fazla olan ifadeyi, yani (a + 1) yazıyoruz. İfadeyi parantezi açarak düzenleriz.

$$\begin{array}{rcl}2& \mid & 2(a+1)+2\\ 2& \mid & 2a+2+2\end{array}$$

Şimdi kısaca bölünebilme konusuna değinelim. Diyelim ki p ve q gibi iki sayı var ve ikisi de bir sayıya, örneğin r sayısına bölünüyor. O zaman toplamları da r sayısına bölünür. Yani şu geçerlidir:

$$(r\mid p\wedge r\mid q)\Rightarrow r\mid (p+q)$$

Buraya örneğin p = 8, q = 20 ve r = 4 sayılarını yazabiliriz. 4’ün hem 8’i hem de 20’yi böldüğünü görüyoruz. Aynı şekilde toplamları olan 8 + 20 = 28 sayısını da böler.

Bunu örneğimizde nasıl kullanırız? Sağ tarafı p ve q sayılarına şöyle ayırırız:

$$p=2a+2;q=2$$

q sayısı, yani 2, 2’ye bölünür, bu açıktır. p ifadesi de 2’ye bölünür, çünkü bunu bize hipotez söylüyor. p ifadesi, doğru olduğunu varsaydığımız hipotezimizle tam olarak örtüşür. p 2’ye bölünüyorsa ve aynı zamanda q da 2’ye bölünüyorsa, toplamları da 2’ye bölünür.

Hipotez hakkında bir kez daha konuşalım. Başta şu önermenin doğru olduğunu varsaydığımızı söylemiştik:

$$2\mid 2a+2.$$

Bu yüzden ispatı kurarken 2a + 2 ifadesiyle karşılaştığımızda, onun 2’ye bölündüğünü söyleyebildik. Çünkü bu bizim hipotezimizdir. Matematiksel tümevarımın en zor adımı genellikle budur — tümevarım hipotezinin ne zaman ve neden kullanılabileceğini anlamak.

Tümevarım burada biter, ispat başarıyla tamamlandı, önerme doğrudur.

İstersen bunu başka türlü ayırabilir ve hipotezi hiç kullanmayabilirsin: p = 2n ve q = 2 + 2. q = 4 sayısı 2’ye bölünür, bu açıktır; p = 2n de öyledir, çünkü 2’ye böldükten sonra elimizde n sayısı kalır, o da bir pozitif tam sayıdır, yani tam sayıdır. Böylece yine ikisi de 2’ye bölünen iki ifade elde ettik, dolayısıyla toplamları da 2’ye bölünür.

Ama iki durumda da şunları ispatlamış olduk:

1. verilen ifade n = 1 için doğrudur,
2. ifade n için doğruysa n + 1 için de doğrudur.

Buradan şunu çıkarabiliriz:

• İfadenin n = 1 için doğru olduğunu biliyoruz.
• n için doğruysa n + 1 için de doğru olmalıdır, yani 1 + 1 için de; demek ki ifade n = 2 için de doğrudur.
• n için doğruysa n + 1 için de doğru olmalıdır, yani 2 + 1 için de; demek ki ifade n = 3 için de doğrudur.
• n için doğruysa n + 1 için de doğru olmalıdır, yani 3 + 1 için de; demek ki ifade n = 4 için de doğrudur.
• n için doğruysa n + 1 için de doğru olmalıdır, yani 4 + 1 için de; demek ki ifade n = 5 için de doğrudur.
• …

İkinci Örnek

Şimdi matematiksel tümevarımla basit bir önermeyi ispatlayalım:

$$2^n\ge 2n;n\in {\mathbb{Z}}^{+}.$$

Önce başlangıç adımı: önermenin n = 1 için, yani n sayısını seçtiğimiz pozitif tam sayıların ilk elemanı için doğru olup olmadığına bakarız.

$$\begin{array}{rcl}{2}^1& \ge & 2\cdot 1\\ 2& \ge & 2\end{array}$$

Bu açıkça doğrudur. Şimdi tümevarım adımına geçelim; burada n = a için doğruysa n = a + 1 için de doğru olup olmadığını bulmalıyız. Yani hipotezimiz şudur:

$$2^a\ge 2a$$

ve şunu ispatlamak istiyoruz:

$$2^{a+1}\ge 2(a+1)$$

Sol tarafı önce üslü ifadelerle işlem kurallarını kullanarak açalım, sağ tarafı da basitçe parantezi açarak düzenleyelim.

$$2\cdot 2^a\ge 2a+2$$

Sol tarafta çarpma yerine toplama kullanırız, sağ tarafı değiştirmeden bırakırız.

$$2^a+2^a\ge 2a+2$$

Şimdi hipotezden yararlanalım. Hipotez, doğru olduğunu varsaydığımız bir önermedir. Eşitsizliğin iki yanında da toplanan ikişer ifade var. Aynı zamanda şunu da biliyoruz:

$$\begin{array}{rcl}{2}^a& \ge & 2a\\ 2^a& \ge & 2.\end{array}$$

Birinci satırı bize hipotez söylüyor, ikinci önerme ise açıktır (2^a ifadesinin en küçük değeri a = 1 için çıkar ve bu tam olarak 2’ye eşittir). Yani sol taraftaki iki ifadenin her biri, sağ taraftaki iki ifadenin her birinden büyük ya da ona eşittir. Böylece ifade a için doğruysa (a + 1) için de doğru olduğunu tümevarımla ispatlamış olduk ve ifade 1 için de doğru olduğundan verilen ifade doğrudur.

Üçüncü Örnek

Şu önermeyi ispatlamaya çalışalım:

$$3\mid n\Rightarrow 3\mid n^2;n\in {\mathbb{Z}}^{+}$$

Sözle: n sayısı 3’e bölünüyorsa n² ifadesi de 3’e bölünür. n sayısı 3’e bölünmüyorsa ifade (koşullu önermenin tanımı gereği) açıkça doğrudur, bu yüzden n sayısının 3’e bölündüğü durumlarla ilgileneceğiz. Bu bize 3, 6, 9, 12, 15… pozitif tam sayılarından oluşan a_i dizisini verir. Bundan sonra bu a_i dizisinin içinde çalışacağız.

Tümevarımla ispata başlangıç adımıyla başlarız, yani önermenin ilk eleman için doğru olup olmadığına bakarız. Hatırlatayım, a_i dizisinde çalışıyoruz, bu yüzden bu dizinin ilk elemanını, yani a₁ elemanını alırız; bu da 3’tür. 3 için önerme doğrudur:

$$3\mid 3\Rightarrow 3\mid 3^2$$

Şimdi tümevarım adımına geçelim. a_i dizisi 3n biçiminde yazılabilir, burada n bir pozitif tam sayıdır. Yani ikinci eleman bir öncekinden 3 fazladır ve böyle devam eder. Şimdi önermenin n için doğru olduğunu varsayalım ve onun (n + 3) için de doğru olduğunu göstermeliyiz; bu, içinde çalıştığımız dizinin bir sonraki elemanını üreten kuraldır. Önce hipotezi yazalım:

$$3\mid n\Rightarrow 3\mid n^2$$

ardından ispatlamak istediğimiz şeyi

$$3\mid (n+3)\Rightarrow 3\mid (n+3{)}^2.$$

Diğer taraftaki parantezi özdeşlik ile açalım:

$$3\mid (n+3)\Rightarrow 3\mid n^2+6n+9.$$

Artık neredeyse hedefteyiz. Sol tarafta kesinlikle 3’e bölünen bir ifade var, çünkü hipoteze göre n sayısı 3’e bölünür (a_i dizisindeki sayılarla çalışıyoruz) ve 3 de 3’e bölünür. Sağ tarafta ise önce n² var, bu da hipoteze göre 3’e bölünür. Çünkü n sayısının 3’e bölündüğünü biliyoruz ve hipotez, n sayısı 3’e bölünüyorsa n² ifadesinin de 3’e bölündüğünü söylüyor:

$$3\mid n\Rightarrow 3\mid n^2$$

Sonra 6n ifadesi gelir, bu açıkça 3’e bölünür. Bunu kesir sadeleştirme gibi düşünebilirsin:

$$\frac{6n}{3}=2n$$

n değişkeni bir pozitif tam sayıdır, bu yüzden 2n çarpımı da bir pozitif tam sayı olur, yani 3’e böldükten sonra bir pozitif tam sayı elde ettik ve 6n ifadesi 3’e bölünmelidir. Sondaki 9 da yine 3’e bölünür. İfade ilk eleman için de tümevarım adımı için de doğrudur, dolayısıyla doğrudur.

Bir İfadedeki Parantez Sayısı

Son örnek biraz alışılmadık olacak. Basit bir ifadedeki parantez sayısının her zaman çift olduğunu ispatlamaya çalışacağız; böylece matematiksel tümevarımın pozitif tam sayılardan tamamen farklı bağlamlarda da kullanılabildiğini görürsün. Başlangıçta basit ifadenin ne olduğunu tanımlamalıyız. Basit ifade şudur:

• pozitif tam sayı,
• p basit ifadeyse (p²) de basit ifadedir,
• p ve q basit ifadeyse (p + q) da basit ifadedir.

Örneğin şunlar basit ifadedir: 12, 54, (5 + 6), (12 + 7), (6²), ((5 + 6)²). Buna karşılık şunlar basit ifade değildir:

• 1 + 2 → dış parantezler eksik,
• (1 + 2 → sağ parantez eksik,
• 13² → dış parantezler eksik,
• (1 + 2 + 3) → parantezler eksik, doğru yazılış (1 + (2 + 3)) olmalıdır

Basit bir ifade örneğin şöyle oluşabilir. Başta basit bir ifade seçelim: (a + b). Şimdi a yerine a = (c + d) basit ifadesini yazalım, böylece ((c + d) + b) elde ederiz ve b yerine 3 yazalım: ((c + d) + 3). c yerine 10 yazalım: ((10 + d) + 3) ve son olarak d yerine (5²) yazalım: ((10 + (5²)) + 3). Parantezlere uymak önemlidir, yoksa bu çalışmaz.

Şimdi basit bir ifadenin çift sayıda parantez içerdiğini ispatlayalım (çift sayılara sıfır da girer).

Tümevarımın ilk adımında bir ilk eleman seçeriz. Bu durumda ilk eleman en basit ifade, yani herhangi bir pozitif tam sayı olacak. Bu yüzden şunu yazarız:

$$j=n;n\in {\mathbb{Z}}^{+}.$$

j ifadesi için parantez sayısı sıfırdır, yani ilk eleman uygundur. Tümevarım adımında p ve q gibi iki basit ifademiz olduğunu ve ikisinin de çift sayıda parantezi bulunduğunu varsayacağız. Sonra (p + q) ve (p²) basit ifadelerinin de çift sayıda parantezi olduğunu ispatlamalıyız.

Önce toplama. Bir de q ifadesinin parantez sayısını veren z(q) fonksiyonunu tanımlayalım. O zaman (p + q) ifadesinde z(p) + z(q) + 2 parantez vardır. Yani p ve q ifadelerinin parantez sayıları toplamından iki parantez fazladır. Hipoteze göre z(p) de z(q) da çifttir, yani üç çift sayıyı toplarsak yine çift sayı elde ederiz. Bu durumda önerme doğrudur.

Şimdi üs alma. Yine p basit ifadesinin çift sayıda parantez içerdiği varsayımı geçerlidir. (p²) ifadesi bu durumda z(p) + 2 parantez içerir, yani yine p ifadesinden iki parantez fazla. Bu durumda da çift sayıları topluyoruz, dolayısıyla sonuç çifttir.

Önerme ilk eleman için doğrudur ve tümevarım adımında da doğrudur, bu yüzden önerme doğrudur.