9 Doğal Sayılar ve Tümevarım
Şimdiye kadar reel sayıların cebirsel ve sıralama aksiyomlarını kullandık; \(0\) ve \(1\) sayıları aksiyomlarla verildi, \(1 + 1\), \(1 + 1 + 1\) gibi sayıları da elde edebiliyoruz. Ama “doğal sayılar” dediğimiz \(1, 2, 3, \dots\) kümesi aksiyomlarda yoktur. Üç nokta “böyle devam eder” der; matematiksel bir tanım ise üç noktaya izin vermez. Bu bölümde doğal sayıları reel sayıların içinde kesin olarak tanımlayacak, ardından onların en önemli özelliğini — tümevarım ilkesini — bir teorem olarak ispatlayacağız. Tümevarım, “her \(n\) için” biçimindeki sonsuz sayıda önermeyi iki adımda ispatlamanın yoludur ve bir önceki bölümde ertelediğimiz genel üçgen eşitsizliği dâhil, ileride sayısız yerde kullanılacaktır.
Bölüm boyunca Bölüm 6.2 ve Bölüm 7.1 altındaki aksiyomlar ile Bölüm 6–8’deki sonuçları kullanacağız; tamlık aksiyomu henüz gerekmeyecek.
9.1 Tümevarımsal Kümeler ve Doğal Sayılar
Doğal sayıları sezgisel olarak şöyle üretiriz: \(1\)’den başla, sürekli \(1\) ekle. Bu üretim kuralını bir kümenin özelliği olarak yazalım: küme \(1\)’i içermeli ve içerdiği her sayının bir fazlasını da içermeli.
Tanım 9.1 (Tümevarımsal Küme) \(A \subset \mathbb{R}\) olsun. Aşağıdaki iki koşul sağlanıyorsa \(A\) kümesine tümevarımsal (inductive) denir:
- \(1 \in A\);
- her \(x \in A\) için \(x + 1 \in A\).
Bu tanımı sağlayan pek çok küme vardır; bir kısmı doğal sayılardan “fazlasını” içerir.
Örnek 9.1 (Tümevarımsal Olan ve Olmayan Kümeler) Aşağıdaki kümelerin tümevarımsal olup olmadığını belirleyiniz: \(\mathbb{R}\), \(\ \mathbb{R}^{+} = (0, \infty)\), \(\ [1, \infty)\), \(\ \{1\} \cup [2, \infty)\), \(\ (1, \infty)\), \(\ [0, 5]\).
Çözüm
\(\mathbb{R}\): \(1 \in \mathbb{R}\) ve toplama \(\mathbb{R}\)’de tanımlı olduğundan \(x \in \mathbb{R}\) için \(x + 1 \in \mathbb{R}\). Tümevarımsaldır.
\((0, \infty)\): Önerme 7.7 gereği \(0 < 1\), yani \(1 \in (0, \infty)\). \(x > 0\) ise (O3) ile \(x + 1 > 0 + 1 = 1 > 0\); dolayısıyla \(x + 1 \in (0, \infty)\). Tümevarımsaldır.
\([1, \infty)\): \(1 \ge 1\). \(x \ge 1\) ise \(x + 1 \ge 2 > 1\). Tümevarımsaldır.
\(\{1\} \cup [2, \infty)\): \(1\) kümededir. \(x = 1\) ise \(x + 1 = 2 \in [2, \infty)\); \(x \ge 2\) ise \(x + 1 \ge 3 \ge 2\). Tümevarımsaldır. Dikkat: bu küme \((1, 2)\) aralığındaki hiçbir sayıyı içermez ama \(\frac{5}{2}\) gibi “doğal olmayan” sayıları içerir.
\((1, \infty)\): \(1 \notin (1, \infty)\) olduğundan birinci koşul bozulur. Tümevarımsal değildir.
\([0, 5]\): \(1 \in [0, 5]\) ama \(5 \in [0, 5]\) iken \(5 + 1 = 6 \notin [0, 5]\). İkinci koşul bozulur; tümevarımsal değildir.
\(\blacksquare\)
Örnek, aradığımız kümeyi işaret ediyor: doğal sayılar kümesi tümevarımsal olmalı, ama “fazlalık” içermemeli — yani tümevarımsal kümelerin en küçüğü olmalı. En küçük kümeyi elde etmenin standart yolu, adayların hepsini kesiştirmektir.
Tanım 9.2 (Doğal Sayılar Kümesi) \(\mathcal{T}\), \(\mathbb{R}\)’nin bütün tümevarımsal alt kümelerinin ailesi olsun (\(\mathbb{R} \in \mathcal{T}\) olduğundan aile boş değildir). Bu ailenin kesişimine (Tanım 3.8) doğal sayılar kümesi denir ve \(\mathbb{N}\) ile gösterilir:
\[\mathbb{N} = \bigcap_{A \in \mathcal{T}} A = \{x \in \mathbb{R} : \text{her tümevarımsal } A \subset \mathbb{R} \text{ için } x \in A\}.\]
\(\mathbb{N}\)’nin elemanlarına doğal sayı denir.
Tanım gereği bir \(x\) reel sayısı ancak ve ancak her tümevarımsal kümede bulunuyorsa doğal sayıdır. Bu tanımın işe yaradığını hemen görelim: \(\mathbb{N}\) kendisi tümevarımsaldır ve gerçekten en küçüğüdür.
Önerme 9.1 (Doğal Sayılar En Küçük Tümevarımsal Kümedir)
- \(\mathbb{N}\) tümevarımsal bir kümedir.
- \(A \subset \mathbb{R}\) tümevarımsal ise \(\mathbb{N} \subset A\)’dır.
İspat
Madde (1). Her tümevarımsal \(A\) için \(1 \in A\) olduğundan \(1\) kesişimdedir: \(1 \in \mathbb{N}\). Şimdi \(x \in \mathbb{N}\) olsun. Kesişimin tanımı gereği \(x\) her tümevarımsal \(A\)’nın elemanıdır; her böyle \(A\) tümevarımsal olduğundan \(x + 1 \in A\)’dır. Demek ki \(x + 1\) her tümevarımsal kümede bulunur, yani \(x + 1 \in \mathbb{N}\).
Madde (2). \(A\) tümevarımsal ise \(A \in \mathcal{T}\)’dir ve bir ailenin kesişimi ailenin her üyesinin alt kümesidir (Teorem 3.2 (1)); dolayısıyla \(\mathbb{N} \subset A\).
\(\blacksquare\)
\(1 \in \mathbb{N}\) olduğundan \(2 := 1 + 1\), \(3 := 2 + 1\), \(4 := 3 + 1\), … sayıları da \(\mathbb{N}\)’dedir. Bunlar gerçekten farklı sayılardır: Önerme 7.7 ile \(0 < 1\), (O3) ile \(1 = 1 + 0 < 1 + 1 = 2\); aynı yolla \(2 < 3 < 4 < \cdots\). Ayrıca Örnek 9.1’ndeki \(\{1\} \cup [2, \infty)\) kümesi tümevarımsal olduğundan \(\mathbb{N}\) onun alt kümesidir: \(1\) ile \(2\) arasında doğal sayı yoktur. Bu gözlemi aşağıda genelleştireceğiz.
9.2 Tümevarım İlkesi
“Her doğal sayı için \(P(n)\) doğrudur” türünden bir iddiayı ispatlamak istiyoruz. Sonsuz tane önerme var; teker teker kontrol edemeyiz. Ama doğal sayılar en küçük tümevarımsal küme olduğu için şu strateji işler: \(P\)’nin doğru olduğu sayıların kümesinin tümevarımsal olduğunu göster; o zaman bu küme \(\mathbb{N}\)’nin tamamını kapsar.
Teorem 9.1 (Tümevarım İlkesi)
- Küme biçimi. \(A \subset \mathbb{N}\) tümevarımsal ise \(A = \mathbb{N}\)’dir.
- Önerme biçimi. Her \(n \in \mathbb{N}\) için bir \(P(n)\) önermesi verilmiş olsun. Eğer
- \(P(1)\) doğruysa (temel adım) ve
- her \(k \in \mathbb{N}\) için “\(P(k)\) doğru \(\Rightarrow\) \(P(k+1)\) doğru” ise (tümevarım adımı),
İspat
Madde (1). \(A\) tümevarımsal olduğundan Önerme 9.1 (2) ile \(\mathbb{N} \subset A\). Varsayımla \(A \subset \mathbb{N}\). İki kapsama birlikte \(A = \mathbb{N}\) verir.
Madde (2). \(A = \{n \in \mathbb{N} : P(n) \text{ doğru}\}\) kümesini alalım; açıkça \(A \subset \mathbb{N}\). Temel adım \(1 \in A\) der. Tümevarım adımı şunu der: \(k \in A\) ise (\(P(k)\) doğruysa) \(P(k+1)\) doğrudur; Önerme 9.1 (1) ile \(k + 1 \in \mathbb{N}\) olduğundan \(k + 1 \in A\). Demek ki \(A\) tümevarımsaldır. Madde (1) ile \(A = \mathbb{N}\), yani her \(n \in \mathbb{N}\) için \(P(n)\) doğrudur.
\(\blacksquare\)
Domino benzetmesi tam olarak budur: ilk taşı devirmek (temel adım) ve her taşın bir sonrakini devireceğinden emin olmak (tümevarım adımı), bütün taşların devrileceğini garantiler. Tümevarım adımında “\(P(k)\) doğru” varsayımına tümevarım hipotezi denir; ispatlanan şey \(P(k)\)’nin doğruluğu değil, \(P(k)\)’den \(P(k+1)\)’e geçilebildiğidir.
- İspatlanacak önermeyi \(n\)’ye bağlı olarak açıkça yaz: “\(P(n)\): …”.
- Temel adım: \(P(1)\)’in doğru olduğunu göster (çoğunlukla doğrudan hesap).
- Tümevarım hipotezi: “Bir \(k \in \mathbb{N}\) için \(P(k)\)’nin doğru olduğunu varsayalım.”
- Tümevarım adımı: Bu varsayımdan \(P(k+1)\)’i çıkar. Hipotezi tam olarak nerede kullandığını belirt.
- Sonuç: “Teorem 9.1 gereği \(P(n)\) her \(n \in \mathbb{N}\) için doğrudur.”
Temel adım olmadan tümevarım adımı hiçbir şey kanıtlamaz: “\(P(n)\): \(n \ge 2\)” önermesi için \(P(k) \Rightarrow P(k+1)\) doğrudur (\(k \ge 2\) ise \(k + 1 \ge 2\)) ama \(P(1)\) yanlıştır. Tersine, “\(P(n)\): \(n = 1\)” için temel adım doğru, tümevarım adımı yanlıştır (\(P(1)\) doğru ama \(P(2)\) yanlış). İki adımın da yazılması ve her \(k \in \mathbb{N}\) için geçerli olması gerekir.
İlk örneklerimiz klasik toplam formülleridir. Şimdilik toplamları \(1 + 2 + \cdots + n\) biçiminde yazıyoruz; toplam sembolünün kesin tanımını biraz sonra vereceğiz.
Örnek 9.2 (Ardışık Doğal Sayıların Toplamı) Her \(n \in \mathbb{N}\) için
\[1 + 2 + \cdots + n = \frac{n(n+1)}{2}\]
olduğunu gösteriniz.
Çözüm
\(P(n)\), yukarıdaki eşitlik olsun.
Temel adım. \(n = 1\) için sol taraf \(1\), sağ taraf \(\frac{1 \cdot 2}{2} = 1\). \(P(1)\) doğrudur.
Tümevarım adımı. Bir \(k \in \mathbb{N}\) için \(P(k)\) doğru olsun: \(1 + 2 + \cdots + k = \frac{k(k+1)}{2}\). \(P(k+1)\)’in sol tarafını yazıp hipotezi kullanalım:
\[1 + 2 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1) = (k+1)\left(\frac{k}{2} + 1\right) = \frac{(k+1)(k+2)}{2}.\]
Sağdaki ifade, \(P(k+1)\)’in sağ tarafı \(\frac{(k+1)\big((k+1)+1\big)}{2}\) ile aynıdır. Demek ki \(P(k) \Rightarrow P(k+1)\).
Teorem 9.1 gereği \(P(n)\) her \(n \in \mathbb{N}\) için doğrudur.
\(\blacksquare\)
Örnek 9.3 (İlk n Tek Sayının Toplamı) Her \(n \in \mathbb{N}\) için \(1 + 3 + 5 + \cdots + (2n - 1) = n^2\) olduğunu gösteriniz.
Çözüm
Temel adım. \(n = 1\): sol taraf \(2 \cdot 1 - 1 = 1\), sağ taraf \(1^2 = 1\).
Tümevarım adımı. \(1 + 3 + \cdots + (2k - 1) = k^2\) olsun. Bir sonraki tek sayı \(2(k+1) - 1 = 2k + 1\)’dir; onu ekleyelim:
\[1 + 3 + \cdots + (2k - 1) + (2k + 1) = k^2 + 2k + 1 = (k + 1)^2.\]
Burada ilk eşitlikte tümevarım hipotezi, ikincisinde dağılma aksiyomuyla açılan \((k+1)^2 = k^2 + 2k + 1\) özdeşliği kullanıldı. Böylece \(P(k+1)\) doğrudur ve Teorem 9.1 ile iddia her \(n\) için geçerlidir.
\(\blacksquare\)
9.3 Doğal Sayıların Temel Özellikleri
Doğal sayılar hakkında “bilinen” her şey artık ispat gerektirir; ispatların hepsi tümevarımla yapılır. Önce toplama ve çarpma altında kapalılık.
Önerme 9.2 (Doğal Sayılar Toplama ve Çarpma Altında Kapalıdır) \(m, n \in \mathbb{N}\) ise \(m + n \in \mathbb{N}\) ve \(mn \in \mathbb{N}\)’dir.
İspat
\(m \in \mathbb{N}\) sabit olsun; \(n\) üzerinden tümevarım yapacağız.
Toplama. \(A = \{n \in \mathbb{N} : m + n \in \mathbb{N}\}\) olsun. \(\mathbb{N}\) tümevarımsal olduğundan \(m + 1 \in \mathbb{N}\), yani \(1 \in A\). \(n \in A\) ise \(m + n \in \mathbb{N}\); yine tümevarımsallıkla \((m + n) + 1 \in \mathbb{N}\) ve (A2) ile \((m + n) + 1 = m + (n + 1)\), yani \(n + 1 \in A\). \(A\) tümevarımsaldır; Teorem 9.1 (1) ile \(A = \mathbb{N}\).
Çarpma. \(B = \{n \in \mathbb{N} : mn \in \mathbb{N}\}\) olsun. (M3) ile \(m \cdot 1 = m \in \mathbb{N}\), yani \(1 \in B\). \(n \in B\) ise \(mn \in \mathbb{N}\); (D) ile \(m(n + 1) = mn + m\) ve toplama altında kapalılıkla \(mn + m \in \mathbb{N}\), yani \(n + 1 \in B\). \(B\) tümevarımsaldır, dolayısıyla \(B = \mathbb{N}\).
\(\blacksquare\)
Çıkarma ve bölme için kapalılık yoktur: \(1 - 2\) ve \(\frac{1}{2}\) doğal sayı değildir; ikisi de \(1\)’den küçüktür, oysa aşağıdaki önerme gereği hiçbir doğal sayı \(1\)’den küçük olamaz. Bu eksikler sırasıyla tam sayılar (Tanım 11.1) ve rasyonel sayılarla (Tanım 11.6) giderilecektir.
Şimdi doğal sayıların sayı doğrusundaki dizilişini kesinleştirelim: \(1\) en küçüktür, ardışık iki doğal sayı arasında başka doğal sayı yoktur ve büyük olandan küçüğü çıkarınca yine doğal sayı elde edilir.
Önerme 9.3 (Doğal Sayıların Dizilişi) \(m, n \in \mathbb{N}\) olsun.
- \(n \ge 1\)’dir. Dolayısıyla \(1\), \(\mathbb{N}\)’nin en küçük elemanıdır ve her doğal sayı pozitiftir.
- \(n \ne 1\) ise \(n - 1 \in \mathbb{N}\)’dir; dolayısıyla \(n \ge 2\)’dir.
- \(n < x < n + 1\) koşulunu sağlayan bir \(x \in \mathbb{N}\) yoktur: ardışık iki doğal sayı arasında doğal sayı bulunmaz.
- \(m < n\) ise \(m + 1 \le n\) ve \(n - m \in \mathbb{N}\)’dir.
İspat
Madde (1). \(A = \{n \in \mathbb{N} : n \ge 1\}\) olsun. \(1 \ge 1\) olduğundan \(1 \in A\). \(n \in A\) ise \(n \ge 1\) ve (O3) ile \(n + 1 \ge 1 + 1 = 2 > 1\); dolayısıyla \(n + 1 \in A\). Teorem 9.1 (1) ile \(A = \mathbb{N}\). Pozitiflik \(n \ge 1 > 0\)’dan çıkar.
Madde (2). \(A = \{1\} \cup \{n \in \mathbb{N} : n - 1 \in \mathbb{N}\}\) olsun; \(A \subset \mathbb{N}\)’dir. \(1 \in A\). \(n \in A\) olsun; \(n \in \mathbb{N}\) olduğundan \(n + 1 \in \mathbb{N}\) ve \((n + 1) - 1 = n \in \mathbb{N}\), yani \(n + 1 \in A\). Böylece \(A\) tümevarımsal ve \(A = \mathbb{N}\): her doğal sayı ya \(1\)’dir ya da bir eksiği doğal sayı olan bir sayıdır. \(n \ne 1\) ise \(n - 1 \in \mathbb{N}\), madde (1) ile \(n - 1 \ge 1\), yani \(n \ge 2\).
Madde (3). \(P(n)\): “\(n < x < n + 1\) olan \(x \in \mathbb{N}\) yoktur” önermesi için tümevarım yapalım.
Temel adım. \(1 < x < 2\) olan bir \(x \in \mathbb{N}\) olsaydı \(x \ne 1\) olurdu ve madde (2) ile \(x \ge 2\) gelirdi; bu \(x < 2\) ile çelişir. \(P(1)\) doğrudur.
Tümevarım adımı. \(P(k)\) doğru olsun ve \(k + 1 < x < k + 2\) olan bir \(x \in \mathbb{N}\) bulunduğunu varsayalım. \(x > k + 1 \ge 2 > 1\) olduğundan \(x \ne 1\), madde (2) ile \(x - 1 \in \mathbb{N}\). Eşitsizliklerden \(1\) çıkarınca \(k < x - 1 < k + 1\); bu, \(P(k)\) ile çelişir. Demek ki böyle \(x\) yoktur ve \(P(k+1)\) doğrudur.
Madde (4). Önce \(m + 1 \le n\): üçlem yasası (O1) gereği ya \(m + 1 \le n\) ya da \(n < m + 1\)’dir. İkincisi \(m < n\) ile birleşince \(m < n < m + 1\) verir; madde (3) bunu yasaklar. O hâlde \(m + 1 \le n\).
Şimdi \(n - m \in \mathbb{N}\) olduğunu \(m\) üzerinden tümevarımla gösterelim; \(Q(m)\): “her \(n \in \mathbb{N}\) için, \(m < n\) ise \(n - m \in \mathbb{N}\)”.
Temel adım. \(1 < n\) ise \(n \ne 1\) ve madde (2) ile \(n - 1 \in \mathbb{N}\).
Tümevarım adımı. \(Q(k)\) doğru olsun ve \(n \in \mathbb{N}\), \(k + 1 < n\) olsun. \(k < k + 1 < n\) olduğundan \(Q(k)\) ile \(n - k \in \mathbb{N}\). Ayrıca \(n - k > 1\) olduğundan \(n - k \ne 1\); madde (2) ile \((n - k) - 1 = n - (k + 1) \in \mathbb{N}\). \(Q(k+1)\) doğrudur.
\(\blacksquare\)
Bu önerme ne işe yarar? Doğal sayıların “ayrık” durduğunu söyler: bir doğal sayıya \(1\)’den daha az yaklaşan başka bir doğal sayı yoktur. İleride aynı olguyu tam sayılar için de göstereceğiz — ardışık iki tam sayı arasında tam sayı yoktur (Lemma 11.1, Bölüm 11) — ve Arşimet özelliği (Bölüm 12) buna dayanacaktır.
Doğal sayıların ikinci büyük özelliği, tümevarım ilkesine denk olan iyi sıralama ilkesidir: doğal sayılardan oluşan boş olmayan her kümenin bir en küçük elemanı vardır. Reel sayılarda bu doğru değildir; \((0, 1)\) aralığının en küçük elemanı yoktur.
Teorem 9.2 (İyi Sıralama İlkesi) \(S \subset \mathbb{N}\) boş olmayan bir küme olsun. \(S\)’nin bir en küçük elemanı vardır: öyle bir \(m \in S\) bulunur ki her \(s \in S\) için \(m \le s\). Bu eleman tektir.
İspat
Teklik kolaydır: \(m\) ve \(m'\) ikisi de en küçük eleman olsa \(m \le m'\) ve \(m' \le m\), dolayısıyla (O1) ile \(m = m'\) olur.
Varlık için olmayana ergi yöntemini kullanalım: \(S\)’nin en küçük elemanı olmasın; \(S = \varnothing\) olduğunu göstereceğiz. Bunun için
\[A = \{n \in \mathbb{N} : k \le n \text{ olan her } k \in \mathbb{N} \text{ için } k \notin S\}\]
kümesinin tümevarımsal olduğunu gösterelim; \(A\), “\(S\)’nin \(n\)’ye kadar hiçbir elemanı olmayan” \(n\)’lerden oluşur.
Temel adım: \(1 \in A\). \(1 \in S\) olsaydı, Önerme 9.3 (1) gereği her \(s \in S\) için \(1 \le s\) olurdu; yani \(1\), \(S\)’nin en küçük elemanı olurdu. Bu, varsayımımızla çelişir; demek ki \(1 \notin S\). \(k \le 1\) olan tek doğal sayı \(k = 1\) olduğundan (\(k \ge 1\)) \(1 \in A\).
Tümevarım adımı. \(n \in A\) olsun; \(n + 1 \in A\) olduğunu gösterelim. Önce \(n + 1 \notin S\): aksi hâlde \(n + 1\) en küçük eleman olurdu. Gerçekten, \(s \in S\) ise \(n \in A\) nedeniyle \(s \le n\) olamaz, yani \(n < s\); Önerme 9.3 (4) ile \(n + 1 \le s\). Bu her \(s \in S\) için geçerli olduğundan \(n + 1 \in S\) olsaydı en küçük eleman olurdu — çelişki. Şimdi \(k \le n + 1\) olan bir \(k \in \mathbb{N}\) alalım. Ya \(k = n + 1\)’dir, o zaman az önce gördüğümüz gibi \(k \notin S\); ya da \(k < n + 1\)’dir, o zaman Önerme 9.3 (4) ile \(k + 1 \le n + 1\), yani \(k \le n\) ve \(n \in A\) nedeniyle \(k \notin S\). Her iki hâlde de \(k \notin S\); demek ki \(n + 1 \in A\).
Teorem 9.1 (1) ile \(A = \mathbb{N}\). Şimdi \(s \in S\) olsa \(s \in \mathbb{N} = A\) olur; \(k = s \le s\) alınca \(s \notin S\) çıkar — çelişki. Demek ki \(S = \varnothing\). Bu, \(S\)’nin boş olmadığı varsayımıyla çelişir; o hâlde \(S\)’nin en küçük elemanı vardır.
\(\blacksquare\)
İyi sıralama ilkesi ne işe yarar? “Bir özelliği sağlayan en küçük doğal sayıyı al” adımına izin verir. Bu adım, Bölüm 12’de taban fonksiyonunun varlığında ve “en küçük karşı örnek” tekniğinde kullanılır: bir iddia bazı doğal sayılar için yanlışsa, yanlış olduğu en küçük \(n\) vardır ve bu \(n\) ile çalışmak çoğu zaman çelişki üretir. Bölüm sonu alıştırmasında iyi sıralamadan tümevarım ilkesinin geri çıktığını göstereceğiz; iki ilke birbirine denktir.
9.4 Özyineli Tanımlar
Tümevarım yalnızca ispat aracı değil, tanım aracıdır da. “\(a^n\): \(a\)’nın \(n\) kez kendisiyle çarpımı” ifadesindeki “\(n\) kez” gizli bir üç noktadır. Kesin tanım, \(n = 1\) için değeri verip \(n\)’den \(n + 1\)’e geçiş kuralını söyler; tümevarım ilkesi bu kuralın her \(n\) için tek bir değer belirlediğini garantiler.
Tanım 9.3 (Kuvvet, Faktöriyel, Toplam ve Çarpım Sembolleri) \(a \in \mathbb{R}\) ve her \(k \in \mathbb{N}\) için bir \(a_k \in \mathbb{R}\) verilmiş olsun.
- Doğal kuvvet: \(a^1 = a\) ve her \(n \in \mathbb{N}\) için \(a^{n+1} = a^n \cdot a\). Ayrıca \(a \ne 0\) için \(a^0 = 1\) kabul edilir.
- Faktöriyel: \(0! = 1\), \(1! = 1\) ve her \(n \in \mathbb{N}\) için \((n + 1)! = (n + 1) \cdot n!\).
- Toplam ve çarpım sembolleri:
\[\sum_{k=1}^{1} a_k = a_1, \qquad \sum_{k=1}^{n+1} a_k = \left(\sum_{k=1}^{n} a_k\right) + a_{n+1}; \qquad \prod_{k=1}^{1} a_k = a_1, \qquad \prod_{k=1}^{n+1} a_k = \left(\prod_{k=1}^{n} a_k\right) \cdot a_{n+1}.\]
\(\sum_{k=1}^{n} a_k\) yerine \(a_1 + a_2 + \cdots + a_n\), \(\prod_{k=1}^{n} a_k\) yerine \(a_1 a_2 \cdots a_n\) da yazılır.
Bu tür tanımlara özyineli (recursive) tanım denir. Örneğin \(a^3 = a^2 \cdot a = (a \cdot a) \cdot a\), \(4! = 4 \cdot 3! = 4 \cdot 3 \cdot 2 \cdot 1 = 24\) ve \(n! = \prod_{k=1}^{n} k\)’dır. Kuvvetlerin \(a^m a^n = a^{m+n}\) gibi kuralları tümevarımla ispatlanır; bunları üs tam sayı olacak biçimde genişlettikten sonra Teorem 11.3 olarak vereceğiz. Aşağıdaki hesaplarda yalnızca tanımın kendisini, yani \(a^{n+1} = a^n \cdot a\) eşitliğini kullanacağız. Bir de tanımdan tümevarımla çıkan şu olguyu kaydedelim: \(a > 0\) ise her \(n \in \mathbb{N}\) için \(a^n > 0\), \(a \ge 0\) ise \(a^n \ge 0\)’dır (temel adım \(a^1 = a\); adımda \(a^{n+1} = a^n \cdot a\) çarpımına Önerme 7.5 (1) ya da Önerme 6.9 uygulanır). Aşağıda bunu \(2^{k-1} > 0\) ve \(x^k \ge 0\) biçiminde kullanacağız.
“\(a^n\) her \(n\) için tanımlıdır” iddiası, \(A = \{n \in \mathbb{N} : a^n \text{ tanımlı}\}\) kümesinin tümevarımsal olmasından çıkar: \(a^1\) tanımlıdır ve \(a^n\) tanımlıysa \(a^{n+1} = a^n \cdot a\) da tanımlıdır. Tanımlanan değerin tek olduğu da benzer bir tümevarımla görülür. Bu iki gözlemin genel biçimine özyineleme teoremi denir; biz onu bu düzeyde verilmiş kabul edeceğiz.
Artık daha zengin tümevarım örnekleri yapabiliriz.
Örnek 9.4 (Üstel Büyüme Doğrusalı Geçer) Her \(n \in \mathbb{N}\) için \(2^n > n\) olduğunu gösteriniz.
Çözüm
Temel adım. \(2^1 = 2 > 1\).
Tümevarım adımı. \(2^k > k\) olsun. Tanımla \(2^{k+1} = 2^k \cdot 2 = 2^k + 2^k\). Hipotezle \(2^k > k\) ve Önerme 9.3 (1) ile \(2^k > k \ge 1\); ikisini taraf tarafa toplayalım:
\[2^{k+1} = 2^k + 2^k > k + 1.\]
\(P(k+1)\) doğrudur; Teorem 9.1 ile iddia her \(n\) için geçerlidir.
\(\blacksquare\)
Örnek 9.5 (Faktöriyel Üstelden Hızlı Büyür) Her \(n \in \mathbb{N}\) için \(n! \ge 2^{\,n-1}\) olduğunu gösteriniz.
Çözüm
Temel adım. \(n = 1\): \(1! = 1\) ve \(2^{0} = 1\); \(1 \ge 1\).
Tümevarım adımı. \(k! \ge 2^{k-1}\) olsun. Tanımla \((k+1)! = (k+1) \cdot k!\). Hipotezi pozitif sayı \(k + 1\) ile çarparsak (O4) \((k+1)! \ge (k+1) \cdot 2^{k-1}\). Öte yandan \(k \ge 1\) olduğundan \(k + 1 \ge 2\); bunu pozitif sayı \(2^{k-1}\) ile çarpınca \((k + 1) \cdot 2^{k-1} \ge 2 \cdot 2^{k-1} = 2^{k}\). Geçişlilikle \((k+1)! \ge 2^{k} = 2^{(k+1)-1}\).
(Burada \(k = 1\) için \(2^{k-1} = 2^0 = 1\) kabulü ve \(2^0 \cdot 2 = 2^1\) eşitliği kullanıldı; \(k \ge 2\) için \(2^{k-1} \cdot 2 = 2^k\) doğrudan tanımdır.)
\(\blacksquare\)
Örnek 9.6 (Bir Bölünebilme Özelliği) Her \(n \in \mathbb{N}\) için \(8^n - 1 = 7m\) olacak biçimde bir \(m \in \mathbb{N}\) bulunduğunu gösteriniz. (Bölünebilme dilinde: \(8^n - 1\), \(7\)’ye bölünür; bkz. Tanım 11.3.)
Çözüm
Temel adım. \(8^1 - 1 = 7 = 7 \cdot 1\); \(m = 1\) işe yarar.
Tümevarım adımı. \(8^k - 1 = 7m\) olacak bir \(m \in \mathbb{N}\) bulunsun; yani \(8^k = 7m + 1\). O zaman
\[8^{k+1} - 1 = 8^k \cdot 8 - 1 = (7m + 1) \cdot 8 - 1 = 56m + 8 - 1 = 56m + 7 = 7(8m + 1).\]
Önerme 9.2 ile \(8m + 1 \in \mathbb{N}\); demek ki \(m' = 8m + 1\) istenen özelliktedir. Teorem 9.1 ile iddia her \(n\) için doğrudur.
\(\blacksquare\)
9.5 Tümevarımın Değişik Biçimleri
Bazı iddialar ancak belli bir \(n_0\)’dan sonra doğrudur; bazılarında ise \(P(k+1)\)’i göstermek için yalnızca \(P(k)\) değil, öncekilerin tamamı gerekir. Tümevarım ilkesi her iki duruma da uyarlanır.
Teorem 9.3 (Bir n₀’dan Başlayan Tümevarım) \(n_0 \in \mathbb{N}\) ve her \(n \ge n_0\) doğal sayısı için bir \(P(n)\) önermesi verilmiş olsun. Eğer \(P(n_0)\) doğruysa ve \(n_0 \le k\) olan her \(k \in \mathbb{N}\) için \(P(k) \Rightarrow P(k+1)\) ise, \(n \ge n_0\) olan her \(n \in \mathbb{N}\) için \(P(n)\) doğrudur.
İspat
Her \(m \in \mathbb{N}\) için \(Q(m) := P(n_0 + m - 1)\) diyelim. Bu tanımlıdır: \(m = 1\) için \(n_0 + m - 1 = n_0\); \(m \ge 2\) için Önerme 9.3 (2) ile \(m - 1 \in \mathbb{N}\), Önerme 9.2 ile \(n_0 + (m - 1) \in \mathbb{N}\) ve \(m - 1 \ge 1\) olduğundan \(n_0 + m - 1 \ge n_0\). \(Q(1) = P(n_0)\) doğrudur. \(Q(m)\) doğruysa \(k = n_0 + m - 1 \ge n_0\) için \(P(k)\) doğrudur, varsayımla \(P(k+1) = P(n_0 + (m+1) - 1) = Q(m+1)\) doğrudur. Teorem 9.1 ile her \(m \in \mathbb{N}\) için \(Q(m)\) doğrudur.
Şimdi \(n \ge n_0\) olsun. \(n = n_0\) ise \(P(n) = Q(1)\) doğrudur. \(n > n_0\) ise Önerme 9.3 (4) ile \(n - n_0 \in \mathbb{N}\); \(m = (n - n_0) + 1 \in \mathbb{N}\) alınca \(n_0 + m - 1 = n\), yani \(P(n) = Q(m)\) doğrudur.
\(\blacksquare\)
Örnek 9.7 (Bir Yerden Sonra Doğru Olan Eşitsizlik) \(n \ge 3\) olan her \(n \in \mathbb{N}\) için \(n^2 > 2n + 1\) olduğunu gösteriniz.
Çözüm
\(n = 1\) ve \(n = 2\) için iddia yanlıştır (\(1 < 3\), \(4 < 5\)); bu yüzden \(n_0 = 3\)’ten başlıyoruz.
Temel adım. \(3^2 = 9 > 7 = 2 \cdot 3 + 1\).
Tümevarım adımı. \(k \ge 3\) ve \(k^2 > 2k + 1\) olsun. O zaman
\[(k+1)^2 = k^2 + 2k + 1 > (2k + 1) + 2k + 1 = 4k + 2 = 2(k+1) + 2k \ge 2(k+1) + 1,\]
çünkü \(k \ge 1\) nedeniyle \(2k \ge 2 > 1\). Böylece \((k+1)^2 > 2(k+1) + 1\) ve Teorem 9.3 ile iddia her \(n \ge 3\) için doğrudur.
\(\blacksquare\)
Teorem 9.4 (Güçlü Tümevarım) Her \(n \in \mathbb{N}\) için bir \(P(n)\) önermesi verilmiş olsun. Eğer \(P(1)\) doğruysa ve her \(k \in \mathbb{N}\) için
\[P(1), P(2), \dots, P(k) \text{ doğru} \ \Longrightarrow\ P(k+1) \text{ doğru}\]
ise, her \(n \in \mathbb{N}\) için \(P(n)\) doğrudur.
İspat
\(Q(n)\): “\(j \le n\) olan her \(j \in \mathbb{N}\) için \(P(j)\) doğru” önermesini alalım ve \(Q\) için sıradan tümevarım yapalım. \(j \le 1\) olan tek doğal sayı \(1\)’dir; \(P(1)\) doğru olduğundan \(Q(1)\) doğrudur. \(Q(k)\) doğru olsun: \(P(1), \dots, P(k)\) doğrudur. Varsayımla \(P(k+1)\) doğrudur. \(j \le k + 1\) olan bir \(j \in \mathbb{N}\) ya \(j = k + 1\)’dir ya da \(j < k + 1\), yani Önerme 9.3 (4) ile \(j \le k\)’dır; her iki hâlde \(P(j)\) doğrudur. Demek ki \(Q(k+1)\) doğrudur. Teorem 9.1 ile her \(n\) için \(Q(n)\), özel olarak \(P(n)\) doğrudur.
\(\blacksquare\)
Güçlü tümevarım, sıradan tümevarımdan daha güçlü bir ilke değildir — ispat gösteriyor ki ondan çıkar — ama tümevarım adımında bütün önceki durumları kullanabilmek bazı ispatları çok kolaylaştırır. Tipik örnek, her terimi önceki iki terime bağlı olan dizilerdir.
Örnek 9.8 (Fibonacci Sayıları) \(F_1 = 1\), \(F_2 = 1\) ve her \(n \in \mathbb{N}\) için \(F_{n+2} = F_{n+1} + F_n\) olsun (özyineli tanım: \(1, 1, 2, 3, 5, 8, 13, \dots\)). Her \(n \in \mathbb{N}\) için \(F_n < 2^n\) olduğunu gösteriniz.
Çözüm
Güçlü tümevarım kullanacağız, çünkü \(F_{k+1}\)’i sınırlamak için hem \(F_k\) hem \(F_{k-1}\) gerekir.
Temel adımlar. \(F_1 = 1 < 2 = 2^1\) ve \(F_2 = 1 < 4 = 2^2\).
Tümevarım adımı. \(k \ge 2\) olsun ve \(j \le k\) olan her \(j\) için \(F_j < 2^j\) doğru olsun. \(k \ge 2\) olduğundan \(k - 1 \in \mathbb{N}\) ve \(F_{k+1} = F_k + F_{k-1}\) yazılabilir. Hipotezle
\[F_{k+1} = F_k + F_{k-1} < 2^k + 2^{k-1} < 2^k + 2^k = 2^k \cdot 2 = 2^{k+1}.\]
Ortadaki adımda \(2^{k-1} < 2^{k-1} \cdot 2 = 2^k\) kullanıldı (\(2^{k-1} > 0\) olduğundan). Adımı \(k \ge 2\) için yazmamız yeterlidir: güçlü tümevarımın \(k = 1\) için istediği “\(P(1) \Rightarrow P(2)\)” koşulu, \(P(2)\) temel adımda doğrudan gösterildiği için zaten sağlanır. Teorem 9.4 ile iddia her \(n\) için doğrudur.
\(\blacksquare\)
9.6 Bernoulli Eşitsizliği
Bir kuvvetin alttan basit bir sınırı, analizde sürekli lazım olur: \((1 + x)^n\) ifadesi \(1 + nx\)’ten küçük değildir. Sezgi, \(x \ge 0\) için binom açılımından gelir (\(1 + nx\) açılımın ilk iki terimidir); ama eşitsizlik \(x \ge -1\) için de doğrudur.
Teorem 9.5 (Bernoulli Eşitsizliği) \(x \ge -1\) ve \(n \in \mathbb{N}\) ise
\[(1 + x)^n \ge 1 + nx.\]
İspat
\(n\) üzerinden tümevarım.
Temel adım. \((1 + x)^1 = 1 + x = 1 + 1 \cdot x\); eşitlik vardır.
Tümevarım adımı. \((1 + x)^k \ge 1 + kx\) olsun. \(x \ge -1\) olduğundan \(1 + x \ge 0\)’dır. \(1 + x = 0\) ise \((1+x)^{k+1} = 0 \ge 1 + (k+1)(-1) = -k\), doğrudur. \(1 + x > 0\) ise hipotezi bu pozitif sayıyla çarpabiliriz (O4):
\[(1 + x)^{k+1} = (1 + x)^k (1 + x) \ge (1 + kx)(1 + x) = 1 + (k + 1)x + kx^2.\]
Önerme 7.12 (1) ile \(x^2 \ge 0\) ve \(k > 0\) olduğundan \(kx^2 \ge 0\); dolayısıyla \(1 + (k+1)x + kx^2 \ge 1 + (k+1)x\). Geçişlilikle \((1 + x)^{k+1} \ge 1 + (k+1)x\).
\(\blacksquare\)
Bernoulli eşitsizliği ne işe yarar? \(x > 0\) için \((1 + x)^n \ge 1 + nx\) sağ tarafı \(n\) büyüdükçe her sınırı aşar (bunu bir sonraki bölümde, doğal sayıların üstten sınırsızlığıyla kanıtlayacağız); dolayısıyla \(1\)’den büyük bir sayının kuvvetleri de her sınırı aşar. \(x = 1\) için \(2^n \ge 1 + n\), Örnek 9.4’nin başka bir ispatıdır. Dizilerde \(q^n \to 0\) (\(|q| < 1\)) ve \(\sqrt[n]{a} \to 1\) sonuçları doğrudan bu eşitsizlikle kanıtlanacaktır.
\(x > -1\), \(x \ne 0\) ve \(n \ge 2\) ise eşitsizlik kesindir: \((1+x)^n > 1 + nx\). İspat aynıdır; \(n = 2\) temel adımında \((1+x)^2 = 1 + 2x + x^2 > 1 + 2x\) (\(x^2 > 0\)) ve tümevarım adımında \(kx^2 > 0\) kullanılır.
9.7 Binom Teoremi
\((a + b)^2 = a^2 + 2ab + b^2\) ve \((a+b)^3 = a^3 + 3a^2 b + 3ab^2 + b^3\) açılımlarını biliyoruz. Genel \(n\) için katsayıları veren sayılar binom katsayılarıdır.
Tanım 9.4 (Binom Katsayısı) \(n \in \mathbb{N}\) ve \(k \in \{0, 1, \dots, n\}\) için
\[\binom{n}{k} = \frac{n!}{k!\,(n-k)!}\]
sayısına binom katsayısı denir ve “\(n\)’nin \(k\)’lısı” diye okunur. (\(k < n\) iken \(n - k \in \mathbb{N}\), \(k = n\) iken \(n - k = 0\) olduğundan payda tanımlıdır.)
Tanımdan hemen çıkan değerler: \(\binom{n}{0} = \binom{n}{n} = 1\), \(\binom{n}{1} = \binom{n}{n-1} = n\) ve simetri \(\binom{n}{k} = \binom{n}{n-k}\) (payda aynı iki çarpandan oluşur). Binom katsayılarını satır satır dizince Pascal üçgeni ortaya çıkar; her sayı, üstündeki iki sayının toplamıdır:
\[\begin{array}{ccccccccc} & & & & 1 & & & & \\ & & & 1 & & 1 & & & \\ & & 1 & & 2 & & 1 & & \\ & 1 & & 3 & & 3 & & 1 & \\ 1 & & 4 & & 6 & & 4 & & 1 \end{array}\]
Bu “üstündeki ikisinin toplamı” kuralı, binom teoreminin ispatındaki temel adımdır.
Lemma 9.1 (Pascal Özdeşliği) \(n \in \mathbb{N}\) ve \(1 \le k \le n\) için
\[\binom{n}{k-1} + \binom{n}{k} = \binom{n+1}{k}.\]
İspat
Faktöriyelin özyineli tanımıyla \(k! = k \cdot (k-1)!\) ve \((n - k + 1)! = (n - k + 1) \cdot (n - k)!\)’dir (\(k = 1\) ve \(k = n\) hâllerinde bu eşitlikler \(1! = 1 \cdot 0!\) biçimini alır; iki yan da \(1\)’dir). Ortak paydaya getirelim:
\[\binom{n}{k-1} + \binom{n}{k} = \frac{n!}{(k-1)!\,(n-k+1)!} + \frac{n!}{k!\,(n-k)!} = \frac{n! \cdot k}{k!\,(n-k+1)!} + \frac{n! \cdot (n-k+1)}{k!\,(n-k+1)!}.\]
Payları toplayınca \(n!\,\big(k + (n - k + 1)\big) = n!\,(n+1) = (n+1)!\) olur; dolayısıyla toplam
\[\frac{(n+1)!}{k!\,\big((n+1)-k\big)!} = \binom{n+1}{k}.\]
\(\blacksquare\)
Teorem 9.6 (Binom Teoremi) \(a, b \in \mathbb{R}\) ve \(n \in \mathbb{N}\) için
\[(a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{\,n-k} b^{\,k} = a^n + \binom{n}{1} a^{n-1} b + \binom{n}{2} a^{n-2} b^2 + \cdots + \binom{n}{n-1} a\, b^{n-1} + b^n.\]
Burada \(a^0\) ve \(b^0\) çarpanları, \(a\) ya da \(b\) sıfır olsa bile \(1\) olarak okunur; toplam da \(k = 0\)’dan başladığı için Tanım 9.3 (3)’ün \(k = 0\) terimi eklenmiş biçimidir.
İspat
\(n\) üzerinden tümevarım.
Temel adım. \(n = 1\): sağ taraf \(\binom{1}{0} a + \binom{1}{1} b = a + b = (a+b)^1\).
Tümevarım adımı. Eşitlik \(n = k\) için doğru olsun. Kuvvetin tanımı ve dağılma aksiyomuyla
\[(a+b)^{k+1} = (a+b)^k (a+b) = \left(\sum_{j=0}^{k} \binom{k}{j} a^{k-j} b^{j}\right) a + \left(\sum_{j=0}^{k} \binom{k}{j} a^{k-j} b^{j}\right) b = \sum_{j=0}^{k} \binom{k}{j} a^{k+1-j} b^{j} + \sum_{j=0}^{k} \binom{k}{j} a^{k-j} b^{j+1}.\]
İkinci toplamda \(j + 1 = i\) diyerek indisi kaydıralım; \(j\), \(0\)’dan \(k\)’ya giderken \(i\), \(1\)’den \(k+1\)’e gider:
\[\sum_{j=0}^{k} \binom{k}{j} a^{k-j} b^{j+1} = \sum_{i=1}^{k+1} \binom{k}{i-1} a^{k+1-i} b^{i}.\]
Şimdi iki toplamı, ortak \(a^{k+1-i} b^{i}\) terimlerine göre birleştirelim. Birinci toplamın \(i = 0\) terimi \(\binom{k}{0} a^{k+1} = a^{k+1}\), ikincinin \(i = k+1\) terimi \(\binom{k}{k} b^{k+1} = b^{k+1}\) tektir; \(1 \le i \le k\) için iki toplamdan birer terim gelir:
\[(a+b)^{k+1} = a^{k+1} + \sum_{i=1}^{k} \left[\binom{k}{i} + \binom{k}{i-1}\right] a^{k+1-i} b^{i} + b^{k+1}.\]
Lemma 9.1 ile köşeli parantez \(\binom{k+1}{i}\)’dir; ayrıca \(a^{k+1} = \binom{k+1}{0} a^{k+1} b^0\) ve \(b^{k+1} = \binom{k+1}{k+1} a^0 b^{k+1}\) yazılabilir. Böylece
\[(a+b)^{k+1} = \sum_{i=0}^{k+1} \binom{k+1}{i} a^{k+1-i} b^{i},\]
yani eşitlik \(n = k + 1\) için doğrudur.
\(\blacksquare\)
Örnek 9.9 (Binom Teoreminin Uygulamaları)
\((a + b)^4\) açılımını yazınız.
Her \(n \in \mathbb{N}\) için \(\displaystyle\sum_{k=0}^{n} \binom{n}{k} = 2^n\) ve \(\displaystyle\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0\) olduğunu gösteriniz.
\(x \ge 0\) için Bernoulli eşitsizliğini binom teoreminden elde ediniz.
Çözüm
a) Pascal üçgeninin beşinci satırı \(1, 4, 6, 4, 1\) olduğundan
\[(a+b)^4 = a^4 + 4a^3 b + 6a^2 b^2 + 4ab^3 + b^4.\]
b) Teorem 9.6 içinde \(a = b = 1\) alınca \((1+1)^n = \sum_{k=0}^{n} \binom{n}{k} \cdot 1 \cdot 1\), yani \(2^n = \sum_{k=0}^{n} \binom{n}{k}\). \(a = 1\), \(b = -1\) alınca \((1 + (-1))^n = 0^n = 0\) (çünkü \(n \ge 1\)) ve sağ taraf \(\sum_{k=0}^{n} \binom{n}{k} (-1)^k\) olur.
c) \(a = 1\), \(b = x \ge 0\) alalım: \((1+x)^n = 1 + nx + \sum_{k=2}^{n} \binom{n}{k} x^k\) (\(n = 1\) için son toplam yoktur). Binom katsayıları pozitif (alıştırma (d)) ve \(x^k \ge 0\) olduğundan son toplam negatif değildir; dolayısıyla \((1+x)^n \ge 1 + nx\).
\(\blacksquare\)
9.8 Genel Üçgen Eşitsizliği
Bölüm 8’de ertelediğimiz ispatı artık yapabiliriz.
Teorem 9.7 (Sonlu Toplamlar İçin Üçgen Eşitsizliği) \(n \in \mathbb{N}\) ve \(a_1, a_2, \dots, a_n \in \mathbb{R}\) olsun.
- \(\displaystyle \left|\sum_{k=1}^{n} a_k\right| \le \sum_{k=1}^{n} |a_k|\), yani \(|a_1 + a_2 + \cdots + a_n| \le |a_1| + |a_2| + \cdots + |a_n|\).
- \(\displaystyle \left|\prod_{k=1}^{n} a_k\right| = \prod_{k=1}^{n} |a_k|\); özel olarak her \(a \in \mathbb{R}\) için \(|a^n| = |a|^n\).
İspat
Madde (1). \(n\) üzerinden tümevarım. \(n = 1\) için iki taraf da \(|a_1|\)’dir. Eşitsizlik \(n = k\) için (her \(k\) terimli toplam için) doğru olsun ve \(a_1, \dots, a_{k+1}\) verilsin. Toplam sembolünün özyineli tanımı, Teorem 8.2 ve tümevarım hipoteziyle
\[\left|\sum_{i=1}^{k+1} a_i\right| = \left|\left(\sum_{i=1}^{k} a_i\right) + a_{k+1}\right| \le \left|\sum_{i=1}^{k} a_i\right| + |a_{k+1}| \le \sum_{i=1}^{k} |a_i| + |a_{k+1}| = \sum_{i=1}^{k+1} |a_i|.\]
Madde (2). Aynı tümevarım, bu kez Teorem 8.1 (5) ile:
\[\left|\prod_{i=1}^{k+1} a_i\right| = \left|\left(\prod_{i=1}^{k} a_i\right) \cdot a_{k+1}\right| = \left|\prod_{i=1}^{k} a_i\right| \cdot |a_{k+1}| = \left(\prod_{i=1}^{k} |a_i|\right) |a_{k+1}| = \prod_{i=1}^{k+1} |a_i|.\]
Bütün \(a_i\)’ler \(a\)’ya eşit alınırsa \(|a^n| = |a|^n\) çıkar.
\(\blacksquare\)
Bu teorem sayesinde sonlu toplamların büyüklüğünü terim terim sınırlayabileceğiz; seriler ve kısmi toplamlar söz konusu olduğunda vazgeçilmez olacaktır.
9.9 Alıştırmalar
Alıştırma 9.1 (Tümevarım Alıştırmaları)
Her \(n \in \mathbb{N}\) için \(1^2 + 2^2 + \cdots + n^2 = \dfrac{n(n+1)(2n+1)}{6}\) olduğunu gösteriniz.
Her \(n \in \mathbb{N}\) için \(\dfrac{1}{1 \cdot 2} + \dfrac{1}{2 \cdot 3} + \cdots + \dfrac{1}{n(n+1)} = \dfrac{n}{n+1}\) olduğunu gösteriniz.
\(n \ge 4\) olan her \(n \in \mathbb{N}\) için \(2^n \ge n^2\) olduğunu gösteriniz.
Her \(n \in \mathbb{N}\) ve \(k \in \{0, 1, \dots, n\}\) için \(\dbinom{n}{k} \in \mathbb{N}\) olduğunu gösteriniz.
İyi sıralama ilkesini (Teorem 9.2) kullanarak tümevarım ilkesinin önerme biçimini ispatlayınız: \(P(1)\) doğru ve her \(k\) için \(P(k) \Rightarrow P(k+1)\) ise her \(n \in \mathbb{N}\) için \(P(n)\) doğrudur.
Çözüm
a) \(n = 1\): sol taraf \(1\), sağ taraf \(\frac{1 \cdot 2 \cdot 3}{6} = 1\). Tümevarım adımı: eşitlik \(k\) için doğruysa
\[1^2 + \cdots + k^2 + (k+1)^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2 = \frac{(k+1)\big[k(2k+1) + 6(k+1)\big]}{6} = \frac{(k+1)(2k^2 + 7k + 6)}{6}.\]
\(2k^2 + 7k + 6 = (k+2)(2k+3)\) olduğundan sağ taraf \(\frac{(k+1)(k+2)(2k+3)}{6}\), yani formülün \(n = k+1\) hâlidir.
b) \(n = 1\): \(\frac{1}{1 \cdot 2} = \frac{1}{2} = \frac{1}{1+1}\). Tümevarım adımı: hipotezle
\[\frac{1}{1 \cdot 2} + \cdots + \frac{1}{k(k+1)} + \frac{1}{(k+1)(k+2)} = \frac{k}{k+1} + \frac{1}{(k+1)(k+2)} = \frac{k(k+2) + 1}{(k+1)(k+2)} = \frac{(k+1)^2}{(k+1)(k+2)} = \frac{k+1}{k+2}.\]
Bu, formülün \(n = k + 1\) hâlidir.
c) Teorem 9.3 ile \(n_0 = 4\)’ten başlayalım. Temel adım: \(2^4 = 16 = 4^2\). Tümevarım adımı: \(k \ge 4\) ve \(2^k \ge k^2\) olsun. O zaman \(2^{k+1} = 2 \cdot 2^k \ge 2k^2 = k^2 + k^2\). \(k \ge 4 \ge 3\) olduğundan Örnek 9.7 ile \(k^2 > 2k + 1\); dolayısıyla
\[2^{k+1} \ge k^2 + k^2 > k^2 + 2k + 1 = (k+1)^2.\]
d) \(n\) üzerinden tümevarım; \(P(n)\): “her \(k \in \{0, \dots, n\}\) için \(\binom{n}{k} \in \mathbb{N}\)”. \(n = 1\): \(\binom{1}{0} = \binom{1}{1} = 1 \in \mathbb{N}\). \(P(n)\) doğru olsun. \(\binom{n+1}{0} = \binom{n+1}{n+1} = 1 \in \mathbb{N}\); \(1 \le k \le n\) için Lemma 9.1 ile \(\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}\), hipotezle iki toplanan da doğal sayıdır ve Önerme 9.2 ile toplamları da doğal sayıdır. \(P(n+1)\) doğrudur.
e) \(P(1)\) doğru ve her \(k\) için \(P(k) \Rightarrow P(k+1)\) olsun. \(S = \{n \in \mathbb{N} : P(n) \text{ yanlış}\}\) kümesini alalım ve \(S \ne \varnothing\) varsayalım. Teorem 9.2 ile \(S\)’nin en küçük elemanı \(m\) vardır. \(P(1)\) doğru olduğundan \(m \ne 1\); Önerme 9.3 (2) ile \(m - 1 \in \mathbb{N}\). \(m - 1 < m\) ve \(m\) en küçük olduğundan \(m - 1 \notin S\), yani \(P(m-1)\) doğrudur. Varsayımla \(P((m-1)+1) = P(m)\) doğrudur; bu \(m \in S\) ile çelişir. Demek ki \(S = \varnothing\): her \(n\) için \(P(n)\) doğrudur. (Bu, iyi sıralama ilkesinin tümevarım ilkesine denk olduğunu gösterir; diğer yön Teorem 9.2’nın ispatıdır.)
\(\blacksquare\)
Doğal sayılar artık elimizde ve “her \(n\) için” tümcelerini ispatlayabiliyoruz. Ama şu ana kadarki aksiyomlar reel sayıları rasyonel sayılardan ayırt edemez; hâlâ \(\sqrt{2}\)’nin var olduğunu bile bilmiyoruz. Eksik olan son aksiyom, sayı doğrusunda “boşluk” bulunmadığını söyleyen tamlık aksiyomudur: Üst Sınır, Supremum ve Tamlık Aksiyomu.