01.06.08 — Matematiksel Tümevarım

Birim kartı

Dünya: 1 — Matematiksel Dil ve Temeller
Bölüm: 1.6 — İspat ve Matematiksel Kesinlik
Seviye: [A] Ana Matematik Gövdesi
Temel soru: Sonsuz sayıda iddiayı tek tek kontrol etmeden nasıl ispatlayabiliriz?
Ana fikir: Bir iddianın başlangıçta doğru olduğunu ve her doğru durumun bir sonrakini zorunlu kıldığını gösterirsek, iddia bütün doğal sayılar boyunca ilerler.
Önceki bağlantılar: Doğrudan ispat, niceleyiciler, koşullu önerme, ispat ile örnek arasındaki fark
İleri bağlantılar: Diziler, bölünebilme, kombinatorik özdeşlikler, özyinelemeli yapılar, algoritmalar, güçlü ve yapısal tümevarım

Bu birimin doğal sayıların yapısına ilişkin tam temeli, ileride 2.01.04 — Ardıl ilkesi, doğal sayıların yapısı ve tümevarım fikri biriminde daha yapısal biçimde kurulacaktır.

Şimdilik doğal sayıların

1,2,3,4,\ldots

şeklinde, her sayıdan bir sonraki sayıya $+1$ ile geçilen kesintisiz bir zincir oluşturduğu fikrini kullanacağız.

1. Başlangıç problemi: sonsuz sayıda iddia

Şu toplamı inceleyelim:

1+2+3+\cdots+n.

İlk birkaç değeri hesaplayalım.

1=1

1+2=3

1+2+3=6

1+2+3+4=10

Bir örüntü fark edebiliriz:

1+2+\cdots+n=\frac{n(n+1)}{2}.

Kontrol edelim.

$n=1$ için:

1=\frac{1\cdot2}{2}=1.

$n=2$ için:

1+2=\frac{2\cdot3}{2}=3.

$n=3$ için:

1+2+3=\frac{3\cdot4}{2}=6.

$n=100$ için bile hesaplayıp doğrulayabiliriz.

Ama iddiamız yalnızca ilk yüz doğal sayı hakkında değildir.

İddiamız:

\boxed{ \text{Her }n\in\mathbb N\text{ için } 1+2+\cdots+n=\frac{n(n+1)}2 }

şeklindedir.

Kaç tane örnek kontrol etmemiz gerekir?

$100$ mü?

$1\,000\,000$ mı?

$10^{100}$ mü?

Hiçbiri yeterli değildir.

Çünkü doğal sayıların sonuncusu yoktur.

Burada daha önce öğrendiğimiz önemli ayrımla yeniden karşılaşıyoruz:

Bir iddianın çok sayıda örnekte doğru çıkması, bütün doğal sayılar için doğru olduğunu ispatlamaz.

Dolayısıyla elimizde yeni bir problem var:

\boxed{ \text{Sonsuz sayıda ayrı iddiayı sonlu bir ispatla nasıl kapsayacağız?} }

İşte matematiksel tümevarım tam olarak bu probleme cevap verir.

2. Eski araç neden yetmedi?

Her doğal sayı için ayrı ayrı ispat yapmaya çalışsaydık:

P(1)'i ispatla
P(2)'yi ispatla
P(3)'ü ispatla
P(4)'ü ispatla
      ⋮

işimiz hiçbir zaman bitmezdi.

Burada $P(n)$ ile " $n$ sayısına karşılık gelen iddia"yı gösteriyoruz.

Örneğin biraz önceki problemde:

P(n): \quad 1+2+\cdots+n=\frac{n(n+1)}2.

$P(1)$ bir önerme,

$P(2)$ başka bir önerme,

$P(3)$ başka bir önermedir.

Aslında ispatlamak istediğimiz:

P(1),P(2),P(3),P(4),\ldots

şeklindeki sonsuz bir önerme ailesidir.

Tek tek ilerlemek yerine bütün bu önermeleri birbirine bağlayabilir miyiz?

Tümevarımın fikri tam burada doğar.

3. Temel sezgi: tek tek taşları değil, geçiş mekanizmasını ispatlamak

Şöyle bir domino dizisi düşünelim.

Tümevarımın domino modeli

P(1)      P(2)      P(3)      P(4)      P(5)       ...
 │          │          │          │          │
 ▼          ▼          ▼          ▼          ▼
[1]  ───▶  [2]  ───▶  [3]  ───▶  [4]  ───▶  [5]  ───▶ ...

İlk dominonun devrilmesi ve her dominonun kendisinden sonraki dominoyu devirmesi bütün domino zincirinin devrilmesini sağlar.

