MAT2033 · 3. hafta · proof techniques and mathematical induction

Matematiksel tümevarım ve güçlü tümevarım

Toplam formülü, bölünebilme ve eşitsizlik için tümevarım iskeleti; pul problemleri ve özyinelemeli dizilerde güçlü tümevarım. Vizede neredeyse kesin bir 20 puanlık soru.

mathematical inductionbasis stepinductive stepinductive hypothesisstrong inductionwell-ordering principledivisibilityinequalityrecursively defined sequence

Tümevarım (mathematical induction), “her pozitif tam sayı $n$ için …” diye başlayan iddiaları ispatlamanın standart yolu. Vizede neredeyse kesin bir soru: bir toplam formülü, bir bölünebilme ya da bir eşitsizlik. İyi haber: iskelet hep aynı. İskeleti kelimesi kelimesine ezberlersen, içine sadece cebiri koyarsın. Basis step tek başına bile puan getirir.

Altın kurallar:

İki adım: basis ve inductive step. İkisi de şart.
Basis, iddianın başladığı $n_0$ ‘dır. " $n \ge 4$ " diyorsa $n = 4$ .
Hipotezi mutlaka kullan. Kullanmıyorsan tümevarım yapmıyorsun.
$P(k+1)$ ‘i önce açıkça yaz. Nereye gittiğini bilmeden yola çıkma.
Tek taraftan başla. $P(k+1)$ ‘in sol tarafını al, sağ tarafa ulaş. İki tarafı birlikte işleme.

Fikir: domino

Sonsuz bir domino dizisinin hepsini devirmek için iki şey yeter:

İlk taşı devir (basis step): $P(n_0)$ doğru.
Herhangi bir taş düşerse bir sonrakini de düşürdüğünü göster (inductive step): her $k \ge n_0$ için $P(k) \to P(k+1)$ .

Biçimsel olarak:

$\big(P(n_0) \land \forall k \ge n_0\,(P(k) \to P(k+1))\big) \to \forall n \ge n_0\, P(n)$

Inductive step’te ” $P(k)$ doğru olsun” diyorsun. Bu, ispatlamak istediğini varsaymak değil: sadece “bir taş düşerse” diyorsun, düştüğünü iddia etmiyorsun. Bu varsayıma inductive hypothesis (IH) denir.

İskelet (sınavda İngilizce yazacaksın)

Let P(n) be the statement "...". We prove P(n) for all integers n ≥ n0.

Basis step. For n = n0: LHS = ..., RHS = .... They are equal, so P(n0) is true.

