Doğrusal yinelemeler, üreteç fonksiyonlar ve içerme-dışlama

Bu hafta, 8.1’de kurduğun yinelemeleri (recurrence relation) çözmeyi öğreniyorsun: $a_n$‘i önceki terimlere bağlı yazmak yerine doğrudan $n$ cinsinden bir formül bulmak. Bu konu vizede yok, final konusu. Final sorusu genelde şöyle: “Solve the recurrence … with initial conditions …”. Ardından bir üreteç fonksiyon (generating function) ya da içerme-dışlama (inclusion-exclusion) sorusu gelir.

Altın kurallar:

1. Karakteristik denklem: $a_n = r^n$ koy, $r$‘nin denklemini çöz.
2. Farklı kökler $r_1 \neq r_2$: $a_n = \alpha r_1^n + \beta r_2^n$.
3. Çift kök $r$: $a_n = (\alpha + \beta n) r^n$. $n$ çarpanını unutan puanı kaybeder.
4. Sabitleri $a_0$, $a_1$ ile bul. Bir terim daha hesaplayıp kontrol et.
5. Homojen değilse: genel çözüm = homojen çözüm + özel çözüm. Başlangıç koşulunu en son uygula.

Doğrusal homojen yineleme nedir?

$k$. dereceden doğrusal homojen sabit katsayılı yineleme (linear homogeneous recurrence relation of degree $k$ with constant coefficients):

$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \dots + c_k a_{n-k}, \qquad c_k \neq 0.$

Kelime kelime:

Derece $k$ ise $k$ tane başlangıç koşulu (initial condition) diziyi tek türlü belirler. Final derecesi neredeyse her zaman 2.

Sezgi: neden $r^n$?

$a_n = 2a_{n-1}$ gibi birinci dereceden bir yineleme her adımda 2 ile çarpar, çözüm $a_n = a_0 2^n$. İkinci derecede de çözümün “üstel” olmasını bekleriz. $a_n = r^n$ yaz, yinelemeye koy:

$r^n = c_1 r^{n-1} + c_2 r^{n-2} \;\Longrightarrow\; r^2 - c_1 r - c_2 = 0.$

Bu karakteristik denklem (characteristic equation), kökleri karakteristik kökler (characteristic roots). Her kök bir temel çözüm verir; doğrusal olduğu için temel çözümlerin her doğrusal birleşimi de çözümdür.

Kural 1: farklı kökler

$r^2 - c_1 r - c_2 = 0$ iki farklı kök $r_1, r_2$ veriyorsa:

$a_n = \alpha_1 r_1^n + \alpha_2 r_2^n.$

Örnek. $a_n = a_{n-1} + 2a_{n-2}$, $a_0 = 2$, $a_1 = 7$.

1) r^2 = r + 2  ->  r^2 - r - 2 = 0  ->  (r - 2)(r + 1) = 0  ->  r = 2, r = -1
2) a_n = A 2^n + B (-1)^n
3) n = 0:  A + B = 2
   n = 1:  2A - B = 7
   topla:  3A = 9  ->  A = 3,  B = -1
4) a_n = 3 * 2^n - (-1)^n
5) kontrol: a_2 = 7 + 2*2 = 11 ;  formül 12 - 1 = 11

İPUCU · her zaman bir terim kontrol et. $a_2$‘yi yinelemeden hesapla, formülden de hesapla. Eşit değilse sistemde işaret hatası var. Sınavda 20 saniye sürer, puanı kurtarır.

Kural 2: çift kök

Karakteristik denklemin tek bir kökü varsa ($r_0$, iki katlı), $r_0^n$ tek başına iki koşulu sağlamaya yetmez. İkinci temel çözüm $n r_0^n$ olur:

$a_n = (\alpha_1 + \alpha_2 n)\, r_0^n.$

Örnek. $a_n = 4a_{n-1} - 4a_{n-2}$, $a_0 = 1$, $a_1 = 6$.

r^2 - 4r + 4 = (r - 2)^2 = 0   ->  r = 2 (çift kök)
a_n = (A + B n) 2^n
n = 0:  A = 1
n = 1:  (1 + B) * 2 = 6  ->  B = 2
a_n = (1 + 2n) 2^n
kontrol: a_3 = 4*20 - 4*6 = 56 ;  formül 7 * 8 = 56

TUZAK · çift kökte $\alpha 2^n + \beta 2^n$ yazmak. Bu aslında $(\alpha+\beta)2^n$, yani tek bir sabit. İki başlangıç koşulunu birden sağlayamaz. Çift kökte ikinci terim mutlaka $\beta n r^n$.

Bir çözümü ispatla doğrulamak

Finalde bazen “Show that $a_n = \dots$ is a solution” diye sorulur. Bu bir doğrudan ispattır: formülü sağ tarafa koy, sol tarafı elde et.

Claim. $a_n = 3\cdot 2^n - (-1)^n$ satisfies $a_n = a_{n-1} + 2a_{n-2}$ for all $n \ge 2$, with $a_0 = 2$, $a_1 = 7$.

Proof. For $n \ge 2$,

$a_{n-1} + 2a_{n-2} = 3\cdot 2^{n-1} - (-1)^{n-1} + 2\left(3\cdot 2^{n-2} - (-1)^{n-2}\right) = 3\cdot 2^{n-1} + 3\cdot 2^{n-1} - (-1)^{n-1} - 2(-1)^{n-2}.$

The first two terms give $3\cdot 2^n$. Since $(-1)^{n-1} = -(-1)^{n-2}$, the last two terms give $(-1)^{n-2} - 2(-1)^{n-2} = -(-1)^{n-2} = -(-1)^n$. Hence $a_{n-1} + 2a_{n-2} = 3\cdot 2^n - (-1)^n = a_n$. Also $a_0 = 3 - 1 = 2$ and $a_1 = 6 + 1 = 7$. $\blacksquare$