Bütün dominoların devrileceğini göstermek için her bir dominoyu elimizle devirmemiz gerekmez.

İki şeyi bilirsek yeter:

İlk domino devriliyor.
Her domino devrildiğinde bir sonrakini deviriyor.

Birinci koşul zinciri başlatır.

İkinci koşul zincirin devam etmesini sağlar.

Matematiksel tümevarım da aynı yapıyı kullanır.

Tümevarımın öz fikri

Tek tek

P(1),P(2),P(3),\ldots

önermelerini ispatlamak yerine:

zincirin başladığını,
zincirdeki herhangi bir halkadan bir sonraki halkaya geçilebildiğini

ispatlarız.

Böylece sonlu uzunluktaki bir mantıksal argüman, sonsuz sayıdaki durumu kapsar.

4. Matematiksel tümevarım nedir?

Bir $P(n)$ önermesinin $n=n_0,n_0+1,n_0+2,\ldots$ doğal sayılarının tamamı için doğru olduğunu göstermek istediğimizi düşünelim.

Matematiksel Tümevarım İlkesi

Aşağıdaki iki koşul sağlanıyorsa:

1. Başlangıç adımı

P(n_0)

doğrudur.

2. Tümevarım adımı

Her $k\ge n_0$ için

P(k)\Rightarrow P(k+1)

doğrudur.

O hâlde:

P(n)

önermesi bütün

n\ge n_0

doğal sayıları için doğrudur.

Sembolik olarak:

P(n_0)

\forall k\ge n_0\; \bigl(P(k)\Rightarrow P(k+1)\bigr)

gösterilirse,

\forall n\ge n_0\;P(n)

sonucuna ulaşırız.

Buradaki niceleyicilere dikkat edin.

Tümevarım adımında yalnızca belirli bir $k$ için değil:

\boxed{\text{her }k\ge n_0}

için geçişi göstermemiz gerekir.

5. İki adımın farklı görevleri

Tümevarımın iki koşulundan biri diğerinin yerine geçemez.

Başlangıç adımı ne yapar?

Zincirin içine girmemizi sağlar.

Örneğin:

P(1)

doğruysa ilk halkayı elde ederiz.

Tümevarım adımı ne yapar?

Bir halkadan diğerine geçişi sağlar:

P(k)\Rightarrow P(k+1).

Bunları birlikte kullanınca:

P(1)

doğru olduğundan

P(2)

doğrudur.

$P(2)$ doğru olduğundan:

P(3)

doğrudur.

Sonra:

P(4),P(5),P(6),\ldots

aynı mekanizmayla gelir.

Başlat + devam ettir

Matematiksel tümevarımın bütün mantığı iki işlevde toplanabilir:

\boxed{ \text{Başlangıç} + \text{Geçiş} }

Başlangıç olmadan zincire giremeyiz.

Geçiş olmadan zincirde ilerleyemeyiz.

6. Çok önemli: Tümevarım varsayımı ne demektir?

Tümevarım ispatlarının ilk görüldüğünde en şaşırtıcı kısmı şudur:

İspatlamaya çalıştığımız şeyi neden bir noktada doğru varsayıyoruz?

Tümevarım adımında şöyle deriz:

Bir $k\ge n_0$ alalım ve $P(k)$ doğru olsun.

Bu ifadeye tümevarım varsayımı veya tümevarım hipotezi denir.

İngilizcesi:

induction hypothesis.

Fakat burada bütün teoremi doğru varsaymıyoruz.

Şunu varsaymıyoruz:

\forall n\;P(n).

Yalnızca şu koşullu önermeyi ispatlamak için çalışıyoruz:

P(k)\Rightarrow P(k+1).

Bir koşullu önermeyi doğrudan ispatlarken ne yapıyorduk?

Öncülü doğru kabul edip sonuca ulaşmaya çalışıyorduk.

Burada da aynısını yapıyoruz:

\underbrace{P(k)}_{\text{öncül}} \Rightarrow \underbrace{P(k+1)}_{\text{sonuç}}.

Dolayısıyla tümevarım adımı aslında daha önce öğrendiğimiz doğrudan ispatın özel bir kullanımıdır.

Döngüsel akıl yürütme değildir

Tümevarım varsayımı:

“Teorem bütün doğal sayılar için doğrudur.”

demek değildir.

Yalnızca:

“Rastgele seçilmiş bir $k$ için doğru olduğunu kabul edersem, $k+1$ için de doğru olduğunu gösterebilir miyim?”

sorusunu inceleriz.

İspatladığımız şey:

P(k)\Rightarrow P(k+1)

koşullu önermesidir.

