1 Tümevarım ve İyi Sıralama Prensibi
Sayılar teorisi, tam sayıların yapısını inceler. Bu yapının üzerine kurulduğu temel, doğal sayıların sıralanışıdır: her doğal sayıdan sonra bir sonraki gelir ve geriye doğru sonsuza kadar inilemez. Bu bölümde bu basit gözlemin iki farklı yüzü olan tümevarım ile iyi sıralama prensibini tanıtacak, dersin geri kalanında sürekli kullanacağımız ispat tekniklerini kuracağız.
1.1 Notasyon
Ders boyunca aşağıdaki gösterimleri kullanacağız.
| Sembol | Küme | Elemanları |
|---|---|---|
| \(\mathbb{N}\) | Doğal sayılar | \(1, 2, 3, \dots\) |
| \(\mathbb{Z}\) | Tam sayılar | \(\dots, -2, -1, 0, 1, 2, \dots\) |
| \(\mathbb{Q}\) | Rasyonel sayılar | \(\dfrac{a}{b}\) biçimindeki sayılar \((a \in \mathbb{Z},\ b \in \mathbb{N})\) |
Bu notlarda \(\mathbb{N}\) kümesi \(1\)’den başlar; \(0\) doğal sayı sayılmaz. Sıfırı da katmak istediğimizde \(\mathbb{N} \cup \{0\}\) yazacağız.
1.2 Tümevarım Yöntemi
Sonsuz sayıda önermeyi tek tek doğrulamak mümkün değildir. Tümevarım, bu sonsuz doğrulamayı iki adımlık sonlu bir işe indirger: ilk önermeyi doğrularız, sonra da her önermenin bir sonrakini doğurduğunu gösteririz.
Teorem 1.1 (Tümevarım İlkesi) Her \(n \in \mathbb{N}\) için \(p(n)\) bir önerme olsun. Eğer
- \(p(1)\) doğruysa (yani önerme \(n = 1\) için doğruysa),
- her \(k \in \mathbb{N}\) için, \(p(k)\) doğru olduğunda \(p(k+1)\) de doğru oluyorsa,
o hâlde her \(n \in \mathbb{N}\) için \(p(n)\) önermesi doğrudur.
Birinci koşula başlangıç adımı, ikincisine tümevarım adımı denir. Tümevarım adımında \(p(k)\)’nin doğruluğunu kabul ederiz; bu kabule tümevarım hipotezi adı verilir.
Domino taşlarını düşünün. Başlangıç adımı ilk taşı devirir; tümevarım adımı ise “devrilen her taş bir sonrakini devirir” güvencesini verir. İkisi birlikte bütün taşların devrildiğini söyler.
İki koşuldan biri olmadan sonuç çökebilir: “\(n\) sayısı \(n+1\)’e eşittir” önermesi tümevarım adımını sağlar (\(n = n+1\) ise \(n+1 = n+2\)’dir) ama başlangıç adımı sağlanmadığından hiçbir \(n\) için doğru değildir.
Örnek 1.1 (İlk \(n\) Doğal Sayının Toplamı) Her \(n \in \mathbb{N}\) için
\[\sum_{m=1}^{n} m = 1 + 2 + \cdots + n = \frac{n(n+1)}{2}\]
eşitliğini tümevarımla ispatlayınız.
Çözüm
Her \(n\) pozitif tam sayısı için \(A_n\) ve \(B_n\) sayılarını
\[A_n := 1 + 2 + \cdots + n, \qquad B_n := \frac{n(n+1)}{2}\]
biçiminde tanımlayalım. Her \(n \in \mathbb{N}\) için \(A_n = B_n\) olduğunu göstermeliyiz.
Başlangıç adımı (\(n = 1\)).
\[A_1 = 1, \qquad B_1 = \frac{1 \cdot 2}{2} = 1\]
olduğundan \(A_1 = B_1\)’dir; önerme \(n = 1\) için doğrudur.
Tümevarım adımı. \(k \in \mathbb{N}\) olsun ve önermenin \(n = k\) için doğru olduğunu, yani
\[A_k = B_k = \frac{k(k+1)}{2}\]
eşitliğini varsayalım. \(n = k+1\) için de doğru olduğunu gösterelim. Tanım gereği \(A_{k+1} = A_k + (k+1)\)’dir. Tümevarım hipotezini kullanalım:
\[ \begin{aligned} A_{k+1} &= A_k + (k+1) \\ &= \frac{k(k+1)}{2} + (k+1) \\ &= (k+1)\left( \frac{k}{2} + 1 \right) \\ &= (k+1) \cdot \frac{k+2}{2} \\ &= \frac{(k+1)\big((k+1)+1\big)}{2} = B_{k+1} \end{aligned} \]
Böylece \(A_{k+1} = B_{k+1}\) elde edildi. Tümevarım ilkesi gereği her \(n \in \mathbb{N}\) için eşitlik doğrudur.
\(\blacksquare\)
Aynı sonuç tümevarım kullanmadan da görülebilir. Toplamı bir kez düz, bir kez ters yazıp alt alta toplayalım:
\[ \begin{aligned} S &= 1 + 2 + \cdots + (n-1) + n \\ S &= n + (n-1) + \cdots + 2 + 1 \\ \hline 2S &= \underbrace{(n+1) + (n+1) + \cdots + (n+1)}_{n \text{ tane}} = n(n+1) \end{aligned} \]
Buradan \(S = n(n+1)/2\) bulunur. Tümevarım bir formülü doğrulamak için birebir yöntemdir; ancak formülü keşfetmek için çoğu zaman böyle bir fikre ihtiyaç duyarız.
1.3 Tümevarımla Tanım Verme
Tümevarım yalnızca ispat aracı değildir; bir kavramı adım adım tanımlamak için de kullanılır. Bir nesneyi \(n = 1\) için tanımlar, sonra \(n\)’inci adımdan \((n+1)\)’inci adımı üretecek bir kural veririz.
Tanım 1.1 (Faktöriyel) Her \(n \in \mathbb{N}\) için \(n!\) sembolü tümevarımla şu şekilde tanımlanır:
- \(1! = 1\),
- her \(n \in \mathbb{N}\) için \((n+1)! = n! \cdot (n+1)\).
Bu kural \(n!\) sayısını \(1 \cdot 2 \cdots n\) çarpımı olarak üretir: \(2! = 2\), \(3! = 6\), \(4! = 24\) ve benzeri.
Faktöriyelin ileride binom katsayılarıyla birlikte kullanılabilmesi için tanım \(n = 0\) noktasına da genişletilir ve
\[0! = 1\]
kabul edilir. Bu keyfî bir seçim değildir: \((n+1)! = n! \cdot (n+1)\) kuralının \(n = 0\) için de geçerli olması, yani \(1! = 0! \cdot 1\) eşitliğinin bozulmaması isteniyorsa \(0!\) mecburen \(1\) olmalıdır.
1.4 Güçlü Tümevarım
Bazen \(p(k+1)\)’i ispatlamak için yalnızca \(p(k)\) yetmez; daha küçük indislerin hepsine ihtiyaç duyarız. Örneğin bir sayıyı çarpanlarına ayırırken \(n = a \cdot b\) yazarız ve \(a\) ile \(b\) hakkındaki bilgiye başvururuz — bunlar \(n-1\) olmak zorunda değildir. Tümevarımın aşağıdaki güçlendirilmiş biçimi tam olarak bu ihtiyacı karşılar.
Teorem 1.2 (Güçlü Tümevarım) Her \(n \in \mathbb{N}\) için \(p(n)\) bir önerme olsun. Eğer
- \(p(1)\) doğruysa,
- her \(k \in \mathbb{N}\) için, \(p(1), p(2), \dots, p(k)\) önermelerinin hepsi doğru olduğunda \(p(k+1)\) de doğru oluyorsa,
o hâlde her \(n \in \mathbb{N}\) için \(p(n)\) önermesi doğrudur.
İki ilke arasındaki tek fark tümevarım hipotezinin genişliğidir: sıradan tümevarımda yalnızca bir önceki adımı, güçlü tümevarımda ise o ana kadarki bütün adımları kullanma hakkımız vardır. Bu, ispat gücünü artırır ama hiçbir şey kaybettirmez; çünkü daha geniş bir hipotezi kullanmak zorunda değilizdir.
Örnek 1.2 (Bir Dizi Eşitsizliği) Aşağıdaki gibi tanımlanan diziyi göz önüne alalım:
\[a_1 = 1, \qquad a_2 = 3, \qquad a_n = a_{n-1} + a_{n-2} \quad (n \geq 3)\]
Her \(n\) pozitif tam sayısı için
\[a_n < \left( \frac{7}{4} \right)^{n}\]
olduğunu gösteriniz. (Bu diziye Lucas dizisi denir.)
Çözüm
Dizinin \(n\)’inci terimi kendisinden önceki iki terime bağlı olduğundan güçlü tümevarım kullanacağız. Bu nedenle başlangıç adımında iki terimi birden doğrulamamız gerekir.
Başlangıç adımları.
\[a_1 = 1 < \frac{7}{4}, \qquad a_2 = 3 < \left( \frac{7}{4} \right)^{2} = \frac{49}{16} = 3{,}0625\]
Her iki eşitsizlik de sağlanıyor. (İkincisinin ne kadar dar bir farkla sağlandığına dikkat ediniz; \(7/4\) yerine daha küçük bir taban seçilseydi iddia bozulurdu.)
Tümevarım adımı. \(k \geq 2\) olsun ve iddianın \(n = 1, 2, \dots, k\) değerlerinin hepsi için doğru olduğunu varsayalım. \(n = k+1\) için gösterelim. Dizinin tanımı gereği
\[a_{k+1} = a_k + a_{k-1}\]
yazılır. Tümevarım hipotezi hem \(k\) hem de \(k-1\) indisi için kullanılabilir:
\[a_{k+1} < \left( \frac{7}{4} \right)^{k} + \left( \frac{7}{4} \right)^{k-1}\]
Sağ taraftaki ortak çarpanı ayıralım:
\[\left( \frac{7}{4} \right)^{k} + \left( \frac{7}{4} \right)^{k-1} = \left( \frac{7}{4} \right)^{k-1} \left( \frac{7}{4} + 1 \right) = \left( \frac{7}{4} \right)^{k-1} \cdot \frac{11}{4}\]
Şimdi kilit gözlem şudur:
\[\frac{11}{4} = 2{,}75 \ < \ \frac{49}{16} = 3{,}0625 = \left( \frac{7}{4} \right)^{2}\]
Bu eşitsizliği yukarıda yerine koyarsak
\[a_{k+1} < \left( \frac{7}{4} \right)^{k-1} \cdot \left( \frac{7}{4} \right)^{2} = \left( \frac{7}{4} \right)^{k+1}\]
elde edilir. Güçlü tümevarım ilkesi gereği eşitsizlik her \(n \in \mathbb{N}\) için doğrudur.
\(\blacksquare\)
1.5 İyi Sıralama Prensibi
Tümevarımın bir başka yüzü, doğal sayıların hiç boş olmayan her parçasının bir “en küçüğü” bulunduğu gözlemidir. Sayılar teorisinde en sık kullanacağımız araçlardan biri budur: bir şeyin var olduğunu göstermek için, uygun bir kümenin en küçük elemanını seçeriz.
Teorem 1.3 (İyi Sıralama Prensibi) Doğal sayıların boş kümeden farklı her alt kümesinin bir en küçük elemanı vardır.
İspat
\(\emptyset \neq A \subseteq \mathbb{N}\) olsun. \(A\) kümesinin en küçük elemanının olmadığını varsayıp bir çelişki arayalım.
\(A\) kümesinin \(\mathbb{N}\) içindeki tümleyeni \(B\) olsun:
\[B = \{ n \in \mathbb{N} : n \notin A \}\]
Her \(n \in \mathbb{N}\) için \(p(n)\) önermesini “\(n \in B\)” biçiminde tanımlayalım ve \(p(n)\)’in her \(n\) için doğru olduğunu güçlü tümevarımla gösterelim.
Başlangıç adımı. \(1 \in B\) midir? Eğer \(1 \notin B\) olsaydı \(1 \in A\) olurdu. Ama \(1\), \(\mathbb{N}\) kümesinin en küçük elemanıdır; dolayısıyla \(A\)’nın da en küçük elemanı olurdu. Bu, \(A\)’nın en küçük elemanının olmadığı varsayımıyla çelişir. O hâlde \(1 \in B\)’dir.
Tümevarım adımı. \(k \in \mathbb{N}\) olsun ve \(1, 2, \dots, k\) sayılarının hepsinin \(B\) içinde olduğunu varsayalım; yani bu sayıların hiçbiri \(A\)’da değildir. \(k+1 \in B\) olduğunu gösterelim.
Aksini varsayalım: \(k+1 \in A\) olsun. \(A\) kümesinde \(k+1\)’den küçük hiçbir eleman yoktur, çünkü \(1, \dots, k\) sayılarının hepsi \(B\)’dedir. O hâlde \(k+1\), \(A\) kümesinin en küçük elemanı olur — yine çelişki. Demek ki \(k+1 \in B\)’dir.
Güçlü tümevarım ilkesi gereği her \(n \in \mathbb{N}\) için \(n \in B\)’dir; yani \(B = \mathbb{N}\) ve dolayısıyla \(A = \emptyset\)’dir. Bu ise \(A \neq \emptyset\) kabulümüzle çelişir.
Çelişki, “\(A\)’nın en küçük elemanı yoktur” varsayımından doğmuştur. O hâlde \(A\) kümesinin bir en küçük elemanı vardır.
\(\blacksquare\)
Yukarıda iyi sıralama prensibini tümevarımdan çıkardık. Ters yönde de gidilebilir: iyi sıralama prensibi kabul edilirse tümevarım ilkesi ispatlanabilir. Bunun için tümevarımın iki koşulunu sağlayan bir \(p(n)\) önermesi verildiğinde, \(p(n)\)’in yanlış olduğu \(n\)’lerin kümesine bakılır; bu küme boş değilse en küçük elemanı \(m\) olsun. \(p(1)\) doğru olduğundan \(m \neq 1\), dolayısıyla \(m - 1 \in \mathbb{N}\)’dir ve \(m\)’nin seçimi gereği \(p(m-1)\) doğrudur. Ama tümevarım adımı \(p(m)\)’in de doğru olmasını gerektirir — çelişki.
Yani iki ilke birbirine denktir; hangisinin kullanılacağı yalnızca kolaylık meselesidir.
Sonuç 1.1 (Sıfırın Katılması) \(\mathbb{N} \cup \{0\}\) kümesinin boştan farklı her alt kümesinin bir en küçük elemanı vardır.
Bu sonuç doğrudan iyi sıralama prensibinden gelir: eğer küme \(0\) içeriyorsa en küçük eleman zaten \(0\)’dır; içermiyorsa küme \(\mathbb{N}\)’nin bir alt kümesidir ve önceki teorem uygulanır. Bu küçük genişletmeye ihtiyaç duyacağız, çünkü bölme algoritmasında karşılaşacağımız kalanlar \(0\) olabilir.
1.6 Arşimed Prensibi
İyi sıralama prensibinin ilk uygulaması, “yeterince çok kez toplarsak her sayıyı geçeriz” biçimindeki sezgiyi kesinleştirir.
Teorem 1.4 (Arşimed Prensibi) Her \(a\) ve \(b\) pozitif tam sayısı için
\[na \geq b\]
olacak biçimde en az bir \(n\) doğal sayısı vardır.
İspat
Teoremin doğru olmadığını varsayalım. Bu durumda her \(n \in \mathbb{N}\) için
\[na < b\]
olur. O hâlde her \(n \in \mathbb{N}\) için \(b - na\) sayısı pozitiftir ve
\[S = \{ b - na : n \in \mathbb{N} \}\]
kümesi doğal sayıların bir alt kümesidir. Ayrıca \(n = 1\) alındığında \(b - a \in S\) olduğundan \(S\) boş değildir.
İyi sıralama prensibine göre \(S\) kümesinin bir en küçük elemanı vardır; buna \(m\) diyelim. \(m \in S\) olduğundan
\[m = b - ka\]
olacak biçimde bir \(k \in \mathbb{N}\) vardır. Şimdi \(k+1\) de bir doğal sayı olduğundan \(b - (k+1)a\) sayısı da \(S\) kümesine aittir. Oysa \(a > 0\) olduğundan
\[b - (k+1)a = (b - ka) - a = m - a < m\]
olur; yani \(S\) kümesinde \(m\)’den küçük bir eleman bulduk. Bu, \(m\)’nin \(S\)’nin en küçük elemanı olmasıyla çelişir.
O hâlde varsayımımız yanlıştır ve \(na \geq b\) olacak biçimde bir \(n\) doğal sayısı vardır.
\(\blacksquare\)
1.7 Tümevarımla Çözülmüş Örnekler
Aşağıdaki örnekler, tümevarımın toplam formüllerinde nasıl kullanıldığını gösterir. Hepsinde izlenen şablon aynıdır: başlangıç adımını doğrula, tümevarım hipotezini yaz, \((k+1)\)’inci terimi ekleyip ortak çarpan düzenlemesiyle hedef formüle ulaş.
Örnek 1.3 (İlk \(n\) Karenin Toplamı) Her \(n \in \mathbb{N}\) için
\[\sum_{m=1}^{n} m^2 = 1^2 + 2^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}\]
eşitliğini tümevarımla ispatlayınız.
Çözüm
Başlangıç adımı (\(n = 1\)). Sol taraf \(1^2 = 1\)’dir. Sağ taraf
\[\frac{1 \cdot 2 \cdot 3}{6} = 1\]
olduğundan eşitlik \(n = 1\) için doğrudur.
Tümevarım adımı. Eşitliğin \(n = k\) için doğru olduğunu varsayalım:
\[1^2 + 2^2 + \cdots + k^2 = \frac{k(k+1)(2k+1)}{6}\]
Her iki tarafa \((k+1)^2\) ekleyelim:
\[ \begin{aligned} 1^2 + \cdots + k^2 + (k+1)^2 &= \frac{k(k+1)(2k+1)}{6} + (k+1)^2 \\[4pt] &= \frac{k(k+1)(2k+1) + 6(k+1)^2}{6} \\[4pt] &= \frac{(k+1)\big[ k(2k+1) + 6(k+1) \big]}{6} \\[4pt] &= \frac{(k+1)\big( 2k^2 + 7k + 6 \big)}{6} \end{aligned} \]
Köşeli parantez içindeki ifadeyi çarpanlarına ayıralım. \(2k^2 + 7k + 6\) ifadesinin kökleri \(k = -2\) ve \(k = -3/2\) olduğundan
\[2k^2 + 7k + 6 = (k+2)(2k+3)\]
yazılır. Böylece
\[1^2 + \cdots + (k+1)^2 = \frac{(k+1)(k+2)(2k+3)}{6} = \frac{(k+1)\big((k+1)+1\big)\big(2(k+1)+1\big)}{6}\]
bulunur; bu tam olarak formülün \(n = k+1\) hâlidir.
\(\blacksquare\)
Örnek 1.4 (İlk \(n\) Tek Sayının Toplamı) Her \(n \in \mathbb{N}\) için
\[\sum_{m=1}^{n} (2m - 1) = 1 + 3 + \cdots + (2n - 1) = n^2\]
eşitliğini tümevarımla ispatlayınız.
Çözüm
Başlangıç adımı (\(n = 1\)). Sol taraf \(2 \cdot 1 - 1 = 1\), sağ taraf \(1^2 = 1\)’dir.
Tümevarım adımı. Eşitliğin \(n = k\) için doğru olduğunu, yani
\[1 + 3 + \cdots + (2k - 1) = k^2\]
olduğunu varsayalım. Sıradaki tek sayı \(2(k+1) - 1 = 2k + 1\)’dir; her iki tarafa ekleyelim:
\[1 + 3 + \cdots + (2k-1) + (2k+1) = k^2 + 2k + 1 = (k+1)^2\]
Bu, formülün \(n = k+1\) hâlidir.
\(\blacksquare\)
Son eşitlik resimle de görülebilir: \(n \times n\) boyutunda bir kareyi, sol üst köşeden başlayarak “L” biçimindeki şeritlere ayırın. Şeritlerdeki birim kare sayıları sırasıyla \(1, 3, 5, \dots, 2n-1\) olur ve hepsinin toplamı karenin alanı olan \(n^2\)’ye eşittir.
Örnek 1.5 (Ardışık Çarpımların Toplamı) Her \(n \in \mathbb{N}\) için
\[\sum_{m=1}^{n} m(m+1) = 1 \cdot 2 + 2 \cdot 3 + \cdots + n(n+1) = \frac{n(n+1)(n+2)}{3}\]
eşitliğini tümevarımla ispatlayınız.
Çözüm
Başlangıç adımı (\(n = 1\)). Sol taraf \(1 \cdot 2 = 2\); sağ taraf
\[\frac{1 \cdot 2 \cdot 3}{3} = 2\]
olduğundan eşitlik sağlanır.
Tümevarım adımı. Eşitlik \(n = k\) için doğru olsun:
\[1 \cdot 2 + \cdots + k(k+1) = \frac{k(k+1)(k+2)}{3}\]
Her iki tarafa \((k+1)(k+2)\) ekleyelim:
\[ \begin{aligned} 1 \cdot 2 + \cdots + (k+1)(k+2) &= \frac{k(k+1)(k+2)}{3} + (k+1)(k+2) \\[4pt] &= (k+1)(k+2) \left( \frac{k}{3} + 1 \right) \\[4pt] &= (k+1)(k+2) \cdot \frac{k+3}{3} \\[4pt] &= \frac{(k+1)\big((k+1)+1\big)\big((k+1)+2\big)}{3} \end{aligned} \]
Böylece formül \(n = k+1\) için de doğrudur.
\(\blacksquare\)
Örnek 1.6 (İlk \(n\) Küpün Toplamı) Her \(n\) pozitif tam sayısı için
\[\sum_{i=1}^{n} i^3 = \left( \frac{n(n+1)}{2} \right)^{2}\]
olduğunu gösteriniz.
Çözüm
Başlangıç adımı (\(n = 1\)). Sol taraf \(1^3 = 1\); sağ taraf \(\left( \tfrac{1 \cdot 2}{2} \right)^2 = 1\)’dir.
Tümevarım adımı. Eşitlik \(n = k\) için doğru olsun:
\[1^3 + 2^3 + \cdots + k^3 = \left( \frac{k(k+1)}{2} \right)^{2} = \frac{k^2(k+1)^2}{4}\]
Her iki tarafa \((k+1)^3\) ekleyelim:
\[ \begin{aligned} 1^3 + \cdots + k^3 + (k+1)^3 &= \frac{k^2(k+1)^2}{4} + (k+1)^3 \\[4pt] &= (k+1)^2 \left( \frac{k^2}{4} + (k+1) \right) \\[4pt] &= (k+1)^2 \cdot \frac{k^2 + 4k + 4}{4} \\[4pt] &= \frac{(k+1)^2 (k+2)^2}{4} \\[4pt] &= \left( \frac{(k+1)\big((k+1)+1\big)}{2} \right)^{2} \end{aligned} \]
Böylece eşitlik \(n = k+1\) için de sağlanır.
\(\blacksquare\)
Örnek 1.7 (Kesirli Bir Toplam) Her \(n\) pozitif tam sayısı için
\[\sum_{i=1}^{n} \frac{i}{2^i} = 2 - \frac{n+2}{2^n}\]
olduğunu gösteriniz.
Çözüm
Başlangıç adımı (\(n = 1\)). Sol taraf \(\tfrac{1}{2}\); sağ taraf
\[2 - \frac{1+2}{2^1} = 2 - \frac{3}{2} = \frac{1}{2}\]
olduğundan eşitlik doğrudur.
Tümevarım adımı. Eşitlik \(n = k\) için doğru olsun:
\[\sum_{i=1}^{k} \frac{i}{2^i} = 2 - \frac{k+2}{2^k}\]
Her iki tarafa sıradaki terim olan \(\dfrac{k+1}{2^{k+1}}\)’i ekleyelim:
\[ \begin{aligned} \sum_{i=1}^{k+1} \frac{i}{2^i} &= 2 - \frac{k+2}{2^k} + \frac{k+1}{2^{k+1}} \\[4pt] &= 2 - \frac{2(k+2)}{2^{k+1}} + \frac{k+1}{2^{k+1}} \\[4pt] &= 2 - \frac{2k + 4 - k - 1}{2^{k+1}} \\[4pt] &= 2 - \frac{k+3}{2^{k+1}} \\[4pt] &= 2 - \frac{(k+1)+2}{2^{k+1}} \end{aligned} \]
Bu, formülün \(n = k+1\) hâlidir.
\(\blacksquare\)
\(n\) büyüdükçe \(\dfrac{n+2}{2^n}\) ifadesi sıfıra yaklaşır; çünkü payda üstel hızla, pay ise doğrusal hızla büyür. Dolayısıyla toplam \(2\) sayısına yaklaşır ama onu hiçbir zaman geçmez. Tümevarımla ispatladığımız kapalı formül, bu davranışı tek bakışta okumamızı sağlar.
1.8 Çalışma Problemleri
Alıştırma 1.1 (Tümevarımla Toplam Formülleri) Aşağıdaki eşitlikleri tümevarımla ispatlayınız.
a) \(\displaystyle \sum_{m=1}^{n} \frac{1}{m(m+1)} = \frac{n}{n+1}\)
b) \(\displaystyle \sum_{m=1}^{n} (2m-1)^2 = \frac{n(2n-1)(2n+1)}{3}\)
c) \(\displaystyle \sum_{m=1}^{n} m \cdot m! = (n+1)! - 1\)
d) \(\displaystyle \sum_{m=1}^{n} \frac{1}{2^m} = 1 - \frac{1}{2^n}\)
Alıştırma 1.2 (Bir Çarpanlara Ayırma Özdeşliği) Her \(x\) reel sayısı ve her \(n\) pozitif tam sayısı için
\[x^{n+1} - 1 = (x - 1)\left( x^{n} + x^{n-1} + \cdots + x + 1 \right)\]
eşitliğini tümevarımla ispatlayınız.
İpucu: Tümevarım adımında \(x^{n+2} - 1 = x \cdot (x^{n+1} - 1) + (x - 1)\) yazımından yararlanınız.
Alıştırma 1.3 (Üstel Büyüme) Her \(2 < n\) tam sayısı için
\[n + 1 < 2^n\]
olduğunu tümevarımla gösteriniz. (Bu eşitsizliği ileride, sözde-asal sayıların sonsuzluğunu ispatlarken kullanacağız.)
Alıştırma 1.4 (İyi Sıralama Prensibiyle Bir İspat) Boş kümeden farklı bir \(A \subseteq \mathbb{Z}\) kümesi alttan sınırlı olsun; yani her \(a \in A\) için \(c \leq a\) olacak biçimde bir \(c\) tam sayısı bulunsun. Bu durumda \(A\) kümesinin bir en küçük elemanı olduğunu gösteriniz.
İpucu: \(B = \{ a - c + 1 : a \in A \}\) kümesinin \(\mathbb{N}\) içinde kaldığını gözlemleyip iyi sıralama prensibini \(B\)’ye uygulayınız.