Lise öğrencisi olduğum yıllarda, tümevarım yöntemi kullanılan karşılaştığım ilk ispat sanırım $1 + 2 + 3 + \cdots + n = \dfrac{n(n+1)}{2}$ eşitliğinin ispatıdır. İspatlanacak ifadenin illa bir eşitlik olması gerekmez, eşitsizlik de olabilir. İzlenilmesi gereken ve iyi bildiğimiz algoritma şu şekildedir:
$\bullet$ $P(n)$ önermesini $n=1$ için ispatla.
$\bullet$ $P(n)$ önermesinin bir $n=k$ doğal sayısı için doğru olduğunu kabul et.
$\bullet$ $n=k+1$ için $P(k+1)$ önermesinin de doğru olduğunu ispatla.
O zaman her $n$ pozitif tam sayısı için $P(n)$ önermesi doğrudur, sonucuna varıyoruz.
Tümevarım bundan biraz daha fazlasıdır. İlk basamakta biraz değişikliğe gidip
$n=n_{0} $ gibi bir doğal sayı için $P(n)$ önermesinin doğru olduğunu ispatla
maddesini koyalım. Diğer kısımları aynı kalsın. O zaman da $P(n)$ önermesinin her $n\geq n_0$ doğal sayısı için doğru olduğunu göstermiş oluyoruz.
Örnek: Her $n \geq 3$ için $3^n >2^n + 2n^2$ olduğunu ispatlayınız.
Çözüme Giriş: Burada ilk basamak olarak $n=3$ için önermenin doğru olduğunu göstemeliyiz. Zaten $n=1$, $n=2$ için önerme yanlıştır. $n=3$ için $3^3 = 27$, $2^3 + 2\cdot 3^2 = 26$ olup $27>26$ dır, önerme doğrudur. Bundan sonraki adımlar, tümevarım basamaklarına devam edilebilir diye düşünüyorum ama biraz uğraştırıcı olacak gibi görünüyor. (Başka bir yerde soru olarak sorayım bunu.)
Bir de şunu kullanabiliyoruz:
$\bullet$ $P(n)$ önermesini $n=1$ için ispatla.
$\bullet$ $P(n)$ önermesinin $1 \leq n\leq k$ doğal sayıları için doğru olduğunu kabul et. ($k$ sabit bir pozitif tam sayı)
$\bullet$ $n=k+1$ için $P(k+1)$ önermesinin de doğru olduğunu ispatla.
O zaman, her $n$ pozitif tam sayısı için $P(n)$ önermesi doğrudur, sonucuna varıyoruz.
Buraya kadar olan kısım Zayıf Tümevarım Prensibi olarak isimlendiriliyor. Doğru hatırlıyorsam, Kuvvetli Tümevarım Prensibi şu şekildedir:
$\bullet$ $P(n)$ önermesini $n=1,2,\dots, m$ için ispatla. $m$ sabit bir pozitif tam sayı.
$\bullet$ $P(n)$ önermesinin bir $n=k, k+1, \dots, k+m-1$ doğal sayıları için doğru olduğunu kabul et.
$\bullet$ $n=k+m$ için $P(k+m)$ önermesinin de doğru olduğunu ispatla.
Bu durumda da, her $n$ pozitif tam sayısı için $P(n)$ önermesi doğrudur, sonucuna varıyoruz.
Ne zaman tümevarım kullanabiliriz sorusunun yanıtı: genel olarak bu adımları uygulayabileceğimiz herhangi bir problem türünde tümevarım kullanabiliriz, olur. Doğal sayıların sonsuz elemanlı bir alt kümesindeki bir önerme için tümevarım uygulamayı akla getirebiliriz. Cevap veriyor gibi görünüp, aslında çok fazla bir şey söylemeyen bir şey yazdığımın farkındayım. Çünkü, 'matematikte bir yöntemi şuralarda kullanabiliriz' demek insan zihnini biraz kısıtlayıcı bir söz gibi geliyor. Daha önce başkasının aklına gelmemiş bir şekilde de bu yöntemi kullanabilirsiniz.
Bir hikaye paylaşabilirim: Sylvester'in doğru problemi (Sylvester's Line Problem) ile ilgili biliyorum. Problem yaklaşık 50 yıl sonra, Ekstrem Değer Prensibi kullanılarak çözülüyor. Bu prensip basitçe, gerçel sayıların sonlu elemanlı (boş olmayan) bir alt kümesinde bir en büyük eleman vardır, bir en küçük eleman vardır, der. Bu basit prensibi birisi (Grünwald) uygulayıp Sylvester'in doğru problemini çözmeyi başarmıştır.
Tümevarım için de, hiç akla gelmemiş bir problem üzerinde bu yöntemin uygulaması keşfedilebilir.