7. İlk tam ispat: ilk $n$ doğal sayının toplamı

Şimdi başlangıçtaki problemimizi gerçekten ispatlayalım.

İddiamız:

1+2+\cdots+n=\frac{n(n+1)}2.

Tümevarımla toplam formülünün ispatı

Her $n\ge1$ için

P(n): \quad 1+2+\cdots+n=\frac{n(n+1)}2

önermesini tanımlayalım.

1. Başlangıç adımı

$n=1$ için:

1=\frac{1(1+1)}2=1.

Dolayısıyla:

P(1)

doğrudur.

2. Tümevarım varsayımı

Bir $k\ge1$ için $P(k)$ 'nin doğru olduğunu varsayalım.

Yani:

1+2+\cdots+k=\frac{k(k+1)}2.

3. Tümevarım adımı

$P(k+1)$ 'in doğru olduğunu göstermeliyiz.

Yani hedefimiz:

1+2+\cdots+k+(k+1) = \frac{(k+1)(k+2)}2.

Sol taraftan başlayalım:

1+2+\cdots+k+(k+1).

Tümevarım varsayımına göre:

1+2+\cdots+k = \frac{k(k+1)}2.

Bu nedenle:

1+2+\cdots+k+(k+1) = \frac{k(k+1)}2+(k+1).

$(k+1)$ ortak çarpanını alalım:

= (k+1)\left(\frac{k}{2}+1\right).

= (k+1)\left(\frac{k+2}{2}\right).

Dolayısıyla:

= \frac{(k+1)(k+2)}2.

Bu tam olarak $P(k+1)$ 'dir.

Yani:

P(k)\Rightarrow P(k+1).

Başlangıç adımı ve tümevarım adımı birlikte sağlandığından:

\boxed{ 1+2+\cdots+n=\frac{n(n+1)}2 }

eşitliği her $n\ge1$ doğal sayısı için doğrudur.

Burada kritik hareket neydi?

Tümevarım varsayımını:

1+2+\cdots+k=\frac{k(k+1)}2

tam ihtiyacımız olan yerde kullandık.

Çünkü $k+1$ 'inci toplam:

\underbrace{1+2+\cdots+k}_{\text{bildiğimizi varsaydığımız bölüm}} +(k+1)

biçimindeydi.

Yani yeni durum, bir önceki durumun üzerine bir parça eklenerek oluşuyordu.

Tümevarım özellikle böyle yapılarda doğaldır.

8. Tümevarım neden gerçekten çalışıyor?

Domino modeli iyi bir sezgi verir.

Fakat matematiksel olarak daha derin bir soru sorabiliriz:

İlk durum doğru ve her durum bir sonrakini doğuruyorsa neden arada bir yerde başarısızlık olamaz?

Bunu doğal sayıların önemli bir özelliği üzerinden anlayabiliriz.

Pozitif doğal sayılardan oluşan boş olmayan herhangi bir kümenin bir en küçük elemanı vardır.

Bu düşünce ileride doğal sayıların iyi sıralanmasıyla daha açık biçimde ele alınacaktır.

En küçük karşı örnek fikriyle neden çalıştığı

Başlangıç ve tümevarım adımlarının doğru olduğunu düşünelim.

Buna rağmen bazı doğal sayılar için $P(n)$ 'nin yanlış olduğunu varsayalım.

Yanlış olduğu doğal sayılar arasında bir en küçük sayı olsun:

m.

Başlangıç durumu doğru olduğundan:

m>n_0.

Dolayısıyla $m$ 'den hemen önceki sayı:

m-1

vardır ve

m-1\ge n_0.

$m$ , başarısız olan en küçük sayı olduğuna göre:

P(m-1)

doğru olmak zorundadır.

Ama tümevarım adımımız:

P(k)\Rightarrow P(k+1)

diyordu.

$k=m-1$ alırsak:

P(m-1)\Rightarrow P(m).

$P(m-1)$ doğru olduğundan $P(m)$ de doğru olmalıdır.

Bu ise $m$ 'yi yanlış olan en küçük durum seçmemizle çelişir.

Demek ki böyle bir başarısız doğal sayı yoktur.

Bu argüman tümevarımın doğal sayıların yapısıyla ne kadar yakından ilişkili olduğunu gösterir.

9. İkinci örnek: bölünebilme

Tümevarım yalnız toplam formülleri için değildir.

Sayı teorisindeki bölünebilme iddialarında da çok doğal biçimde ortaya çıkar.

Her $n\ge1$ için $7\mid(8^n-1)$

İddiamız:

P(n): \quad 7\mid(8^n-1).

Başka bir deyişle:

8^n-1

