Question

Tümevarım nedir? Tümevarım bize neyi ispatlıyor? Tümevarım neden bir ispat yöntemidir?

Answer 1

Tümevarım bir teoremdir. Şunu söyler:

$P(n)$ doğal sayılarla parametrize edilmiş bir önerme olsun. Eğer $P(0)$ doğruysa ve her $n$ için $P(n)$ doğru iken $P(n+1)$ de doğruysa, her $n \in \mathbb{N}$ için $P(n)$ doğrudur.

Sezgisel olarak bu teoremin kanıtı söyledir: Diyelim ki $P(0)$ doğru ve her $n$ için $P(n)$ doğru iken $P(n+1)$ de doğru. O zaman, $P(0)$ doğru olduğundan $P(1)$ doğru. $P(1)$ doğru olduğundan $P(2)$ doğru. Böyle giderek her $n$ için $P(n)$ doğru olmalı. Tümevarım teoremini sonsuz uzunlukta bir domino taşı dizisi üzerinde görebiliriz. $P(n)$ doğru iken $P(n+1)$'in doğru olması $n$ numaralı domino taşını devirince $n+1$ numaralı taşın da devrildiği manasında okuyabiliriz. Tabi ki, $P(0)$'ın doğru olması $0$ numaralı domino taşını devirdiğimiz manasında geliyorsa, bütün domino taşları devrilecektir çünkü bir taşın devrilmesi bir sonrakisinin devrilmesi gerektiriyor.

Tümevarım teoreminin gerçek bir kanıtı şudur: Diyelim ki bir $n$ için $P(n)$ doğru değil, buradan bir çelişki elde etmek istiyorum. Böyle $n$'lerin en küçüğünü alalım. Tabi ki $n=0$ olamaz çünkü $P(0)$ doğru. O zaman $n=k+1$, yazabilirim ve $k<n$ olduğundan $P(k)$ doğrudur. Fakat teoremin varsayımı gereği $P(k)$ doğru ise $P(k+1)$ de doğru olmalı, çelişki. Demek ki her $n \in \mathbb{N}$ için $P(n)$ doğru.

Answer 2

Genel tumevarim yontemi:

ilk olarak bir seyin dogruluguna inaniyorum diyelim. ilk olarak herhangi bir $a$ icin dogru ise $a+1$ icin dogrulugunu ispatlayalim. Bu su demek: eger $x$ icin dogru ise $x+1$ icin dogru, $x+1$ icin dogru ise $x+2$ icin dogru, $\cdots$, yani tum $x+n$ icin dogru, $n \in \mathbb{N}$ olmak uzere.. Demek ki bir  baslangic noktasi $x$'e ihtiyacim var. 

ikisinin de olmasi onemli. yani $a>a+1$ ise $a+1>(a+1)+1=a+2$ ama bunu saglayan hic bir baslangic degerim yok.

ornekte $+1$ ile tumevardik, fakat $-1/2$ de olabilir $-\pi$ de.. daha farkli teknikler kullanilip gelistirilebilir de. 

Kisacasi cok dogal ve hos bir ispat yontemi..