Türkçesi: iki üstel parçayı ayrı ayrı topla. $2^{n-1} + 2^{n-1} = 2^n$ hilesi ve $(-1)$‘in kuvvetlerinde bir adım kaydırınca işaret değiştiğini kullan.

Homojen olmayan yinelemeler

$a_n = c_1 a_{n-1} + \dots + c_k a_{n-k} + F(n)$ biçiminde, $F(n) \neq 0$. Çözüm:

$a_n = a_n^{(h)} + a_n^{(p)}$

$a_n^{(h)}$: $F(n)$‘i silip elde ettiğin homojen yinelemenin genel çözümü. $a_n^{(p)}$: yinelemeyi sağlayan herhangi bir özel çözüm (particular solution). Özel çözüm için tahmin tablosu:

Örnek. $a_n = 3a_{n-1} + 4$, $a_0 = 1$.

homojen:  a_n = 3 a_{n-1}            ->  a_n(h) = A 3^n
özel:     a_n(p) = C  (sabit dene)   ->  C = 3C + 4  ->  C = -2
genel:    a_n = A 3^n - 2
koşul:    a_0 = A - 2 = 1  ->  A = 3
sonuç:    a_n = 3^(n+1) - 2      kontrol: a_1 = 3 + 4 = 7 = 9 - 2

TUZAK · başlangıç koşulunu homojen kısma uygulamak. $\alpha 3^n$‘e $a_0 = 1$ uygulayıp sonra $-2$ eklersen yanlış çıkar. Önce genel çözümü tam yaz ($a^{(h)} + a^{(p)}$), koşulu en son uygula.

Böl ve yönet yinelemeleri

Problemi $a$ tane, her biri $n/b$ boyutunda alt probleme bölen, birleştirmesi $g(n)$ süren algoritmalar (binary search, merge sort):

$f(n) = a f(n/b) + g(n).$

Binary search: $f(n) = f(n/2) + 2$. Merge sort: $M(n) = 2M(n/2) + n$.

Master theorem. $f(n) = a f(n/b) + cn^d$, $a \ge 1$, $b > 1$, $c > 0$, $d \ge 0$ ise:

$f(n) \text{ is } \begin{cases} O(n^d) & a < b^d \\ O(n^d \log n) & a = b^d \\ O(n^{\log_b a}) & a > b^d \end{cases}$

Okuma şekli: $a$ (dal sayısı) ile $b^d$‘yi (bir seviyedeki işin küçülme hızı) karşılaştır.

Küçük değerleri elle de hesaplayabilirsin: $f(n) = 2f(n/2) + 3$, $f(1) = 1$ ise $f(2) = 5$, $f(4) = 13$, $f(8) = 29$.

Üreteç fonksiyonlar

Bir dizinin üreteç fonksiyonu (generating function), terimleri katsayı olarak taşıyan kuvvet serisidir:

$G(x) = a_0 + a_1 x + a_2 x^2 + \dots = \sum_{k=0}^{\infty} a_k x^k.$

Sezgi: $x^k$ bir “raf etiketi”, katsayı o rafta kaç şey olduğunu söylüyor. Polinomları çarpınca üsler toplanır; bu da “toplamı $k$ olan seçimleri say” işine birebir uyar.

Ezberlenecek açılımlar:

Sayma örneği. Üç çeşit poğaçadan 8 tane alacaksın, peynirliden en az 2 tane olmalı. Kaç farklı seçim var?

peynirli:  x^2 + x^3 + ...  = x^2 / (1 - x)
diğer iki: 1 + x + x^2 + ... = 1 / (1 - x)   (her biri)
G(x) = x^2 / (1 - x)^3
x^8 katsayısı = 1/(1-x)^3 içindeki x^6 katsayısı = C(3+6-1, 6) = C(8, 6) = 28

Sınırlı değişkenlerde (üst sınır varsa) seriyi sonlu polinom olarak yaz ve katsayıyı çarparak bul. Bu, sorulardaki $e_1 + e_2 + e_3 = 6$ örneğinde yapılan iş.

Üreteç fonksiyonla yineleme de çözülebilir: $a_k = 3a_{k-1}$, $a_0 = 1$ için $G(x) - 3xG(x) = 1$, $G(x) = \frac{1}{1-3x}$, yani $a_k = 3^k$. Finalde bu yöntem daha seyrek, karakteristik kök yöntemi asıl beklenen.

İçerme-dışlama (inclusion-exclusion)

İki küme için $|A \cup B| = |A| + |B| - |A\cap B|$. Üç küme:

$|A\cup B\cup C| = |A| + |B| + |C| - |A\cap B| - |A\cap C| - |B\cap C| + |A\cap B\cap C|.$

Sezgi: tek tek toplayınca iki kümede olanları iki kez saydın, çıkar. Ama üçünde olanı önce 3 kez ekleyip 3 kez çıkardın, yani hiç saymadın: bir kez geri ekle.

Örnek. $1..100$ arasında 2, 3 ya da 7’ye bölünen kaç sayı var?

|A| = floor(100/2) = 50     |B| = floor(100/3) = 33     |C| = floor(100/7) = 14
|AB| = floor(100/6) = 16    |AC| = floor(100/14) = 7    |BC| = floor(100/21) = 4
|ABC| = floor(100/42) = 2
|A u B u C| = 50 + 33 + 14 - 16 - 7 - 4 + 2 = 72

“Hiçbirine bölünmeyen” sorulursa $100 - 72 = 28$. Bu tamamlayıcı adımı unutmak en sık kayıp.

Sık yapılan hatalar