sayısının her $n\ge1$ için $7$ 'ye bölündüğünü göstermek istiyoruz.

Başlangıç

$n=1$ için:

8^1-1=7.

Dolayısıyla:

7\mid7.

Yani $P(1)$ doğrudur.

Tümevarım varsayımı

Bir $k\ge1$ için:

7\mid(8^k-1)

olduğunu varsayalım.

Bu, bir $m\in\mathbb Z$ için:

8^k-1=7m

yazabileceğimiz anlamına gelir.

Tümevarım adımı

Şimdi:

8^{k+1}-1

ifadesini inceleyelim.

8^{k+1}-1 = 8\cdot8^k-1.

İfadeyi tümevarım varsayımını kullanabileceğimiz biçime getirelim:

8^{k+1}-1 = 8(8^k-1)+7.

Varsayımımıza göre:

8^k-1=7m.

O hâlde:

8^{k+1}-1 = 8(7m)+7.

= 7(8m+1).

$8m+1$ bir tam sayı olduğundan:

7\mid(8^{k+1}-1).

Böylece:

P(k)\Rightarrow P(k+1)

gösterildi.

Sonuç:

\boxed{ 7\mid(8^n-1) }

her $n\ge1$ için doğrudur.

Bu örnekte tümevarım varsayımını kullanabilmek için ifadeyi özellikle:

8(8^k-1)+7

biçimine dönüştürdük.

Bu, tümevarım ispatlarında sık görülen düşünme biçimidir:

$P(k+1)$ durumunun içinde $P(k)$ 'yi nasıl görünür hâle getirebilirim?

10. Tümevarım ispatı nasıl tasarlanır?

Tümevarımı bir şablonu körü körüne doldurmak yerine şu düşünce akışıyla kullanmak daha yararlıdır.

Adım 1 — İddiayı açıkça tanımla

Önce:

P(n)

tam olarak ne demek, yaz.

Örneğin:

P(n): \quad 1+3+5+\cdots+(2n-1)=n^2.

İddia belirsizse ispat da belirsiz olur.

Adım 2 — Başlangıç değerini belirle

İddia nereden itibaren geçerli?

n=0?

n=1?

n=4?

Tümevarımın mutlaka $1$ 'den başlaması gerekmez.

Adım 3 — Başlangıç durumunu doğrula

P(n_0)

gerçekten doğru mu?

Adım 4 — Rastgele bir $k$ seç

k\ge n_0

olsun.

Buradaki $k$ özel bir sayı değildir.

Herhangi bir doğal sayıyı temsil eder.

Adım 5 — Tümevarım varsayımını açıkça yaz

P(k)

doğru olsun.

Adım 6 — Hedefini açıkça yaz

Gösterilecek şey:

P(k+1).

Adım 7 — $P(k)$ bilgisini kullan

Genellikle asıl matematik burada gerçekleşir.

$P(k+1)$ ifadesini, içinde $P(k)$ 'nin kullanılabileceği biçime dönüştürürüz.

Adım 8 — Mantıksal sonucu belirt

P(k)\Rightarrow P(k+1)

gösterildi.

Başlangıç da doğru olduğundan bütün istenen doğal sayılar için sonuç geçerlidir.

İspat sırasında sorulacak ana soru

Tümevarım adımında kendine şunu sor:

$k+1$ durumunu, bildiğimi varsaydığım $k$ durumuna nasıl bağlayabilirim?

Tümevarımın hesap kısmının büyük bölümü bu bağlantıyı bulmaktır.

11. Tümevarım ne değildir?

Türkçedeki tümevarım sözcüğü başka bir akıl yürütme biçimiyle karışmaya çok müsaittir.

Gündelik veya bilimsel anlamdaki tümevarım kabaca şöyle olabilir:

İlk örnek doğru.
İkinci örnek doğru.
Üçüncü örnek doğru.
Birçok örnek doğru.

→ Herhalde genel kural da doğrudur.

Bu, yeni bir tahmin veya genelleme üretmek için yararlı olabilir.

Fakat matematiksel ispat değildir.

Matematiksel tümevarım ise:

Başlangıç durumu kesin olarak doğru.

ve

Her k için:
P(k) doğruysa P(k+1) kesin olarak doğru.

───────────────────────────────

Bütün doğal sayı zinciri kapsanır.

şeklindedir.

İsim benzerliği yanıltmasın

Matematiksel tümevarım:

“Çok örnek gördüm; demek ki hep doğrudur.”

yöntemi değildir.

Örnekler yalnızca iddiayı keşfetmemize yardımcı olabilir.

İspatı yapan şey:

P(n_0)

P(k)\Rightarrow P(k+1)

