Tümevarım yöntemi bir açık önermenin tüm pozitif tam sayılar için doğru olduğunu göstermekte kullanılan bir ispat yöntemidir.
Bir \( p(n) \) açık önermesinin tüm pozitif tam sayılar için doğru olduğunu göstermek istediğimizi varsayalım.
Tümevarım yöntemine göre, aşağıdaki iki adımın doğru olduğu gösterildiğinde \( p(n) \) açık önermesinin her \( n \ge 1 \) tam sayısı için doğru olduğu gösterilmiş olur.
Tümevarım yöntemini, en sık kullanıldığı soru tiplerinden biri olan toplam formülleri örneği üzerinde gösterelim.
Bir \( p(n) \) açık önermesinin her \( n \) değeri için karşılık geldiği önermeler bir zincirin halkaları olarak düşünülebilir.
Buna göre tümevarım yönteminde amaç; başlangıç adımında zincirin ilk halkasının (\( p(1) \)) doğru olduğunu göstermek, tümevarım adımında zincirin herhangi bir noktasından seçilen bir halkanın (\( p(k) \)) doğru olduğu kabul edilirse sonraki halkanın da (\( p(k + 1) \)) doğru olduğunu göstermektir.
Önermenin bu iki durum için doğru olması tüm durumlar için doğru olduğunu gösterir.
Başlangıç adımındaki ilk durum \( n = 1 \) yerine 0 ya da farklı bir pozitif tam sayı olabilir.
Bazı ispatlarda tümevarım adımında \( p(k) \Rightarrow p(k + 1) \) koşullu önermesinin yerine \( p(k - 1) \Rightarrow p(k) \) önermesi de kullanılabilir.
Tümevarım yönteminin sık kullanıldığı diğer iki soru tipi olan bölünebilme ve eşitsizliklerle ilgili de birer örnek soru çözelim.
SORU 1:
Her \( n \ge 1 \) tam sayısı için aşağıdaki toplam formülünün doğru olduğunu gösterin.
\( 1^3 + 2^3 + 3^3 + \ldots + n^3 \) \( = (\dfrac{n(n + 1)}{2})^2 \)
Çözümü Göster
Verilen eşitliği bir \( p(n) \) açık önermesi şeklinde tanımlayalım ve doğruluğunu ispatlamak için tümevarım yöntemini kullanalım.
\( p(n): 1^3 + 2^3 + \ldots + n^3 = (\dfrac{n(n + 1)}{2})^2 \)
Başlangıç adımı: Önermenin \( n = 1 \) için doğru olduğunu gösterelim.
\( n = 1 \) için sayı dizisi tek bir terimden oluşur.
\( 1^3 \stackrel{?}{=} (\dfrac{1(1 + 1)}{2})^2 \)
\( 1 = 1 \)
Buna göre \( p(1) \) doğrudur.
Tümevarım adımı: \( k \ge 1 \) olmak üzere, önermenin \( n = k \) için doğru olduğunu kabul edelim ve \( n = k + 1 \) için de doğru olduğunu gösterelim.
\( p(k) \Rightarrow p(k + 1) \)
Tümevarım hipotezi: \( p(k) \) önermesinin doğru olduğunu kabul edelim.
\( 1^3 + 2^3 + \ldots + k^3 = (\dfrac{k(k + 1)}{2})^2 \)
\( p(k + 1) \) önermesinin doğru olduğunu gösterelim.
\( 1^3 + 2^3 + \ldots + (k + 1)^3 = \textcolor{red}{(\dfrac{(k + 1)(k + 2)}{2})^2} \)
Eşitliğin sol tarafında son terim dışındaki terimlerin toplamı \( p(k) \) toplam formülüne eşittir.
\( = (\dfrac{k(k + 1)}{2})^2 + (k + 1)^3 \)
İfadeyi düzenleyelim.
\( = \dfrac{k^2(k + 1)^2}{4} + (k + 1)^2(k + 1) \)
Terimleri \( (k + 1)^2 \) parantezine alalım.
\( = (k + 1)^2[\dfrac{k^2}{4} + (k + 1)] \)
\( = (k + 1)^2\dfrac{k^2 + 4k + 4}{4} \)
\( = \dfrac{(k + 1)^2(k + 2)^2}{4} \)
\( = \textcolor{red}{(\dfrac{(k + 1)(k + 2)}{2})^2} \)
\( p(k + 1) \) önermesindeki eşitliğin sağ tarafını elde etmiş olduk.
O halde \( p(k) \) doğru ise \( p(k + 1) \) de doğru olur.
Dolayısıyla, tümevarım yöntemine göre \( p(n) \) önermesi her \( n \ge 1 \) tam sayısı için doğrudur.
SORU 2:
Her \( n \ge 1 \) tam sayısı için aşağıdaki toplam formülünün doğru olduğunu gösterin.
\( 1 \cdot 1! + 2 \cdot 2! + 3 \cdot 3! + \ldots + n \cdot n! \) \( = (n + 1)! - 1 \)
Çözümü Göster
Verilen eşitliği bir \( p(n) \) açık önermesi şeklinde tanımlayalım ve doğruluğunu ispatlamak için tümevarım yöntemini kullanalım.
\( p(n): 1 \cdot 1! + 2 \cdot 2! + \ldots + n \cdot n! = (n + 1)! - 1 \)
Başlangıç adımı: Önermenin \( n = 1 \) için doğru olduğunu gösterelim.
\( n = 1 \) için sayı dizisi tek bir terimden oluşur.
\( 1 \cdot 1! \stackrel{?}{=} (1 + 1)! - 1 \)
\( 1 = 1 \)
Buna göre \( p(1) \) doğrudur.
Tümevarım adımı: \( k \ge 1 \) olmak üzere, önermenin \( n = k \) için doğru olduğunu kabul edelim ve \( n = k + 1 \) için de doğru olduğunu gösterelim.
\( p(k) \Rightarrow p(k + 1) \)
Tümevarım hipotezi: \( p(k) \) önermesinin doğru olduğunu kabul edelim.
\( 1 \cdot 1! + 2 \cdot 2! + \ldots + k \cdot k! = (k + 1)! - 1 \)
\( p(k + 1) \) önermesinin doğru olduğunu gösterelim.
\( 1 \cdot 1! + 2 \cdot 2! + \ldots + (k + 1) \cdot (k + 1)! = \textcolor{red}{(k + 2)! - 1} \)
Eşitliğin sol tarafında son terim dışındaki terimlerin toplamı \( p(k) \) toplam formülüne eşittir.
\( = (k + 1)! - 1 + (k + 1) \cdot (k + 1)! \)
1. ve 3. terimleri \( (k + 1)! \) parantezine alalım.
\( = (k + 1)![1 + (k + 1)] - 1 \)
\( = (k + 1)!(k + 2) - 1 \)
\( = \textcolor{red}{(k + 2)! - 1} \)
\( p(k + 1) \) önermesindeki eşitliğin sağ tarafını elde etmiş olduk.
O halde \( p(k) \) doğru ise \( p(k + 1) \) de doğru olur.
Dolayısıyla, tümevarım yöntemine göre \( p(n) \) önermesi her \( n \ge 1 \) tam sayısı için doğrudur.
SORU 3:
Her \( n \ge 2 \) tam sayısı için \( n^3 - n \) ifadesinin 6'ya tam bölündüğünü gösterin.
Çözümü Göster
Verilen ifadeyi bir \( p(n) \) açık önermesi şeklinde tanımlayalım ve doğruluğunu ispatlamak için tümevarım yöntemini kullanalım.
\( p(n): 6 \mid n^3 - n \)
Başlangıç adımı: Önermenin \( n = 2 \) için doğru olduğunu gösterelim.
\( 2^3 - 2 = 6 \)
\( 6 \mid 6 \)
Buna göre \( p(2) \) doğrudur.
Tümevarım adımı: \( k \ge 2 \) olmak üzere, önermenin \( n = k \) için doğru olduğunu kabul edelim ve \( n = k + 1 \) için de doğru olduğunu gösterelim.
\( p(k) \Rightarrow p(k + 1) \)
Tümevarım hipotezi: \( p(k) \) önermesinin doğru olduğunu kabul edelim.
\( 6 \mid k^3 - k \)
\( p(k + 1) \) önermesinin doğru olduğunu gösterelim.
\( 6 \mid (k + 1)^3 - (k + 1) \)
\( (k + 1)^3 - (k + 1) \) ifadesini düzenleyelim.
\( (k + 1)^3 - (k + 1) = k^3 + 3k^2 + 3k + 1 - k - 1 \)
\( = k^3 + 3k^2 + 2k \)
\( = (k^3 - k) + (3k^2 + 3k) \)
\( = (k^3 - k) + 3k(k + 1) \)
Tümevarım hipotezine göre \( k^3 - k \) ifadesi 6'ya tam bölünür.
\( a \in \mathbb{Z} \) olmak üzere,
\( k^3 - k = 6a \)
\( k(k + 1) \) ifadesi bir tek ve bir çift sayının çarpımı olduğu için çift sayıdır, dolayısıyla \( 3k(k + 1) \) ifadesi 2 ve 3 çarpanı içerdiği için 6'ya tam bölünür.
\( b \in \mathbb{Z} \) olmak üzere,
\( 3k(k + 1) = 6b \)
\( (k^3 - k) + 3k(k + 1) = 6a + 6b \)
\( = 6(a + b) \)
Buna göre \( (k^3 - k) + 3k(k + 1) \) ifadesi 6'ya tam bölünür.
O halde \( p(k) \) doğru ise \( p(k + 1) \) de doğru olur.
Dolayısıyla, tümevarım yöntemine göre \( p(n) \) önermesi her \( n \ge 2 \) tam sayısı için doğrudur.
SORU 4:
Her \( n \ge 1 \) tam sayısı için \( 9^n - 4^n \) ifadesinin 5'e tam bölündüğünü gösterin.
Çözümü Göster
Verilen önermeyi bir \( p(n) \) açık önermesi şeklinde tanımlayalım ve doğruluğunu ispatlamak için tümevarım yöntemini kullanalım.
\( p(n): 5 \mid 9^n - 4^n \)
Başlangıç adımı: Önermenin \( n = 1 \) için doğru olduğunu gösterelim.
\( 9^1 - 4^1 = 5 \)
\( 5 \mid 5 \)
Buna göre \( p(1) \) doğrudur.
Tümevarım adımı: \( k \ge 1 \) olmak üzere, önermenin \( n = k \) için doğru olduğunu kabul edelim ve \( n = k + 1 \) için de doğru olduğunu gösterelim.
\( p(k) \Rightarrow p(k + 1) \)
Tümevarım hipotezi: \( p(k) \) önermesinin doğru olduğunu kabul edelim.
\( 5 \mid 9^k - 4^k \)
\( p(k + 1) \) önermesinin doğru olduğunu gösterelim.
\( 5 \mid 9^{k + 1} - 4^{k + 1} \)
\( 9^{k + 1} - 4^{k + 1} \) ifadesini düzenleyelim.
\( 9^{k + 1} - 4^{k + 1} = 9 \cdot 9^k - 4 \cdot 4^k \)
\( = 5 \cdot 9^k + 4 \cdot 9^k - 4 \cdot 4^k \)
\( = 5 \cdot 9^k + 4(9^k - 4^k) \)
Tümevarım hipotezine göre \( 9^k - 4^k \) ifadesi 5'e tam bölünür.
\( a \in \mathbb{Z} \) olmak üzere,
\( 9^k - 4^k = 5a \)
\( = 5 \cdot 9^k + 4(5a) \)
\( = 5(9^k + 4a) \)
Buna göre \( 9^{k + 1} - 4^{k + 1} \) ifadesi 5'e tam bölünür.
O halde \( p(k) \) doğru ise \( p(k + 1) \) de doğru olur.
Dolayısıyla, tümevarım yöntemine göre \( p(n) \) önermesi her \( n \ge 1 \) tam sayısı için doğrudur.
SORU 5:
Her \( n \ge 5 \) tam sayısı için \( 4n \lt 2^n \) olduğunu gösterin.
Çözümü Göster
Verilen eşitsizliği bir \( p(n) \) açık önermesi şeklinde tanımlayalım ve doğruluğunu ispatlamak için tümevarım yöntemini kullanalım.
\( p(n): 4n \lt 2^n \)
Başlangıç adımı: Önermenin \( n = 5 \) için doğru olduğunu gösterelim.
\( 4(5) \stackrel{?}{\lt} 2^5 \)
\( 20 \lt 32 \)
Buna göre \( p(5) \) doğrudur.
Tümevarım adımı: \( k \ge 5 \) olmak üzere, önermenin \( n = k \) için doğru olduğunu kabul edelim ve \( n = k + 1 \) için de doğru olduğunu gösterelim.
\( p(k) \Rightarrow p(k + 1) \)
Tümevarım hipotezi: \( p(k) \) önermesinin doğru olduğunu kabul edelim.
\( 4k \lt 2^k \)
\( p(k + 1) \) önermesinin doğru olduğunu gösterelim.
\( 4(k + 1) \lt 2^{k + 1} \)
\( 4(k + 1) = 4k + 4 \)
Tümevarım hipotezine göre \( 4k \lt 2^k \) olur.
\( \lt 2^k + 4 \)
Her \( k \ge 5 \) için \( 2^k \gt 4 \) olur.
\( \lt 2^k + 2^k \)
\( = 2 \cdot 2^k \)
\( = 2^{k + 1} \)
\( 4(k + 1) \lt 2^{k + 1} \)
O halde \( p(k) \) doğru ise \( p(k + 1) \) de doğru olur.
Dolayısıyla, tümevarım yöntemine göre \( p(n) \) önermesi her \( n \ge 5 \) tam sayısı için doğrudur.
SORU 6:
\( x \in \mathbb{R^+} \) olmak üzere,
Her \( n \ge 1 \) tam sayısı için \( (1 + x)^n \ge 1 + nx \) olduğunu gösterin.
Çözümü Göster
Verilen eşitsizliği bir \( p(n) \) açık önermesi şeklinde tanımlayalım ve doğruluğunu ispatlamak için tümevarım yöntemini kullanalım.
\( p(n): (1 + x)^n \ge 1 + nx \)
Başlangıç adımı: Önermenin \( n = 1 \) için doğru olduğunu gösterelim.
\( (1 + x)^1 \stackrel{?}{\ge} 1 + 1x \)
\( 1 + x \ge 1 + x \)
Buna göre \( p(1) \) doğrudur.
Tümevarım adımı: \( k \ge 1 \) olmak üzere, önermenin \( n = k \) için doğru olduğunu kabul edelim ve \( n = k + 1 \) için de doğru olduğunu gösterelim.
\( p(k) \Rightarrow p(k + 1) \)
Tümevarım hipotezi: \( p(k) \) önermesinin doğru olduğunu kabul edelim.
\( (1 + x)^k \ge 1 + kx \)
\( p(k + 1) \) önermesinin doğru olduğunu gösterelim.
\( (1 + x)^{k + 1} \ge 1 + (k + 1)x \)
\( (1 + x)^{k + 1} = (1 + x)(1 + x)^k \)
Tümevarım hipotezine göre \( (1 + x)^k \ge 1 + kx \) olur.
\( \ge (1 + x)(1 + kx) \)
\( = 1 + kx + x + kx^2 \)
Her \( k \ge 1 \) için \( kx^2 \ge 0 \) olduğu için eşitsizliğin sağ tarafından \( kx^2 \) çıkarmamız \( \ge \) eşitsizliğini bozmaz.
\( \ge 1 + kx + x \)
\( = 1 + (k + 1)x \)
\( (1 + x)^{k + 1} \ge 1 + (k + 1)x \)
O halde \( p(k) \) doğru ise \( p(k + 1) \) de doğru olur.
Dolayısıyla, tümevarım yöntemine göre \( p(n) \) önermesi her \( n \ge 1 \) tam sayısı için doğrudur.
SORU 7:
\( x \ne y \) olmak üzere,
Her \( n \ge 1 \) tam sayısı için \( x^n - y^n \) ifadesinin \( x - y \) ifadesine tam bölündüğünü gösterin.
Çözümü Göster
Verilen ifadeyi bir \( p(n) \) açık önermesi şeklinde tanımlayalım ve doğruluğunu ispatlamak için tümevarım yöntemini kullanalım.
\( p(n): x - y \mid x^n - y^n \)
Başlangıç adımı: Önermenin \( n = 1 \) için doğru olduğunu gösterelim.
\( x - y \mid x^1 - y^1 \)
Buna göre \( p(1) \) doğrudur.
Tümevarım adımı: \( k \ge 1 \) olmak üzere, önermenin \( n = k \) için doğru olduğunu kabul edelim ve \( n = k + 1 \) için de doğru olduğunu gösterelim.
\( p(k) \Rightarrow p(k + 1) \)
Tümevarım hipotezi: \( p(k) \) önermesinin doğru olduğunu kabul edelim.
\( x - y \mid x^k - y^k \)
\( p(k + 1) \) önermesinin doğru olduğunu gösterelim.
\( x - y \mid x^{k + 1} - y^{k + 1} \)
\( x^{k + 1} - y^{k + 1} \) ifadesini düzenleyelim.
\( x^{k + 1} - y^{k + 1} = x \cdot x^k - y \cdot y^k \)
\( = [(x - y) \cdot x^k + y \cdot x^k] - y \cdot y^k \)
\( = (x - y)x^k + y(x^k - y^k) \)
Tümevarım hipotezine göre \( x^k - y^k \) ifadesi \( x - y \) ifadesine tam bölünür.
\( a \in \mathbb{Z} \) olmak üzere,
\( x^k - y^k = a(x - y) \)
\( = (x - y)x^k + ya(x - y) \)
\( = (x - y)(x^k + ya) \)
Buna göre \( x^{k + 1} - y^{k + 1} \) ifadesi \( x - y \) ifadesine tam bölünür.
O halde \( p(k) \) doğru ise \( p(k + 1) \) de doğru olur.
Dolayısıyla, tümevarım yöntemine göre \( p(n) \) önermesi her \( n \ge 1 \) tam sayısı için doğrudur.
SORU 8:
Her \( n \ge 1 \) tam sayısı için \( 4^n + 6n + 8 \) ifadesinin 9'a tam bölündüğünü gösterin.
Çözümü Göster
Verilen ifadeyi bir \( p(n) \) açık önermesi şeklinde tanımlayalım ve doğruluğunu ispatlamak için tümevarım yöntemini kullanalım.
\( p(n): 9 \mid 4^n + 6n + 8 \)
Başlangıç adımı: Önermenin \( n = 1 \) için doğru olduğunu gösterelim.
\( 4^1 + 6(1) + 8 = 18 \)
\( 9 \mid 18 \)
Buna göre \( p(1) \) doğrudur.
Tümevarım adımı: \( k \ge 1 \) olmak üzere, önermenin \( n = k \) için doğru olduğunu kabul edelim ve \( n = k + 1 \) için de doğru olduğunu gösterelim.
\( p(k) \Rightarrow p(k + 1) \)
Tümevarım hipotezi: \( p(k) \) önermesinin doğru olduğunu kabul edelim.
\( 9 \mid 4^k + 6k + 8 \)
\( p(k + 1) \) önermesinin doğru olduğunu gösterelim.
\( 9 \mid 4^{k + 1} + 6(k + 1) + 8 \)
\( 4^{k + 1} + 6(k + 1) + 8 \) ifadesini düzenleyelim.
\( 4^{k + 1} + 6(k + 1) + 8 = 4 \cdot 4^k + 6k + 14 \)
\( = (4^k + 6k + 8) + 3(4^k + 2) \)
Tümevarım hipotezine göre \( 4^k + 6k + 8 \) ifadesi 9'a tam bölünür.
\( a \in \mathbb{Z} \) olmak üzere,
\( 4^k + 6k + 8 = 9a \)
\( = 9a + 3(4^k + 2) \)
Yukarıdaki soruda \( x^n - y^n \) ifadesinin \( x - y \) ifadesine bölünebildiğini göstermiştik, buna göre \( 4^n - 1^n = 4^n - 1 \) ifadesi \( 4 - 1 = 3 \)'e tam bölünür.
\( 4^n - 1 \) ifadesi 3'e tam bölünüyorsa \( 4^n + 2 \) ifadesi de tam bölünür. \( 4^k + 2 \) ifadesinin 3'e bölünebilirliği ayrı bir tümevarım ispatı ile de gösterilebilir.
\( 3 \mid 4^n + 2 \)
\( b \in \mathbb{Z} \) olmak üzere,
\( 4^n + 2 = 3b \)
Bu değeri \( p(k + 1) \) önermesindeki bölünende yerine koyalım.
\( = 9a + 3(3b) \)
\( = 9(a + b) \)
Buna göre \( 9 \mid 4^{k + 1} + 6(k + 1) + 8 \) ifadesi 9'a tam bölünür.
O halde \( p(k) \) doğru ise \( p(k + 1) \) de doğru olur.
Dolayısıyla, tümevarım yöntemine göre önerme her \( n \ge 1 \) için doğrudur.
SORU 9:
\( x \ne 1 \) olmak üzere,
Her \( n \ge 1 \) pozitif tam sayısı için aşağıdaki eşitliğin sağlandığını gösterin.
\( 1 + x + x^2 + \ldots + x^n = \dfrac{x^{n + 1} - 1}{x - 1} \)
Çözümü Göster
Verilen eşitliği bir \( p(n) \) açık önermesi şeklinde tanımlayalım ve doğruluğunu ispatlamak için tümevarım yöntemini kullanalım.
\( p(n): 1 + x + x^2 + \ldots + x^n = \dfrac{x^{n + 1} - 1}{x - 1} \)
Başlangıç adımı: Önermenin \( n = 1 \) için doğru olduğunu gösterelim.
\( 1 + x^1 = \dfrac{x^{1 + 1} - 1}{x - 1} \)
\( 1 + x = \dfrac{(x - 1)(x + 1)}{x - 1} \)
\( 1 + x = x + 1 \)
Buna göre \( p(1) \) doğrudur.
Tümevarım adımı: \( k \ge 1 \) olmak üzere, önermenin \( n = k \) için doğru olduğunu kabul edelim ve \( n = k + 1 \) için de doğru olduğunu gösterelim.
\( p(k) \Rightarrow p(k + 1) \)
Tümevarım hipotezi: \( p(k) \) önermesinin doğru olduğunu kabul edelim.
\( 1 + x + x^2 + \ldots + x^k = \dfrac{x^{k + 1} - 1}{x - 1} \)
\( p(k + 1) \) önermesinin doğru olduğunu gösterelim.
\( 1 + x + x^2 + \ldots + x^{k + 1} = \textcolor{red}{\dfrac{x^{k + 2} - 1}{x - 1}} \)
Eşitliğin sol tarafında son terim dışındaki terimlerin toplamı \( p(k) \) toplam formülüne eşittir.
\( = \dfrac{x^{k + 1} - 1}{x - 1} + x^{k + 1} \)
İfadeyi düzenleyelim.
\( = \dfrac{x^{k + 1} - 1}{x - 1} + \dfrac{x^{k + 1}(x - 1)}{x - 1} \)
\( = \dfrac{x^{k + 1} - 1 + x^{k + 2} - x^{k + 1}}{x - 1} \)
\( = \textcolor{red}{\dfrac{x^{k + 2} - 1}{x - 1}} \)
\( p(k + 1) \) önermesindeki eşitliğin sağ tarafını elde etmiş olduk.
O halde \( p(k) \) doğru ise \( p(k + 1) \) de doğru olur.
Dolayısıyla, tümevarım yöntemine göre \( p(n) \) önermesi her \( n \ge 1 \) tam sayısı için doğrudur.
SORU 10:
30 takımın katıldığı bir voleybol turnuvasında her takım diğer her takımla tek bir maç yapıyor ve her maçı takımlardan biri kazanıyor.
Turnuva sonunda takımların \( k \). takım \( (k + 1) \). takımı yenmiş olacak şekilde 1'den 30'a kadar numaralandırılmasının mümkün olduğunu gösterin (\( k \in \{1, 2, \ldots, 29\} \)).
Çözümü Göster
Verilen ifadeyi bir \( p(n) \) açık önermesi şeklinde tanımlayalım ve doğruluğunu ispatlamak için tümevarım yöntemini kullanalım.
\( p(n) \): \( n \). takım \( (n - 1) \). takımı yendi.
Başlangıç adımı: Önermenin \( n = 2 \) için doğru olduğunu gösterelim.
2 takımlı turnuvada iki takım arasındaki maçı kazanan takım 1, kaybeden takım 2 olarak numaralandırdığında istenen koşul sağlanır.
Buna göre \( p(2) \) doğrudur.
Tümevarım adımı: \( k \ge 2 \) olmak üzere, önermenin \( n = k \) için doğru olduğunu kabul edelim ve \( n = k + 1 \) için de doğru olduğunu gösterelim.
\( p(k) \Rightarrow p(k + 1) \)
Tümevarım hipotezi: \( p(k) \) önermesinin doğru olduğunu kabul edelim.
\( p(k) \) önermesinin doğru olduğunu kabul ettiğimiz için \( k \) takımın istenen şekilde numaralandırılabildiğini varsayabiliriz.
\( p(k + 1) \) önermesinin doğru olduğunu gösterelim.
\( (k + 1) \). takım hiçbir maçı kazanmadıysa \( (k + 1) \) olarak numaralandırılır. Bu durumda takım listenin sonundaki takıma da kaybettiği için liste istenen koşulu sağlamaya devam eder.
\( (k + 1) \). takım en az bir maçı kazandıysa yendiği takımlar içinde listedeki en düşük numaralı takımın numarasına \( m \) diyelim. Bu durumda \( (k + 1) \). takım \( m \). takımın yerine geçer ve listede \( m \). sırada ve sonraki takımların numaraları birer artırılır. \( (k + 1) \). takım \( (m - 1) \). takıma kaybettiği ve \( m \). takımı yendiği için liste istenen koşulu sağlamaya devam eder.
O halde \( p(k) \) doğru ise \( p(k + 1) \) de doğru olur.
Dolayısıyla, tümevarım yöntemine göre \( p(n) \) önermesi her \( n \ge 2 \) tam sayısı için doğrudur.
SORU 11:
\( a_0 = 3, a_1 = 8 \) olmak üzere,
Her \( n \ge 2 \) tam sayısı için \( a_n = 3a_{n-1} - 2a_{n-2} - 5 \) eşitliği veriliyor.
Her \( n \ge 0 \) için \( a_n = 5n + 3 \) olduğunu gösterin.
Çözümü Göster
Verilen eşitliği bir \( p(n) \) açık önermesi şeklinde tanımlayalım ve doğruluğunu ispatlamak için tümevarım yöntemini kullanalım.
\( p(n): a_n = 5n + 3 \)
Başlangıç adımı: Önermenin \( n = 0 \) ve \( n = 1 \) için doğru olduğunu gösterelim.
\( a_0 = 5(0) + 3 = 3 \)
\( a_1 = 5(1) + 3 = 8 \)
Buna göre \( p(0) \) ve \( p(1) \) doğrudur.
Tümevarım adımı: \( k \ge 1 \) olmak üzere, önermenin \( n = k \) için doğru olduğunu kabul edelim ve \( n = k + 1 \) için de doğru olduğunu gösterelim.
\( p(k) \Rightarrow p(k + 1) \)
Tümevarım hipotezi: \( p(k) \) önermesinin doğru olduğunu kabul edelim.
\( a_k = 5k + 3 \)
\( p(k + 1) \) önermesinin doğru olduğunu gösterelim.
\( a_{k+1} = \textcolor{red}{5(k + 1) + 3} \)
Soruda verilen özyinelemeli formülü kullanalım.
\( a_{k+1} = 3a_k - 2a_{k-1} - 5 \)
Tümevarım hipotezine göre \( a_k = 5k + 3 \) olur.
\( = 3(5k + 3) - 2(5(k - 1) + 3) - 5 \)
\( = 15k + 9 - 2(5k - 2) - 5 \)
\( = 15k + 9 - 10k + 4 - 5 \)
\( = 5k + 8 \)
\( = \textcolor{red}{5(k + 1) + 3} \)
\( p(k + 1) \) önermesindeki eşitliğin sağ tarafını elde etmiş olduk.
O halde \( p(k) \) doğru ise \( p(k + 1) \) de doğru olur.
Dolayısıyla, tümevarım yöntemine göre \( p(n) \) önermesi her \( n \ge 0 \) tam sayısı için doğrudur.
SORU 12:
\( F_0 = 0 \) ve \( F_1 = 1 \) olmak üzere, Fibanacci dizisi aşağıdaki şekilde tanımlıdır.
\( F_n = F_{n-1} + F_{n-2} \)
Her \( n \ge 0 \) için, ilk \( n \) Fibonacci sayısının toplamının aşağıdaki formülle bulunabileceğini gösterin.
\( F_0 + F_1 + \ldots + F_n = F_{n+2} - 1 \)
Çözümü Göster
Verilen eşitliği bir \( p(n) \) açık önermesi şeklinde tanımlayalım ve doğruluğunu ispatlamak için tümevarım yöntemini kullanalım.
\( p(n): F_0 + F_1 + \ldots + F_n = F_{n+2} - 1 \)
Başlangıç adımı: Önermenin \( n = 0 \) için doğru olduğunu gösterelim.
\( F_2 = F_1 + F_0 = 1 + 0 = 1 \)
\( F_0 \stackrel{?}{=} F_2 - 1 \)
\( 0 = 1 - 1 = 0 \)
Buna göre \( p(0) \) doğrudur.
Tümevarım adımı: \( k \ge 0 \) olmak üzere, önermenin \( n = k \) için doğru olduğunu kabul edelim ve \( n = k + 1 \) için de doğru olduğunu gösterelim.
\( p(k) \Rightarrow p(k + 1) \)
Tümevarım hipotezi: \( p(k) \) önermesinin doğru olduğunu kabul edelim.
\( F_0 + F_1 + \ldots + F_k = F_{k+2} - 1 \)
\( p(k + 1) \) önermesinin doğru olduğunu gösterelim.
\( F_0 + F_1 + \ldots + F_{k+1} = \textcolor{red}{F_{k+3} - 1} \)
Eşitliğin sol tarafında son terim dışındaki terimlerin toplamı \( p(k) \) toplam formülüne eşittir.
\( = (F_{k+2} - 1) + F_{k+1} \)
\( = (F_{k+1} + F_{k+2}) - 1 \)
\( = \textcolor{red}{F_{k+3} - 1} \)
\( p(k + 1) \) önermesindeki eşitliğin sağ tarafını elde etmiş olduk.
O halde \( p(k) \) doğru ise \( p(k + 1) \) de doğru olur.
Dolayısıyla, tümevarım yöntemine göre önerme her \( n \ge 0 \) için doğrudur.
SORU 13:
Her \( n \ge 1 \) tam sayısı için aşağıdaki toplam formülünün doğru olduğunu gösterin.
\( 1(2) + 2(3) + 3(4) + \ldots + n(n + 1) \) \( = \dfrac{n(n + 1)(n + 2)}{3} \)
Çözümü Göster
Verilen eşitliği bir \( p(n) \) açık önermesi şeklinde tanımlayalım ve doğruluğunu ispatlamak için tümevarım yöntemini kullanalım.
\( p(n): 1(2) + 2(3) + \ldots + n(n + 1) \) \( = \dfrac{n(n + 1)(n + 2)}{3} \)
Başlangıç adımı: Önermenin \( n = 1 \) için doğru olduğunu gösterelim.
\( n = 1 \) için sayı dizisi tek bir terimden oluşur.
\( 1(2) \stackrel{?}{=} \dfrac{1(1 + 1)(1 + 2)}{3} \)
\( 2 = 2 \)
Buna göre \( p(1) \) doğrudur.
Tümevarım adımı: \( k \ge 1 \) olmak üzere, önermenin \( n = k \) için doğru olduğunu kabul edelim ve \( n = k + 1 \) için de doğru olduğunu gösterelim.
\( p(k) \Rightarrow p(k + 1) \)
Tümevarım hipotezi: \( p(k) \) önermesinin doğru olduğunu kabul edelim.
\( 1(2) + 2(3) + \ldots + k(k + 1) = \dfrac{k(k + 1)(k + 2)}{3} \)
\( p(k + 1) \) önermesinin doğru olduğunu gösterelim.
\( 1(2) + 2(3) + \ldots + (k + 1)(k + 2) = \textcolor{red}{\dfrac{(k + 1)(k + 2)(k + 3)}{3}} \)
Eşitliğin sol tarafında son terim dışındaki terimlerin toplamı \( p(k) \) toplam formülüne eşittir.
\( = \dfrac{k(k + 1)(k + 2)}{3} + (k + 1)(k + 2) \)
Terimleri \( (k + 1)(k + 2) \) parantezine alalım.
\( = (k + 1)(k + 2)(\dfrac{k}{3} + 1) \)
\( = \textcolor{red}{\dfrac{(k + 1)(k + 2)(k + 3)}{3}} \)
\( p(k + 1) \) önermesindeki eşitliğin sağ tarafını elde etmiş olduk.
O halde \( p(k) \) doğru ise \( p(k + 1) \) de doğru olur.
Dolayısıyla, tümevarım yöntemine göre \( p(n) \) önermesi her \( n \ge 1 \) tam sayısı için doğrudur.
SORU 14:
Her \( n \ge 1 \) tam sayısı için aşağıdaki toplam formülünün doğru olduğunu gösterin.
\( 1(2)(3) + 2(3)(4) + \ldots + n(n + 1)(n + 2) \) \( = \dfrac{n(n + 1)(n + 2)(n + 3)}{4} \)
Çözümü Göster
Verilen eşitliği bir \( p(n) \) açık önermesi şeklinde tanımlayalım ve doğruluğunu ispatlamak için tümevarım yöntemini kullanalım.
\( p(n): 1(2)(3) + 2(3)(4) + \ldots + n(n + 1)(n + 2) \) \( = \dfrac{n(n + 1)(n + 2)(n + 3)}{4} \)
Başlangıç adımı: Önermenin \( n = 1 \) için doğru olduğunu gösterelim.
\( n = 1 \) için sayı dizisi tek bir terimden oluşur.
\( 1(2)(3) \stackrel{?}{=} \dfrac{1(1 + 1)(1 + 2)(1 + 3)}{4} \)
\( 6 = 6 \)
Buna göre \( p(1) \) doğrudur.
Tümevarım adımı: \( k \ge 1 \) olmak üzere, önermenin \( n = k \) için doğru olduğunu kabul edelim ve \( n = k + 1 \) için de doğru olduğunu gösterelim.
\( p(k) \Rightarrow p(k + 1) \)
Tümevarım hipotezi: \( p(k) \) önermesinin doğru olduğunu kabul edelim.
\( 1(2)(3) + 2(3)(4) + \ldots + k(k + 1)(k + 2) = \dfrac{k(k + 1)(k + 2)(k + 3)}{4} \)
\( p(k + 1) \) önermesinin doğru olduğunu gösterelim.
\( 1(2)(3) + 2(3)(4) + \ldots + (k + 1)(k + 2)(k + 3) = \textcolor{red}{\dfrac{(k + 1)(k + 2)(k + 3)(k + 4)}{4}} \)
Eşitliğin sol tarafında son terim dışındaki terimlerin toplamı \( p(k) \) toplam formülüne eşittir.
\( = \dfrac{k(k + 1)(k + 2)(k + 3)}{4} + (k + 1)(k + 2)(k + 3) \)
Terimleri \( (k + 1)(k + 2)(k + 3) \) parantezine alalım.
\( = (k + 1)(k + 2)(k + 3)(\dfrac{k}{4} + 1) \)
\( = \textcolor{red}{\dfrac{(k + 1)(k + 2)(k + 3)(k + 4)}{4}} \)
\( p(k + 1) \) önermesindeki eşitliğin sağ tarafını elde etmiş olduk.
O halde \( p(k) \) doğru ise \( p(k + 1) \) de doğru olur.
Dolayısıyla, tümevarım yöntemine göre \( p(n) \) önermesi her \( n \ge 1 \) tam sayısı için doğrudur.
SORU 15:
Her \( n \ge 1 \) tam sayısı için aşağıdaki toplam formülünün doğru olduğunu gösterin.
\( \dfrac{1}{1 \cdot 3} + \dfrac{1}{3 \cdot 5} + \dfrac{1}{5 \cdot 7} + \ldots + \dfrac{1}{(2n - 1)(2n + 1)} \) \( = \dfrac{n}{2n + 1} \)
Çözümü Göster
Verilen eşitliği bir \( p(n) \) açık önermesi şeklinde tanımlayalım ve doğruluğunu ispatlamak için tümevarım yöntemini kullanalım.
\( p(n): \dfrac{1}{1 \cdot 3} + \dfrac{1}{3 \cdot 5} + \ldots + \dfrac{1}{(2n - 1)(2n + 1)} \) \( = \dfrac{n}{2n + 1} \)
Başlangıç adımı: Önermenin \( n = 1 \) için doğru olduğunu gösterelim.
\( n = 1 \) için sayı dizisi tek bir terimden oluşur.
\( \dfrac{1}{1 \cdot 3} \stackrel{?}{=} \dfrac{1}{2(1) + 1} \)
\( \dfrac{1}{3} = \dfrac{1}{3} \)
Buna göre \( p(1) \) doğrudur.
Tümevarım adımı: \( k \ge 1 \) olmak üzere, önermenin \( n = k \) için doğru olduğunu kabul edelim ve \( n = k + 1 \) için de doğru olduğunu gösterelim.
\( p(k) \Rightarrow p(k + 1) \)
Tümevarım hipotezi: \( p(k) \) önermesinin doğru olduğunu kabul edelim.
\( \dfrac{1}{1 \cdot 3} + \dfrac{1}{3 \cdot 5} + \ldots + \dfrac{1}{(2k - 1)(2k + 1)} = \dfrac{k}{2k + 1} \)
\( p(k + 1) \) önermesinin doğru olduğunu gösterelim.
\( \dfrac{1}{1 \cdot 3} + \dfrac{1}{3 \cdot 5} + \ldots + \dfrac{1}{(2(k + 1) - 1)(2(k + 1) + 1)} = \textcolor{red}{\dfrac{k + 1}{2(k + 1) + 1}} \)
Eşitliğin sol tarafında son terim dışındaki terimlerin toplamı \( p(k) \) toplam formülüne eşittir.
\( = \dfrac{k}{2k + 1} + \dfrac{1}{(2(k + 1) - 1)(2(k + 1) + 1)} \)
\( = \dfrac{k}{2k + 1} + \dfrac{1}{(2k + 1)(2k + 3)} \)
\( = \dfrac{k(2k + 3)}{(2k + 1)(2k + 3)} + \dfrac{1}{(2k + 1)(2k + 3)} \)
\( = \dfrac{2k^2 + 3k + 1}{(2k + 1)(2k + 3)} \)
\( = \dfrac{(2k + 1)(k + 1)}{(2k + 1)(2k + 3)} \)
\( = \dfrac{k + 1}{2k + 3} \)
\( = \textcolor{red}{\dfrac{k + 1}{2(k + 1) + 3}} \)
\( p(k + 1) \) önermesindeki eşitliğin sağ tarafını elde etmiş olduk.
O halde \( p(k) \) doğru ise \( p(k + 1) \) de doğru olur.
Dolayısıyla, tümevarım yöntemine göre \( p(n) \) önermesi her \( n \ge 1 \) tam sayısı için doğrudur.
SORU 16:
Her \( n \ge 1 \) tam sayısı için aşağıdaki toplam formülünün doğru olduğunu gösterin.
\( 3 + 11 + 19 + \ldots + (8n - 5) = n(4n - 1) \)
Çözümü Göster
Verilen eşitliği bir \( p(n) \) açık önermesi şeklinde tanımlayalım ve doğruluğunu ispatlamak için tümevarım yöntemini kullanalım.
\( p(n): 3 + 11 + \ldots + (8n - 5) = n(4n - 1) \)
Başlangıç adımı: Önermenin \( n = 1 \) için doğru olduğunu gösterelim.
\( n = 1 \) için sayı dizisi tek bir terimden oluşur.
\( 3 \stackrel{?}{=} 1(4(1) - 1) \)
\( 3 = 3 \)
Buna göre \( p(1) \) doğrudur.
Tümevarım adımı: \( k \ge 1 \) olmak üzere, önermenin \( n = k \) için doğru olduğunu kabul edelim ve \( n = k + 1 \) için de doğru olduğunu gösterelim.
\( p(k) \Rightarrow p(k + 1) \)
Tümevarım hipotezi: \( p(k) \) önermesinin doğru olduğunu kabul edelim.
\( 3 + 11 + \ldots + (8k - 5) = k(4k - 1) \)
\( p(k + 1) \) önermesinin doğru olduğunu gösterelim.
\( 3 + 11 + \ldots + (8(k + 1) - 5) = \textcolor{red}{(k + 1)(4(k + 1) - 1)} \)
Eşitliğin sol tarafında son terim dışındaki terimlerin toplamı \( p(k) \) toplam formülüne eşittir.
\( = k(4k - 1) + (8(k + 1) - 5) \)
İfadeyi düzenleyelim.
\( = 4k^2 - k + 8k + 3 \)
\( = 4k^2 + 7k + 3 \)
\( = (k + 1)(4k + 3) \)
\( = \textcolor{red}{(k + 1)(4(k + 1) - 1)} \)
\( p(k + 1) \) önermesindeki eşitliğin sağ tarafını elde etmiş olduk.
O halde \( p(k) \) doğru ise \( p(k + 1) \) de doğru olur.
Dolayısıyla, tümevarım yöntemine göre \( p(n) \) önermesi her \( n \ge 1 \) tam sayısı için doğrudur.
SORU 17:
Her \( n \ge 2 \) tam sayısı için aşağıdaki eşitsizliğin doğru olduğunu gösterin.
\( \abs{x_1 + x_2 + \ldots + x_n} \le \abs{x_1} + \abs{x_2} + \ldots + \abs{x_n} \)
Çözümü Göster
Verilen eşitsizliği bir \( p(n) \) açık önermesi şeklinde tanımlayalım ve doğruluğunu ispatlamak için tümevarım yöntemini kullanalım.
\( p(n): \abs{x_1 + x_2 + \ldots + x_n} \le \abs{x_1} + \abs{x_2} + \ldots + \abs{x_n} \)
Başlangıç adımı: Önermenin \( n = 2 \) için doğru olduğunu gösterelim.
\( \abs{x_1 + x_2} \le \abs{x_1} + \abs{x_2} \)
Üçgen eşitsizliğinden bu eşitsizliğin doğru olduğunu biliyoruz.
Buna göre \( p(2) \) doğrudur.
Tümevarım adımı: \( k \ge 2 \) olmak üzere, önermenin \( n = k \) için doğru olduğunu kabul edelim ve \( n = k + 1 \) için de doğru olduğunu gösterelim.
\( p(k) \Rightarrow p(k + 1) \)
Tümevarım hipotezi: \( p(k) \) önermesinin doğru olduğunu kabul edelim.
\( \abs{x_1 + x_2 + \ldots + x_k} \le \abs{x_1} + \abs{x_2} + \ldots + \abs{x_k} \)
\( p(k + 1) \) önermesinin doğru olduğunu gösterelim.
\( \abs{x_1 + x_2 + \ldots + x_{k+1}} \le \abs{x_1} + \abs{x_2} + \ldots + \abs{x_{k+1}} \)
Birinci terimi ilk \( k \) terimin toplamı, ikinci terimi \( (k + 1) \). terim olan aşağıdaki gibi bir ifade yazalım.
\( (x_1 + x_2 + \ldots + x_k) + x_{k+1} \)
Bu iki terimli ifade için üçgen eşitsizliğini yazalım.
\( \abs{(x_1 + x_2 + \ldots + x_k) + x_{k+1}} \le \abs{x_1 + x_2 + \ldots + x_k} + \abs{x_{k+1}} \)
Tümevarım hipotezine göre, bu eşitsizliğin sağ tarafının ilk terimi ilk \( k \) terimin mutlak değerlerinin toplamından küçüktür ya da ona eşittir, dolayısıyla bu terimi kendisinden daha büyük olan bu ifadeyle değiştirebiliriz.
\( \abs{(x_1 + x_2 + \ldots + x_k) + x_{k + 1}} \le \abs{x_1} + \abs{x_2} + \ldots + \abs{x_k} + \abs{x_{k + 1}} \)
Eşitsizliğin iki tarafını düzenleyelim.
\( \abs{x_1 + x_2 + \ldots + x_{k + 1}} \le \abs{x_1} + \abs{x_2} + \ldots + \abs{x_{k + 1}} \)
\( p(k + 1) \) önermesini elde etmiş olduk.
O halde \( p(k) \) doğru ise \( p(k + 1) \) de doğru olur.
Dolayısıyla, tümevarım yöntemine göre \( p(n) \) önermesi her \( n \ge 2 \) tam sayısı için doğrudur.