Albert Erkip
Önce geçen sayıdaki problemleri yanıtlamakla işe başlayalım.
(1) $x_{n+2} = 2 x_{n + 1} – x_n$ dizisini bulduğumuz yoldan çözmeye çalışırsak $r^2 – 2r + 1 = 0$ denklemi çıkar. Kökler $r_1 = 2r_2 – 1$. $x_n = Cr_1^n + Dr_2^n$ çözümünde $C, D$ katsayılarını bulalım. Başlangıç değerlerinden: \begin{gather*} C + D = 1\\C + D = 3 \end{gather*} İşler karıştı: Bir çelişki bulduk, demek ki geçen sayıdaki yol bu kez yürümedi. Başka bir yol deneyelim. Sırayla terimleri indirgeme bağıntısından hesaplarsak, diziyi $1,\, 3,\, 5,\, 7,\, 9, \dots$ olarak görüyoruz. Bu bir aritmetik dizi; genel terimi de $x_n = 2n – 1$. (Bunu kanıtlayabilir misiniz?)
(2) $x_{n + 2} = (x_{n + 1})^3/(x_n)^2$ bağıntısı önce gördüklerimize benzemiyor. Ama bunun logaritmasını alıp $y_n = \log x_n$ diye yeni bir dizi tanımlarsak, $y_n$ için $y_{n + 2} = 3 y_{n + 1} – 2 y_n$ buluruz. $y_1 = \log x_1 = \log 1 = 0,\, y_2 = \log x_2 = \log 10 = 1$ değerleri de var. O halde $y_n = 2^{n – 1} – 1$, aradığımız dizi ise $x_n = 10^{(2^{n – 1} – 1)}$.
(3) Fibonacci dizisi $1,\, 1, \, 2, \, 3, \, 5, \, 8,\, 13,\, 21,\, 34,\, 55,\, 89,\, 144, \dots$. Bu terimleri üçe bölüp kalanları sıralayalım: kalanlar $1,\, 1,\, 2,\, 0,\, 2,\, 2,\, 1,\, 0,\, 1,\, 1,\, 2, \dots$. Görülen, kalanlar dizisinin 8 terimde bir tekrarladığı. Bunu nasıl kanıtlayabiliriz? $x_n$ terimini üçe bölünce kalan tam sayıya $r_n$ diyelim. $x_{n + 2} = x_{n + 1} + x_n$ olduğundan $r_{n + 2}$ ya $r_{n + 1} + r_n$ ye ya da bu sayının üçle bölündüğünde kalanına eşit. Modüler aritmetik işimizi kolaylaştırabilir. Çünkü bu son dediğimiz $$r_{n + 2} = r_{n + 1} + r_n~~~(\text{mod}~3)$$ olarak ifade edilir. Yani kalanlar da bir tür Fibonacci dizisi. Hesapladığımız terimlerden $r_1 = r_2 = 1$ ve $r_9 = r_{10} = 1$. O halde $r_{11} = r_3,\, r_{12} = r_4, \dots$, $r_{n + 8} = r_n$ olacak. Şimdi $r_n$ lere bir kez daha bakalım. $r_4 = r_8 = 0$. O halde bunlardan $8$ sonraki $12,\, 16,\, 20,\, 24, \dots$ terimleri hep sıfır. Bu da Fibonacci dizisinde $4,\, 8,\, 12, \dots,\, 4n$-inci terimlerin üçün katı olduklarını kanıtlıyor.
Beşin katı olan terimleri bulmayı da size bırakalım.
(4) Bir sayının son rakamı, sayıyı onla böldüğümüzde elde ettiğimiz kalandır. Fibonacci dizisindeki terimlerin son rakamlarına $r_n$ diyelim. 3. problemdeki gibi $r_n$ için $r_{n + 2} = r_{n + 1} + r_n (\text{mod}~10)$ bağıntısı vardır ve bu dizinin kendini bir yerden sonra tekrarlaması için $r_m = r_{m + k},\, r_{m + 1} = r_{m + k + 1}$ olması gerekir. Bu durumda indirgeme bağıntısından dizinin ilk $m$ terimden sonra kendini $k$ terimde bir yinelediğini kanıtlayabiliriz.
O halde $r_n$’lerin tekrarlanıp tekrarlanmadığını anlamak için sabırla dizinin terimlerini yazıp ardışık $(r_m,\, r_{m + 1})$ çiftinin tekrarlanıp tekrarlanmadığına bakmak gerekiyor. Yanlış yapmadımsa $(r_{60},\, r_{61})$ çifti $(1,\, 1)$ yani $(r_1,\, r_2)$. Demek ki dizi $60$ terimde bir kendini tekrarlıyor.
Aslında tekrarlama olduğunu göstermenin daha zahmetsiz bir yolu da var. O da şu: $(r_m,\, r_{m + 1})$ çiftlerinin alabilecekleri tüm değerler $(0,\, 0),\, (0,\, 1),\, (1,\, 0), \dots,\, (9,\, 9)$. Bu da tam 100 farklı değer ediyor. Biz dizinin ilk 101 ardışık çifti $(r_1,\, r_2),\, (r_2,\, r_3), \dots,\, (r_{101},\, r_{102})$’ü alırsak bunlardan en az ikisinin birbirine eşit olması gerek. Yani Fibonacci dizisinin son rakamları bir yerden sonra kendilerini tekrarlamalı.
Bu ikinci verdiğimiz kanıt matematikte “çekmece ilkesi” denen bir ilkeye dayanıyor. Elimizde $k$ tane çekmece, içlerinde de en az $k + 1$ çorap varsa, en az bir çekmecede en azından iki çorap olmalıdır. Bu basit görünen ilke ile çok sayıda matematik problemi kolayca çözülebiliyor. Bir noktaya dikkat! Çorapların hangi çekmecede olduğu hakkında bu ilke hiç birşey söylemiyor. Biz de ikinci kanıtımızda tekrar olması gerektiğini bulduk, ama hangi terimde olacak, bunu ancak başka yoldan bulabiliriz.
(5) Para konusunda dikkat etmeli. $A$ bankasına bakalım. Önce ücretini kesip sonra faiz vermesi işimize gelmiyor çünkü bu durumda kestikleri $1$ milyonun faizini alamıyoruz. O halde öbür yolu tercih edeceğiz. Bankaya $p_0$ lira yatırdık, bir yıl sonunda $0.5 p_0$ faiz aldık, $1$ milyon kesildi, toplam para $p_1 = p_0 + 0.5 p_0 – 1$ oldu. Milyonları yer tutmasın diye yazmadık. $n$-inci yıl sonundaki toplam parayı $p_n$ ile gösterirsek, aynı yoldan $p_{n + 1} = 1.5 p_n – 1$ bağıntısı çıkıyor. Geçen sayıda gördüğümüz gibi bunu çözebilmek için önce $n$ yerine $n + 1$ koyup sonra taraf tarafa çıkarıyoruz ve $p_{n + 2} = 2.5 p_{n + 1} – 1.5 p_n$ indirgeme bağıntısını buluyoruz. Başlangıç değerleri $p_0$ ve $p_1 = 1.5 p_0 – 1$ olduğundan çözüm: $$p_n = 2 + (p_0 – 2) (1.5)^n.$$
$B$ bankasında işler daha kolay, $n$-inci yıl sonunda biriken toplam paraya $q_n$ dersek $\%45$ faiz aldığımızdan $q_{n + 1} = 1.45 q_n$. Başta $p_0$ lira yatırdık, o halde $q_n = p_0 (1.45)^n$.
Şimdi iki bankayı kıyaslayalım. $p_0$ miktarı 2 milyondan azsa $A$ kötü, çünkü paramız artmak bir yana azalıyor, bir süre sonra da borçlu çıkacağız. $p_0$, 2 milyondan fazlaysa belki ilk yıllarda $B$ daha çok gelir getirebilir, ama uzun vadede $(1.5)^n$ dizisi $(1.45)^n$’den daha hızlı arttığından tercih $A$ olmalı.
(6) Kırık basamağı bir kenara bırakıp kurbağanın herhangi bir anda $n$-inci basamağa gelme olasılığına $p_n$ diyelim. Kurbağa başta birinci basamakta olduğundan $p_1 = 1$ dir. İkinci basamağa kurbağa ancak ilk seferde tek basamaklık bir sıçrayış yaparak erişebilir, bu da $1/2$ olasılıkla olur. Yani $p_2 = 1/2$. Üçüncüde işler zorlaşıyor. Onun yerine $p_{n + 2}$ ye bakalım. $(n + 2)$-nci basamağa kurbağa ya $(n + 1)$-inciden tek basamak sıçrayarak ya da $n$-inciden çift basamak sıçrayarak gelebilir. Bu son iki olayın da olasılığı $1/2$. O halde $$p_{n + 2} = \frac{1}{2} p_{n + 1} + \frac{1}{2} p_n.$$ Bu indirgemeli dizinin çözümü $$p_n = \frac{2}{3} \left[1 – \left(\frac{-1}{2}\right)^n\right].$$ $38$-inci basamağa gelme olasılığı ise $$p_{38} = \frac{2}{3} \left(1 – \frac{1}{2^{38}}\right)$$ bu da $\frac{2}{3}$ ten biraz küçük.
Öte yandan $38$-inci basamağa basmadan $75$-inciye varmak için kurbağa önce $37$-nciye gelmeli (bunun olasılığı $p_{37}$) sonra çift sıçramalı (bunun olasılığı da $1/2$) ve son olarak da $39$-uncudan $75$-inciye gelmeli. Bu son iş için $75 – 39 = 36$ basamaklık bir yol katetmesi lazım ki, bu da birinciden $37$-inciye gitmekle eşdeğer, olasılığı $p_{37}$. Birleştirirsek, aradığımız olasılık $$p_{37} \cdot \frac{1}{2} \cdot p_{37} = \frac{2}{9} \left(1 + \frac{1}{2^{37}}\right)^2.$$
(7) $n$-inci yıl başındaki $G$ sayısına $g_n$, $D$ sayısına $d_n$ diyelim. Başlangıçta tek bir $G$ var, yani $g_0 = 1,\, d_0 = 0$. Her yıl bir $G$ den bir $G$ ve bir $D$, bir $D$ den ise bir $G$ ve iki $D$ oluşuyor. Yani \begin{align*} g_{n + 1} &= g_n + d_n\\d_{n + 1} &= g_n + 2 d_n \end{align*} Bu bir indirgeme bağıntısı gibi ama iki denklem ve iki bilinmeyen var. Nasıl çözeceğimizi kara kara düşünmek yerine birkaç terim hesaplayalım. \begin{align*} g_1 = 1,\, d_1 = 1;~~~~~&g_2 = 2,\, d_2 = 3;\\g_3 = 5,\, d_3 = 8;~~~~~&g_4 = 13,\, d_4 = 21. \end{align*} Bu Fibonacci dizisi. Yani tahminimiz $x_n$ Fibonacci dizisi olmak üzere $g_n = x_{2n – 1},\, d_n = x_{2n}$. Gerçekten de bunu tümevarımla kanıtlamak zor değil. Bunu size bırakıp problemi tamamlayalım. Aradığımız $d_n/g_n$ oranı. Fibonacci dizisi için $$x_n = \frac{1}{\sqrt{5}} \left[\left(\frac{1 + \sqrt{5}}{2}\right)^n – \left(\frac{1 – \sqrt{5}}{2}\right)^n\right]$$ olduğunu bulmuştuk. O halde $$\frac{d_n}{g_n} = \frac{x_{2n}}{x_{2n – 1}} = \frac{\left(\frac{1 + \sqrt{5}}{2}\right)^{2n} – \left(\frac{1 – \sqrt{5}}{2}^{2n}\right)}{ \left(\frac{1 + \sqrt{5}}{2}\right)^{2n – 1} – \left(\frac{1 – \sqrt{5}}{2}\right)^{2n – 1}}$$ $2n – 1$ tek bir sayı olduğundan paydadaki $ \left(\frac{1 – \sqrt{5}}{2}\right)^{2n – 1}$ terimi negatif, paydaki ise pozitiftir. Bir kesirin payını büyütüp paydasını küçültürsek kesir büyür. Yani: $$\frac{d_n}{g_n} < \frac{ \left(\frac{1 + \sqrt{5}}{2}\right)^{2n}}{ \left(\frac{1 + \sqrt{5}}{2}\right)^{2n – 1}} = \frac{1 + \sqrt{5}}{2}$$ $ \frac{1 + \sqrt{5}}{2} = 1.618\dots$, halbuki $5/3 = 1.666\dots$ daha büyük. Demek ki $d_n/g_n$ hep $5/3$ ten ufak kalıyor. $$*****$$
Geçen sayıdaki problemlerin çözümlerine baktık. Şimdi de indirgemeli dizilerle ilgili bir-iki noktaya daha değinelim:
İlki birinci problemle ilgili. Yöntemimiz orada işlemedi. Nedeni de tahmin ettiğiniz gibi $r_1 = r_2$ olması. Genelde bakarsak iki durum söz konusu: köklerin farklı olduğu durumda geçen sayıda kullandığımız yöntem işliyor. Kökler tekrarlanıyorsa, yani çok katlı kök varsa biraz değişiklik yapmak gerekiyor. $r_1 = r_2 = \dots = r_p$ ise o zaman çözümdeki $r_1^n,\, r_2^n, \dots, r_p^n$ terimleri yerine $r_1^n,\, n r_1^n,\, n^2 r_1^n,\dots,\, n^{p – 1} r_1^n$ terimlerini almak gerekiyor. Bu dediklerimizin kanıtı burada vermek için fazla uzun ama geçen sayıda değindiğimiz “İndirgemeli Diziler” adlı kitapta var.
İkinci nokta son problemle ilgili. Burada tek bir indirgeme bağıntısı yerine iki bilinmeyenli iki indirgeme bağıntısı bulmuştuk. \begin{align*} g_{n + 1} &= g_n + d_n\\d_{n + 1} &= g_n + 2d_n~~~~~~~~~~(*) \end{align*}
Bu tür bir sistemi çözmek için çeşitli yollar var. Örneğin matrisleri kullanarak bir yöntem bulmak mümkün, daha fazla ipucu vermeden bunu meraklılara bırakalım. Sistemleri çözmenin en kısa olmasa da kolay bir yolu bilinmeyenlerden birini yoketmek. $(*)$ sisteminde ilk denklemden $d_n$’yi çekelim: $d_n = g_{n + 1} – g_n$. $n$ yerine $n + 1$ alırsak $d_{n + 1} = g_{n + 2} – g_{n + 1}$. Bu iki değeri $(*)$ daki ikinci denkleme koyarsak: $$g_{n + 2} – g_{n + 1} = g_n + 2(g_{n + 1} – g_n)$$ Toparlarsak $g_{n + 2} = 3g_{n + 1} – g_n$. Buradan önce $g_n$’yi çözer sonra da ilk denklemde yerine koyup $d_n$’yi buluruz. Yedinci problemi bir de bu yolla çözünüz!
Doğrusal indirgemeli dizilerle daha çok şey yapılabilir. Konunun ana hatlarını, temel yöntemleri öğrendiniz. Artık Olimpiyata hazır olmanız lazım.
Gelelim sıçrayan kurbağalara. Altıncı problemdeki kurbağaların benzerleri Olimpiyat hazırlık çalışmalarımızda sık sık yer aldı. Büyük Olimpik kurbağa ise 1979’da Londra’da sıçrıyordu: 1979 Olimpiyatı’nın altıncı problemi şu:
Düzgün bir sekizgenin karşı iki köşesi $A$ ve $E$ olsun. Bir kurbağa $A$ köşesinden sıçramaya başlıyor. $E$ dışındaki her köşeden kurbağa bir komşu köşeye sıçrayabiliyor. $E$ köşesine gelince kurbağa artık sıçramıyor, orada kalıyor. Kurbağanın $A$’dan $E$’ye tam $n$ sıçrayışta gidebileceği değişik yolların sayısına $a_n$ diyelim. $x = 2 + \sqrt{2},\, y = 2 – \sqrt{2}$ olmak üzere $n = 1,\, 2,\, 3, \dots$ için $$a_{2n – 1} = 0 \text{ ve } a_{2n} = \frac{1}{\sqrt{2}} (x^{n – 1} – y^{n – 1})$$ olduğunu kanıtlayınız.
İyi şanslar!
Not: Bu yazı Matematik Dünyası Dergisi arşivinden siteye eklenmiştir. Yazı ilk olarak derginin 1991 yılı 2. sayısında yer almıştır. Matematik Dünyası arşivi titiz bir çalışma ile çevrim içi platformlarda yeni okuyucularıyla buluşuyor. Bu yazıyı burada okunabilir hale getiren tüm gönüllü arşiv ekibimize teşekkür ediyoruz. Yazıyı PDF olarak okumak için PDF arşivine buradan ulaşabilirsiniz.