koşullarının birlikte kurulmasıdır.

12. Başlangıç adımını atlayabilir miyiz?

Hayır.

Şu önermeyi düşünelim:

P(n): \quad n\ge2.

$n\ge2$ için:

P(n)\Rightarrow P(n+1)

doğrudur.

Çünkü:

n\ge2 \Rightarrow n+1\ge3 \Rightarrow n+1\ge2.

Yani zincirin geçiş mekanizması kusursuz çalışıyor.

Fakat buradan:

P(1)

sonucunu çıkaramayız.

Çünkü:

1\not\ge2.

Geçiş var ama başlangıç yok

Şöyle bir zincir kurmuş olduk:

P(2) ───▶ P(3) ───▶ P(4) ───▶ P(5) ───▶ ...

Bu zincir kendi içinde çalışır.

Ama $P(1)$ 'e bağlanmamıştır.

Dolayısıyla tümevarım adımı tek başına bütün doğal sayılar için sonuç vermez.

Domino benzetmesine dönersek:

Bütün dominolar birbirini devirebilecek biçimde yerleştirilmiş olabilir; ama ilk dominoyu hiç devirmediysen hiçbir şey başlamaz.

13. Yalnız başlangıç adımı yeterli midir?

O da yetmez.

Şu iddiayı düşünelim:

P(n): \quad n\le5.

Başlangıçta:

P(1)

doğrudur.

Ayrıca:

P(2),P(3),P(4),P(5)

de doğrudur.

Ama:

P(6)

yanlıştır.

Dolayısıyla:

P(5)\Rightarrow P(6)

geçişi başarısızdır.

Başlangıç var ama zincir kırılıyor

P(1) ─▶ P(2) ─▶ P(3) ─▶ P(4) ─▶ P(5) ─X─▶ P(6)

İlk durumun doğru olması bütün sonraki durumların doğru olmasını sağlamaz.

14. En sık yapılan mantıksal hata

Tümevarım adımında hedefimiz:

P(k)\Rightarrow P(k+1)

olmalıdır.

Fakat bazen şu hata yapılır:

$P(k+1)$ doğru olsun...

ve ardından $P(k+1)$ 'in doğru olduğu sonucuna ulaşılır.

Bu hiçbir şeyi ispatlamaz.

Çünkü ispatlamamız gereken sonucu baştan varsaymış oluruz.

Varsayacağın şey $P(k)$, göstereceğin şey $P(k+1)$

Doğru yapı:

\boxed{ P(k)\text{ doğru varsay} \quad\longrightarrow\quad P(k+1)\text{ doğru olduğunu göster} }

Yanlış yapı:

P(k+1)\text{ doğru varsay} \quad\longrightarrow\quad P(k+1)\text{ doğrudur}.

15. Tümevarımın başlangıç noktası neden her zaman $1$ değildir?

Örneğin bir teorem yalnızca:

n\ge4

için geçerli olabilir.

Bu durumda başlangıç adımımız:

P(4)

olur.

Sonra:

P(k)\Rightarrow P(k+1) \qquad (k\ge4)

gösteririz.

Zincir:

P(4) ───▶ P(5) ───▶ P(6) ───▶ P(7) ───▶ ...

şeklinde başlar.

Dolayısıyla matematiksel tümevarımın özü:

“ $n=1$ 'den başlamak”

değildir.

Özü:

İddianın geçerli olduğu ilk noktadan başlayıp ardıl adımlarla bütün sonraki doğal sayıları kapsamak

tır.

16. Neden özellikle doğal sayılar?

Burada tümevarımın matematikteki gerçek yerini görmeye başlıyoruz.

Doğal sayılarda:

1\rightarrow2\rightarrow3\rightarrow4\rightarrow\cdots

şeklinde belirgin bir ardıl (successor) yapısı vardır.

Her sayıdan sonraki sayıya:

n\mapsto n+1

ile geçilir.

Bu nedenle:

P(n)\Rightarrow P(n+1)

geçişi doğal sayı zincirini adım adım dolaşabilir.

Ama reel sayılarda durum farklıdır.

Örneğin:

P(x)\Rightarrow P(x+1)

göstermek, $P(x)$ 'in bütün reel sayılar için doğru olduğunu göstermez.

Çünkü:

0,\frac12,\sqrt2,\pi,\ldots

gibi sayılar tek bir başlangıçtan sürekli $+1$ yaparak elde edilemez.

Tümevarım doğal sayıların yapısına dayanır

Tümevarım yalnızca bir “ispat numarası” değildir.

Doğal sayıların:

bir başlangıca sahip olması,
ardıl işlemiyle ilerlemesi,
bu ilerlemenin boşluk bırakmaması