Inductive step. Assume P(k) is true for some arbitrary integer k ≥ n0, i.e.
  [P(k)'yi yaz]                                   (inductive hypothesis)
We must show P(k+1):
  [P(k+1)'i yaz]
  [cebir: P(k+1)'in sol tarafında P(k)'nin sol tarafını bul, IH ile değiştir]
So P(k+1) is true.

Conclusion. By the principle of mathematical induction, P(n) is true
for all integers n ≥ n0.  ∎

Tip 1: Toplam formülü

Örnek. Prove that $2 + 5 + 8 + \dots + (3n - 1) = \dfrac{n(3n+1)}{2}$ for all $n \ge 1$ .

Basis $n = 1$ : LHS $= 3 \cdot 1 - 1 = 2$ . RHS $= \tfrac{1 \cdot 4}{2} = 2$ . Eşit.

Inductive step. IH: $2 + 5 + \dots + (3k - 1) = \dfrac{k(3k+1)}{2}$ .

Hedef $P(k+1)$ : $2 + 5 + \dots + (3k - 1) + (3k + 2) = \dfrac{(k+1)(3k+4)}{2}$ .

$\underbrace{2 + 5 + \dots + (3k-1)}_{\text{IH}} + (3k+2) = \frac{k(3k+1)}{2} + (3k+2) = \frac{3k^2 + k + 6k + 4}{2} = \frac{3k^2 + 7k + 4}{2} = \frac{(k+1)(3k+4)}{2}.$

Bu tam olarak $P(k+1)$ ‘in sağ tarafı. By induction, the formula holds for all $n \ge 1$ . ∎

İPUCU · Çarpanlara ayırırken hedefe bak. $3k^2 + 7k + 4$ ‘ü nasıl ayıracağını bilmiyorsan hedefteki $(k+1)(3k+4)$ ‘ü aç: $3k^2 + 7k + 4$ . Eşleşiyorsa bitti. Hedef sana cevabı söylüyor.

Tip 2: Bölünebilme

Hile: $f(k+1)$ ‘i aç, içinde $f(k)$ ‘yı yarat. Geri kalanın da bölen sayının katı olduğunu göster.

Örnek. Prove that $3 \mid 4^n + 5$ for all $n \ge 1$ .

Basis $n = 1$ : $4 + 5 = 9 = 3 \cdot 3$ .

IH: $4^k + 5 = 3m$ for some integer $m$ .

$4^{k+1} + 5 = 4 \cdot 4^k + 5 = 4(4^k + 5) - 20 + 5 = 4(4^k + 5) - 15 = 4 \cdot 3m - 15 = 3(4m - 5).$

$4m - 5$ bir tam sayı, yani $3 \mid 4^{k+1} + 5$ . By induction ∎.

Buradaki hamle: $4 \cdot 4^k$ gördüğünde $4(4^k + 5)$ yazıp fazladan eklediğin $20$ ‘yi çıkarmak. Bölünebilme sorularının neredeyse hepsi bu hamleyle çözülür.

Tip 3: Eşitsizlik

Hipotezden başla, sonra $k \ge n_0$ ‘dan gelen basit bir gerçekle aradaki boşluğu kapat.

Örnek. Prove that $2^n > n^2$ for all integers $n \ge 5$ .

Basis $n = 5$ : $32 > 25$ .

IH: $2^k > k^2$ for some $k \ge 5$ . Then

$2^{k+1} = 2 \cdot 2^k > 2k^2.$

Şimdi $2k^2 \ge (k+1)^2$ olduğunu göstermem lazım. $2k^2 - (k+1)^2 = k^2 - 2k - 1$ . $k \ge 3$ için $k^2 - 2k - 1 = k(k-2) - 1 \ge 3 - 1 > 0$ . Demek ki $k \ge 5$ için de doğru. Zincir:

$2^{k+1} > 2k^2 \ge (k+1)^2.$

So $P(k+1)$ holds. By induction ∎.

TUZAK · Eşitsizliğin yönünü kaybetmek. Zincirdeki her halka aynı yönde olmalı ( $>$ ve $\ge$ karışabilir, sonuç $>$ olur). Bir halkada $\le$ çıkarsa zincir kopar. Her ara eşitsizliğin neden doğru olduğunu tek cümleyle yaz.

Güçlü tümevarım (strong induction)

Bazen $P(k+1)$ ‘i göstermek için sadece $P(k)$ yetmez, daha önceki değerler de lazım olur. Strong induction’da hipotez daha geniştir:

$\text{IH: } P(n_0), P(n_0+1), \dots, P(k) \text{ all true} \quad\Rightarrow\quad P(k+1).$

Mantıksal olarak normal tümevarımla aynı güçtedir; sadece yazımı kolaylaştırır. İkisinin temeli well-ordering principle: pozitif tam sayıların boş olmayan her alt kümesinin en küçük elemanı vardır.

Örnek: pul problemi

Teorem. Every amount of postage of 12 cents or more can be formed using 4-cent and 5-cent stamps.

Basis. 12 = 4+4+4, 13 = 4+4+5, 14 = 4+5+5, 15 = 5+5+5.
Inductive step. Let k ≥ 15 and assume every amount j with 12 ≤ j ≤ k
can be formed (strong IH). Then k + 1 = (k − 3) + 4, and
12 ≤ k − 3 ≤ k, so k − 3 can be formed. Add one 4-cent stamp.
Hence k + 1 can be formed. By strong induction, every n ≥ 12 works.  ∎

Neden dört basis? Adım 4 geri gidiyor. $k + 1 = 16$ için $12$ ‘ye bakıyoruz; ama $13, 14, 15$ için geri gidince 12’nin altına düşerdik, onları ayrı göstermek zorundayız. 12’nin altında 1, 2, 3, 6, 7, 11 oluşturulamaz; bu yüzden iddia 12’den başlıyor.

Örnek: asal çarpanlara ayırma

Teorem. Every integer $n \ge 2$ is a prime or a product of primes.

Basis $n = 2$ : 2 asal. Step: $2 \le j \le k$ için doğru olsun. $k + 1$ asalsa bitti. Değilse $k + 1 = ab$ , $2 \le a, b \le k$ . IH ile $a$ ve $b$ asal çarpımı, o zaman $ab$ de öyle. ∎ (Örnek: $360 = 2^3 \cdot 3^2 \cdot 5$ .) Burada $a$ ve $b$ ‘nin ne olduğunu bilmiyoruz, sadece $k$ ‘den küçük olduklarını biliyoruz. Normal tümevarım ( $P(k) \to P(k+1)$ ) burada işe yaramaz; strong induction tam bunun için var.

Basis neden şart: sahte ispat

İddia: ” $n^2 + n$ is odd for all $n \ge 1$ .” Inductive step: $k^2 + k$ tek olsun. $(k+1)^2 + (k+1) = (k^2 + k) + 2(k+1)$ , tek + çift = tek. Adım kusursuz! Ama $n = 1$ için $1 + 1 = 2$ çift. Basis çöküyor, iddia baştan yanlış. Domino’lar birbirini devirir ama ilk taş hiç düşmez.

Sık yapılan hatalar

Yanlış düşünce	Doğrusu
Basis’i atlamak ya da “açık” demek	Her zaman sayıyla iki tarafı ayrı hesapla
Basis’i $n = 1$ ‘den yapmak, iddia $n \ge 5$	Basis $n_0$ olmalı
IH: “Assume $P(n)$ is true for all $n$ ”	Bu ispatlamak istediğin şey. “for some arbitrary $k$ ” yaz
$P(k+1)$ ‘in iki tarafını birlikte işleyip $0 = 0$ ‘a ulaşmak	Bir taraftan başla, öbür tarafa var
Hipotezi hiç kullanmamak	Kullanmıyorsan tümevarım değil
$P(k+1)$ için son terimi yanlış yazmak	Formülde $n$ yerine $k+1$ koy: $3(k+1) - 1 = 3k + 2$
Strong induction’da tek basis	Adım kaç geri gidiyorsa o kadar basis
Kapanış cümlesini unutmak	“By the principle of mathematical induction …” puanın parçası

Kendini test et

Sınavdaki gibi İngilizce sorular. Önce kâğıt kalemle çöz, sonra cevabı aç.

Soru 1kolay

You want to prove $2^n > n^2$ for all integers $n \ge 5$ by induction. State the basis step and check it.

Cevabı göster

n = 5: 2⁵ = 32 > 25 = 5²

Basis, iddianın başladığı yerdir: $n_0 = 5$ . $n = 1$ değil. $2^5 = 32$ , $5^2 = 25$ , $32 > 25$ doğru. (İddia $n = 2, 3, 4$ için yanlış: $4 = 4$ , $8 < 9$ , $16 = 16$ . Bu yüzden 5'ten başlıyor.)

Soru 2kolay

Let $P(n)$ be $1 + 4 + 7 + \dots + (3n - 2) = \dfrac{n(3n - 1)}{2}$ . Write $P(k+1)$ explicitly.

Cevabı göster

1 + 4 + ... + (3k − 2) + (3k + 1) = (k + 1)(3k + 2)/2

Formülde her $n$ yerine $k+1$ koy. Son terim $3(k+1) - 2 = 3k + 1$ . Sağ taraf $\tfrac{(k+1)(3(k+1) - 1)}{2} = \tfrac{(k+1)(3k+2)}{2}$ . Sol tarafta son terimden bir önceki terimi de ( $3k - 2$ ) yazmak, hipotezi nerede kullanacağını gösterir.

Soru 3orta

Prove by induction that $\displaystyle\sum_{i=1}^{n} \frac{1}{i(i+1)} = \frac{n}{n+1}$ for all $n \ge 1$ .

Cevabı göster

Basis 1/2 = 1/2; step: k/(k+1) + 1/((k+1)(k+2)) = (k+1)/(k+2).

Basis $n = 1$ : sol $\tfrac{1}{1 \cdot 2} = \tfrac12$ , sağ $\tfrac{1}{2}$ . Eşit.
Inductive step: $\sum_{i=1}^{k} \tfrac{1}{i(i+1)} = \tfrac{k}{k+1}$ olsun (IH). Then $\sum_{i=1}^{k+1} \frac{1}{i(i+1)} = \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 tam olarak $P(k+1)$ . By induction, $P(n)$ holds for all $n \ge 1$ . ∎ Anahtar: $k^2 + 2k + 1 = (k+1)^2$ .

Soru 4zor

Prove by induction that $6 \mid n^3 + 5n$ for every positive integer $n$ .

Cevabı göster

(k+1)³ + 5(k+1) = (k³ + 5k) + 3k(k+1) + 6, and 6 divides each part.

Basis $n = 1$ : $1 + 5 = 6 = 6 \cdot 1$ .
IH: $k^3 + 5k = 6m$ . Aç: $(k+1)^3 + 5(k+1) = k^3 + 3k^2 + 3k + 1 + 5k + 5 = (k^3 + 5k) + 3k^2 + 3k + 6 = 6m + 3k(k+1) + 6$ . $k(k+1)$ ardışık iki sayının çarpımı, çift: $k(k+1) = 2t$ . O zaman $3k(k+1) = 6t$ . Toplam $6(m + t + 1)$ , 6'ya bölünür. By induction ∎. Tuzak: $3k(k+1)$ 'in 6'ya bölündüğünü gerekçesiz yazmak.

Soru 5orta

Prove by induction that $5 \mid 6^n - 1$ for all integers $n \ge 0$ .

Cevabı göster

6^(k+1) − 1 = 6(6^k − 1) + 5

Basis $n = 0$ : $6^0 - 1 = 0 = 5 \cdot 0$ . 0 her sayıya bölünür.
IH: $6^k - 1 = 5m$ . Then $6^{k+1} - 1 = 6 \cdot 6^k - 6 + 5 = 6(6^k - 1) + 5 = 6 \cdot 5m + 5 = 5(6m + 1)$ . $6m + 1$ tam sayı, yani $5 \mid 6^{k+1} - 1$ . ∎ Hile: $6^{k+1}$ 'i açıp eski ifadeyi ( $6^k - 1$ ) içinde yarat.

Soru 6orta

Prove that $n! > 2^n$ for every integer $n \ge 4$ .

Cevabı göster

Basis 24 > 16; step: (k+1)! = (k+1)k! > (k+1)2^k ≥ 2·2^k = 2^(k+1).

Basis $n = 4$ : $4! = 24 > 16 = 2^4$ .
IH: $k! > 2^k$ for some $k \ge 4$ . Then $(k+1)! = (k+1) \cdot k! > (k+1) \cdot 2^k$ . $k \ge 4$ olduğu için $k + 1 \ge 2$ , yani $(k+1) \cdot 2^k \ge 2 \cdot 2^k = 2^{k+1}$ . Zincir: $(k+1)! > 2^{k+1}$ . ∎ Eşitsizlikte "biraz küçültmek/büyütmek" serbest, yeter ki yön bozulmasın ve kullandığın gerçeği ( $k+1 \ge 2$ ) yaz.

Soru 7zor

Prove that $\displaystyle\sum_{i=1}^{n} i \cdot 2^i = (n-1)2^{n+1} + 2$ for all $n \ge 1$ .

Cevabı göster

Step: (k−1)2^(k+1) + 2 + (k+1)2^(k+1) = 2k·2^(k+1) + 2 = k·2^(k+2) + 2.

Basis $n = 1$ : sol $1 \cdot 2 = 2$ , sağ $0 \cdot 4 + 2 = 2$ .
IH: $\sum_{i=1}^{k} i 2^i = (k-1)2^{k+1} + 2$ . Yeni terim $(k+1)2^{k+1}$ . $\sum_{i=1}^{k+1} i 2^i = (k-1)2^{k+1} + 2 + (k+1)2^{k+1} = 2k \cdot 2^{k+1} + 2 = k \cdot 2^{k+2} + 2.$ Hedef $((k+1) - 1)2^{(k+1)+1} + 2 = k \cdot 2^{k+2} + 2$ . Aynı. ∎ Ortak çarpan $2^{k+1}$ 'i dışarı almak işi bitirir.

Soru 8kolay

A student "proves" that $n^2 + n$ is odd for all $n \ge 1$ : "Assume $k^2 + k$ is odd. Then $(k+1)^2 + (k+1) = (k^2 + k) + 2(k+1)$ is odd + even = odd." What is wrong?

Cevabı göster

The basis step fails: for n = 1, 1² + 1 = 2 is even.

Inductive step gerçekten doğru: tek + çift = tek. Ama domino zincirinin ilk taşı hiç devrilmiyor: $n = 1$ için $2$ çift. Basis olmadan inductive step hiçbir şey ispatlamaz. Aslında $n^2 + n$ her zaman çift.

Soru 9orta

Which positive integer amounts of postage cannot be formed using only 3-cent and 7-cent stamps? Explain why strong induction shows every amount $n \ge 12$ can be formed.

Cevabı göster

1, 2, 4, 5, 8, 11

Küçük değerleri dene: 3, 6, 7, 9, 10 olur; 1, 2, 4, 5, 8, 11 olmaz. Basis: $12 = 4 \cdot 3$ , $13 = 2 \cdot 3 + 7$ , $14 = 2 \cdot 7$ . Inductive step: $k \ge 14$ ve $12 \le j \le k$ için $j$ oluşturulabiliyorsa, $k + 1 = (k - 2) + 3$ ve $k - 2 \ge 12$ ; $k-2$ için kullanılan pullara bir 3'lük ekle. Üç ardışık basis lazım, çünkü 3 geri gidiyoruz.

Soru 10zor

Let $a_0 = 2$ , $a_1 = 1$ and $a_n = a_{n-1} + 2a_{n-2}$ for $n \ge 2$ . Prove by strong induction that $a_n = 2^n + (-1)^n$ , and find $a_5$ .

Cevabı göster

a_5 = 31

Basis: $a_0 = 2 = 1 + 1$ , $a_1 = 1 = 2 - 1$ . İki basis lazım, çünkü kural iki önceki terime bakıyor.
Step: $k \ge 1$ ve $a_j = 2^j + (-1)^j$ for all $j \le k$ (strong IH). Then $a_{k+1} = a_k + 2a_{k-1} = 2^k + (-1)^k + 2 \cdot 2^{k-1} + 2(-1)^{k-1} = 2^{k+1} + (-1)^{k-1}(-1 + 2) = 2^{k+1} + (-1)^{k+1}$ .
( $(-1)^k = -(-1)^{k-1}$ ve $(-1)^{k-1} = (-1)^{k+1}$ .) ∎ $a_5 = 32 - 1 = 31$ . Kontrol: 2, 1, 5, 7, 17, 31.

Soru 11zor

Prove that $1 + \dfrac14 + \dfrac19 + \dots + \dfrac{1}{n^2} \le 2 - \dfrac1n$ for all $n \ge 1$ .

Cevabı göster

Step reduces to 1/(k+1)² ≤ 1/k − 1/(k+1) = 1/(k(k+1)), which is true.

Basis $n = 1$ : $1 \le 2 - 1 = 1$ . Doğru.
IH: $\sum_{i=1}^{k} \tfrac{1}{i^2} \le 2 - \tfrac1k$ . Then $\sum_{i=1}^{k+1} \tfrac{1}{i^2} \le 2 - \tfrac1k + \tfrac{1}{(k+1)^2}$ . Bunun $\le 2 - \tfrac{1}{k+1}$ olduğunu göstermek için $\tfrac{1}{(k+1)^2} \le \tfrac1k - \tfrac{1}{k+1} = \tfrac{1}{k(k+1)}$ yeter; bu doğru çünkü $k(k+1) \le (k+1)^2$ . ∎ Eşitsizlik tümevarımında "hedefe ulaşmak için neye ihtiyacım var?" diye geriye çalış, sonra ileri yaz.

Soru 12orta

To prove that every postage of $n \ge 12$ cents can be formed with 4-cent and 5-cent stamps using strong induction and the step " $k+1 = (k-3) + 4$ ", how many basis cases are needed?

Cevabı göster

4 (n = 12, 13, 14, 15)

Adım 4 geri gidiyor: $k + 1$ 'i $k - 3$ 'ten elde ediyoruz. $k - 3 \ge 12$ olması için $k + 1 \ge 16$ lazım. Yani 12, 13, 14, 15'i ayrı ayrı göstermelisin: $12 = 3 \cdot 4$ , $13 = 2 \cdot 4 + 5$ , $14 = 4 + 2 \cdot 5$ , $15 = 3 \cdot 5$ .

Doğrulama: Her toplam formülü n = 1..80 için tam sayı/BigInt ile, bölünebilmeler n ≤ 500 için, eşitsizlikler n ≤ 200 için (kesirler tam kesir aritmetiğiyle), pul problemleri bütün kombinasyonlar denenerek, özyinelemeli dizi 60 terim iterasyonla node'da kontrol edildi (verify/MAT2033/03.mjs).

Deftere not kartı

İSKELET: Let P(n): "...". Basis: n=n0, LHS=..., RHS=..., equal. Inductive step: Assume P(k) for arbitrary k≥n0 (IH). Show P(k+1). Conclusion: By mathematical induction, P(n) holds for all n≥n0. ∎ n0'ı iddiadan al: "n≥4" ise basis n=4, "n≥0" ise n=0. TOPLAM: LHS(k+1) = LHS(k) + yeni terim → IH koy → ortak çarpanı dışarı al BÖLÜNEBİLME: f(k)=dm yaz; f(k+1)'i aç, içinde f(k)'yı yarat, kalan d'nin katı 6^(k+1)−1 = 6(6^k−1)+5 4^(k+1)+5 = 4(4^k+5)−15 EŞİTSİZLİK: IH'den başla, k≥n0'dan gelen küçük bir gerçekle kapat (k+1≥2, 2k+1≤k² ...) k(k+1) her zaman çift → 3k(k+1) 6'nın katı GÜÇLÜ (strong): P(n0),...,P(k) hepsini varsay → P(k+1) adım kaç geri gidiyorsa o kadar basis (pul 4-5: 12,13,14,15) a_n iki önceki terime bakıyorsa iki basis Basis yoksa ispat yok (n²+n tek "ispatı" basis'te çöker)