ile ilgilidir.

Bu bağlantıyı 2.01.04 — Ardıl ilkesi, doğal sayıların yapısı ve tümevarım fikri biriminde daha temelden inceleyeceğiz.

17. Tarihsel gelişim

Matematiksel tümevarım tek bir kişinin bir anda ortaya attığı bir yöntem değildir.

Doğal sayılar üzerinde bir durumdan sonraki duruma geçerek genel sonuç çıkarma biçimleri matematik tarihinde farklı dönemlerde görülür.

Orta Çağ İslam matematiğinde özellikle el-Kerecî (al-Karajī) ve onu izleyen cebir geleneğinde, kuvvetler ve toplamlarla ilgili bazı sonuçlarda modern tümevarıma benzeyen ardışık akıl yürütmeler kullanılmıştır.

yüzyılda Blaise Pascal, aritmetik üçgeni üzerine çalışırken ardışık durumları birbirine bağlayan açık tümevarımsal argümanlar kullandı.
yüzyılda doğal sayıların mantıksal ve aksiyomatik temellerinin daha sistematik biçimde incelenmesiyle tümevarım ilkesi modern matematikte çok daha açık bir konum kazandı. Peano tipi doğal sayı aksiyomlarında tümevarım, doğal sayı sisteminin temel özelliklerinden biri olarak formüle edilir.

Dolayısıyla modern matematiksel tümevarımı en doğru biçimde:

doğal sayıların yapısı üzerine yüzyıllar içinde gelişmiş ve giderek biçimselleştirilmiş bir ispat ilkesi

olarak düşünmek gerekir.

18. Nerelerde kullanılır?

Tümevarım özellikle bir problemde $n$ 'den $n+1$ 'e doğal bir geçiş bulunduğunda güçlüdür.

1. Toplamlar ve özdeşlikler

Örneğin:

1+3+5+\cdots+(2n-1)=n^2

veya

1^2+2^2+\cdots+n^2 = \frac{n(n+1)(2n+1)}6

gibi sonsuz sayıda $n$ için geçerli formüller tümevarımla ispatlanabilir.

2. Sayı teorisi

Bölünebilme ve kalan özellikleri:

a\mid f(n)

gibi iddialarda sık sık $n$ 'den $n+1$ 'e geçiş kurulabilir.

Biraz önce:

7\mid(8^n-1)

örneğini gördük.

3. Diziler ve özyinelemeli yapılar

Bir dizi:

a_{n+1}=F(a_n)

gibi önceki terim üzerinden tanımlanıyorsa, bir özelliğin bütün terimler için doğru olduğunu göstermek çoğu zaman tümevarıma dönüşür.

Örneğin:

“Her $n$ için $a_n>0$ .”

gibi bir iddia, $a_n>0$ bilgisinden $a_{n+1}>0$ sonucuna geçilerek ispatlanabilir.

4. Kombinatorik

Binom katsayıları, Pascal özdeşlikleri ve sonlu yapıların $n$ elemanlı durumdan $n+1$ elemanlı duruma geçirilmesi tümevarımla sık sık incelenir.

5. Bilgisayar bilimi

Bir algoritmanın:

$1$ elemanlı girdide doğru çalıştığını,
$k$ elemanlı girdide doğru çalışıyorsa $k+1$ elemanlı girdide de doğru çalıştığını

göstermek, algoritma doğruluğu ispatlarında tümevarımın temel kullanımlarından biridir.

Özellikle özyinelemeli algoritmalar doğal olarak tümevarımsal ispatlarla eşleşir.

19. Tümevarım her ispat için en iyi yöntem midir?

Hayır.

Bir önerme doğal sayılarla indeksleniyor diye mutlaka tümevarım kullanılmaz.

Örneğin:

1+2+\cdots+n=\frac{n(n+1)}2

formülü tümevarımla ispatlanabilir; fakat terimleri baştan ve sondan eşleyerek doğrudan bir ispat da kurulabilir.

Matematikte amaç:

“Tümevarım gördüm, hemen uygula.”

değildir.

Amaç:

“Problemin yapısı ardışık mı? $n+1$ durumu $n$ durumundan üretilebiliyor mu?”

sorusunu sorabilmektir.

Yöntem seçimi

Tümevarım özellikle:

P(n)\rightarrow P(n+1)

bağlantısının doğal olduğu problemlerde güçlüdür.

Fakat daha kısa, daha açıklayıcı bir doğrudan ispat varsa tümevarım kullanmak zorunlu değildir.

Bir ispat yöntemi yalnızca sonucu değil, sonucun neden doğru olduğunu ne kadar iyi gösterdiğiyle de değerlendirilir.

20. Bir tümevarım ispatını okurken kontrol listesi

Bir tümevarım ispatı gördüğünde şu soruları sor:

$P(n)$ açıkça tanımlanmış mı?
İddianın hangi $n$ değerinden başladığı belli mi?
Başlangıç durumu gerçekten doğrulanmış mı?
$k$ rastgele bir doğal sayı olarak mı seçilmiş?
Tümevarım varsayımı açıkça belirtilmiş mi?
İspatlanması gereken $P(k+1)$ açık mı?
$P(k)$ bilgisi gerçekten kullanılmış mı?
Geçiş her uygun $k$ için geçerli mi?
Sonuç yalnızca ispatlanan aralık için mi söyleniyor?

Bu sorulardan biri cevapsızsa ispatta bir boşluk bulunabilir.

21. Bir adım daha ileri: güçlü tümevarım fikri

Bazen $P(k+1)$ 'i göstermek için yalnızca $P(k)$ yetmez.

Daha önceki birkaç duruma birden ihtiyaç duyabiliriz:

P(1),P(2),\ldots,P(k).

Bu durumda güçlü tümevarım (strong induction) adı verilen biçim kullanılır.

Temel fikir:

P(1),P(2),\ldots,P(k) \Rightarrow P(k+1).

Örneğin bir doğal sayının asal çarpanlara ayrılması gibi problemlerde yeni sayıyı daha küçük sayıların özelliklerinden kurmak doğal olabilir.

Güçlü tümevarım burada ayrı bir teknik olarak ayrıntılandırılmayacaktır.

Önemli olan şimdilik onun da aynı doğal sayı yapısına dayandığını görmektir.

22. Matematik haritasındaki yerimiz

Şimdiye kadar ispat yöntemlerinde şu araçları gördük:

Doğrudan ispat
      │
      ├──▶ Karşıt ters
      │
      ├──▶ Çelişki
      │
      ├──▶ Durumlara ayırma
      │
      ├──▶ Varlık / teklik
      │
      └──▶ Matematiksel tümevarım

Tümevarımı diğerlerinden ayıran özellik, özellikle doğal sayılar boyunca ilerleyen sonsuz önerme ailelerini hedeflemesidir.

Daha ileride bu fikir birçok farklı biçimde yeniden karşımıza çıkacak:

Doğal sayıların ardıl yapısı
          │
          ▼
Matematiksel tümevarım
          │
          ├──▶ Diziler ve özyineleme
          ├──▶ Sayı teorisi
          ├──▶ Kombinatorik
          ├──▶ Algoritma doğruluğu
          ├──▶ Güçlü tümevarım
          └──▶ Yapısal tümevarım

Tümevarım böylece yalnızca bir ispat tekniği değil, özyinelemeli ve ayrık yapıların temel düşünme biçimlerinden biri hâline gelir.

23. Kısa sentez

Neden vardı?

Doğal sayılarla indekslenen sonsuz sayıda iddiayı tek tek kontrol ederek ispatlayamayız.

Ne öğrendik?

Matematiksel tümevarım iki koşula dayanır:

P(n_0)

P(k)\Rightarrow P(k+1).

Birincisi zinciri başlatır, ikincisi zincirin devamını garanti eder.

Neyi artık yapabiliyoruz?

Toplam, bölünebilme ve benzeri doğal sayı iddialarını sonsuz sayıda ayrı durum kontrol etmeden ispatlayabiliriz.

En önemli ayrım nedir?

Matematiksel tümevarım:

“Birçok örnek doğru çıktı.”

demek değildir.

Onu ispat yapan şey, genel geçiş mekanizmasının kanıtlanmasıdır.

Sırada ne var?

Bu yöntemin neden doğal sayılar üzerinde bu kadar doğal olduğunu ileride doğal sayıların ardıl ve iyi sıralama yapısıyla daha temelden göreceğiz. Tümevarım daha sonra dizilerde, sayı teorisinde, kombinatorikte ve algoritmik yapılarda tekrar tekrar kullanılacak.

24. Öğrenme kontrolü

Kavrama

Matematiksel tümevarım neden yalnızca çok sayıda örnek kontrol etmek değildir?
Başlangıç adımı ile tümevarım adımının görevlerini kendi sözlerinle açıkla.
Tümevarım varsayımında $P(k)$ 'yi kabul etmek neden döngüsel akıl yürütme değildir?
Tümevarımın doğal sayıların yapısıyla ilişkisi nedir?

Teknik

Tümevarım kullanarak her $n\ge1$ için

1+3+5+\cdots+(2n-1)=n^2

olduğunu ispatla.

Her $n\ge1$ için

3\mid(4^n-1)

olduğunu tümevarımla göster.

Gerekçelendirme

Birisi yalnızca

P(k)\Rightarrow P(k+1)

geçişini ispatlayıp “dolayısıyla $P(n)$ bütün doğal sayılar için doğrudur” sonucuna ulaşıyor. İspattaki eksik nedir?

Bir tümevarım ispatında $P(k+1)$ doğru kabul edilip yeniden $P(k+1)$ sonucuna ulaşılması neden geçerli değildir?

Transfer

Bir dizi

a_1=2, \qquad a_{n+1}=3a_n+1

ile tanımlansın.

Her $n\ge1$ için:

a_n>0

olduğunu tümevarımla ispatlamak için nasıl bir yapı kurardın?

Şu iddia yalnızca $n\ge5$ için geçerli olsun. Tümevarım ispatının başlangıç adımı hangi önerme olmalıdır? Neden $P(1)$ 'i kontrol etmek gerekli değildir?

25. Birimin tamamlanma ölçütü

Bu birimi tamamlamış sayılmak için:

matematiksel tümevarımın hangi probleme cevap verdiğini açıklayabilmeli,
matematiksel tümevarımı örneklerden genelleme yapmaktan ayırabilmeli,
başlangıç adımının neden gerekli olduğunu açıklayabilmeli,
tümevarım varsayımının mantıksal rolünü anlayabilmeli,
$P(k)\Rightarrow P(k+1)$ geçişini doğru kurabilmeli,
basit bir toplam veya bölünebilme iddiasını tümevarımla ispatlayabilmeli,
hatalı bir tümevarım ispatındaki mantıksal boşluğu teşhis edebilmelisin.

En önemlisi, formülü unutmuş olsan bile şu düşünceyi yeniden kurabilmelisin:

\boxed{ \text{Başlangıcı ispatla} \quad+\quad \text{Her adımdan sonrakine geçişi ispatla} \quad\Longrightarrow\quad \text{Bütün doğal sayı zincirini kapsa} }

01.06.08 — Matematiksel Tümevarım

Birim kartı

1. Başlangıç problemi: sonsuz sayıda iddia

2. Eski araç neden yetmedi?

3. Temel sezgi: tek tek taşları değil, geçiş mekanizmasını ispatlamak

4. Matematiksel tümevarım nedir?

1. Başlangıç adımı

2. Tümevarım adımı

5. İki adımın farklı görevleri

Başlangıç adımı ne yapar?

Tümevarım adımı ne yapar?

6. Çok önemli: Tümevarım varsayımı ne demektir?

7. İlk tam ispat: ilk nnn doğal sayının toplamı

1. Başlangıç adımı

2. Tümevarım varsayımı

3. Tümevarım adımı

8. Tümevarım neden gerçekten çalışıyor?

9. İkinci örnek: bölünebilme

Başlangıç

Tümevarım varsayımı

Tümevarım adımı

10. Tümevarım ispatı nasıl tasarlanır?

Adım 1 — İddiayı açıkça tanımla

Adım 2 — Başlangıç değerini belirle

Adım 3 — Başlangıç durumunu doğrula

Adım 4 — Rastgele bir kkk seç

Adım 5 — Tümevarım varsayımını açıkça yaz

Adım 6 — Hedefini açıkça yaz

Adım 7 — P(k)P(k)P(k) bilgisini kullan

Adım 8 — Mantıksal sonucu belirt

11. Tümevarım ne değildir?

12. Başlangıç adımını atlayabilir miyiz?

13. Yalnız başlangıç adımı yeterli midir?

14. En sık yapılan mantıksal hata

15. Tümevarımın başlangıç noktası neden her zaman 111 değildir?

16. Neden özellikle doğal sayılar?

17. Tarihsel gelişim

18. Nerelerde kullanılır?

19. Tümevarım her ispat için en iyi yöntem midir?

20. Bir tümevarım ispatını okurken kontrol listesi

21. Bir adım daha ileri: güçlü tümevarım fikri

22. Matematik haritasındaki yerimiz

23. Kısa sentez

Neden vardı?

Ne öğrendik?

Neyi artık yapabiliyoruz?

En önemli ayrım nedir?

Sırada ne var?

24. Öğrenme kontrolü

Kavrama

Teknik

Gerekçelendirme

Transfer

25. Birimin tamamlanma ölçütü

7. İlk tam ispat: ilk $n$ doğal sayının toplamı

Adım 4 — Rastgele bir $k$ seç

Adım 7 — $P(k)$ bilgisini kullan

15. Tümevarımın başlangıç noktası neden her zaman $1$ değildir?