Doğrusal İndirgemeli Diziler

Yazar: Albert Erkip

Uluslararası Matematik Olimpiyadı çok sayıda ülkeden yarışmacıların katıldığı her yıl yapılan bir problem çözme yarışması. Dörtbuçuk saatlik iki bölümden oluşan yarışmanın her bölümünde üçer problem soruluyor. Problemler bir bakıma lise düzeyinde, zaten yarışmacıların üniversiteye başlamamış olmaları gerekiyor. Öte yandan bu tür problemleri çözmek için yaratıcılıktan başka hem ciddi bir özgün problem çözme alışkanlığı, hem de bazı özel ön bilgiler gerekiyor. Çoğu ülke bu yüzden seçtikleri Olimpiyat takımlarına yüklü bir eğitim programı uyguluyor.

Bu köşede sizlere geçmiş yıllarda sorulmuş bazı Olimpiyat problemlerini tanıtmak istiyoruz. Amacımız bir takım problemleri ve çözümlerini sıralayıp bunların ne zor ya da ne kolay olduklarını tartışmak değil. Bir Olimpiyat hazırlığı yapıyormuşçasına önce ön bilgileri, sonra daha kolayca problemleri verip sizleri bir Olimpiyat problemine hazırlamak. Bu hazırlık bir iki sayı sürebilecek ama sonunda problemin önemli bir kısmını çözebilecek durumda olacaksınız. Gerisi size kalmış. Bir öneri; sabırlı olun! Üç problem için dörtbuçuk saat çok uzun bir süre.

Bu sayıda doğrusal indirgemeli dizi denilen özel türden dizilere bakacağız. Bunun ne olduğunu söylemeden önce bazı örneklere bakalım. $1,4,9,16,225,\dots$ dizisi kareler dizisidir, dizinin aynı şekilde gittiğini varsayarsak $n$-inci terim için $x_n=n^2$ formülünü elde ederiz. Örneğin 38-inci terimi istiyorsak bu ${38}^2=1444$’tür. Bir de $1,2,5,26,677,\dots$ dizisine bakalım. Dikkat edersek her terimin kendinden öncekinin karesinden bir fazla olduğunu görürüz. 38-inci terim nedir? Bunu bulmak uzunca ve tatsız bir takım hesaplar gerektirir. Bu işi bir bilgisayara nasıl yaptırırız? Bilgisayara önce yukarda gözlediğimiz $x_{n+1}=(x_n{)}^2$ bağıntısını veririz, sonra da $x_1=1$ ilk teriminden başlayarak sırasıyla $n=1,n=2,\dots ,n=37$ için bağıntıyı kullanmasını isteriz. Birçok dizi bu ikinci örnektekine benzer yolla kolayca tanımlanabilir; dizinin bir terimi kendinden önceki bir veya birkaç terim cinsinden tanımlanmaktadır. Matematiksel deyişle $n+k$-ıncı terim kendinden önceki $k$ terimin bir fonksiyonu olarak verilmektedir. Bu tür dizilere indirgemeli (rekürsif) dizi, tanımlama bağıntısına da indirgeme bağıntısı denir. Biraz önce değindiğimiz gibi indirgeme bağıntıları bilgisayar kullanımında çok önemlidir.

Konumuz olan doğrusal indirgemeli diziler, indirgeme bağıntısı doğrusal olanlardır. Yani bazı $A_1,A_2,\dots ,A_k$ katsayıları için dizinin terimleri ($n=1,2,\dots$ için) $$x_{n+k}=A_1{x}_{n+k–1}+A_2{x}_{n+k–2}+\cdots +A_k{x}_n(1)$$ bağıntısını sağlarlar. Birkaç örnek verelim; $2,4,8,16,32,\dots$ geometrik dizisinde her terim kendinden öncekinin iki katıdır. Yani her $n=1,2,\dots$ için $x_{n+1}=2x_n$ bağıntısı sağlanır. Bu bağıntı $k=1,A_1=2$ olmak üzere $(1)$ türündendir. Fibonacci dizisi denilen $1,1,2,3,5,8,13,21,\dots$ dizisinde ikinciden sonra her terim kendinden önceki iki terimin toplamıdır, yani $x_{n+2}=x_{n+1}+x_n$ bağıntısı vardır. Öte yandan $4,2,6,8,14,22,\dots$ dizisi de aynı bağıntıyı sağlar. Fark başlangıç değerlerindedir. Fibonacci dizisi $1,1$ ile başlarken ikinci dizi $4,2$ terimleriyle başlamaktadır. Genellersek $(1)$ türünden bir indirgeme bağıntısı tek başına pek çok dizi tarafından sağlanır, ancak başlangıç değerleri dediğimiz ilk $k$ terim $x_1,x_2,\dots ,x_k$ değerlerini de bilirsek indirgeme bağıntısını sırasıyla $n=1,n=2,\dots$ için kullanarak tüm terimleri hesaplayabiliriz. Başka bir deyişle $(1)$ bağıntısı ve başlangıç değerleri tüm diziyi tanımlamak için yeterlidir.

Şimdi doğrusal indirgemeli bir dizinin n-inci terimini veren bir formül bulmaya çalışacağız. Gösterimde kolaylık olsun diye indirgeme bağıntısında iki terim olduğunu varsayalım, yani $k=2$ durumuna bakıyoruz, bağıntımız $$x_{n+2}=A_1{x}_{n+1}+A_2{x}_n(2)$$ türündendir. Genel $(1)$ durumu örneklerde de değineceğimiz gibi kolayca benzer şekilde bulunabilir. $(2)$ bağıntısını sağlayan geometrik dizilere bakalım. Yerine koyup sadeleştirirsek $x_n=r^n$ dizisinin $(2)$ bağıntısını sağlaması için gerek ve yeter koşulunun $$r^2–A_{1}r–A_2=0(3)$$ eşitliği olduğunu buluruz. Bir adım daha atalım, $3$ denkleminin kökleri $r_1$ ve $r_2$ olsun. $C,D$ katsayıları ne olursa olsun $$x_n=C(r_1{)}^n+D(r_2{)}^n(4)$$ dizisinin $(2)$ bağıntısını sağladığı uygun terimleri bir araya toplayarak hemen görülür. Özetlersek, $(3)$ denkleminin köklerini kullanarak çok sayıda ($C$ ve $D$ katsayılarına istediğimiz gibi seçebiliriz!) dizi bulduk.

Şimdi $(2)$ bağıntısının yanısıra dizinin başlangıç terimleri $x_1$ ve $x_2$ verilmiş olsun. Acaba bu dizi uygun $C,D$ katsayıları ile $(4)$ türünde yazılabilir mi? Uygun $C,D$ nasıl seçilebilir? Bunun için $(4)$ te sırayla $n=1$ ve $n=2$ alarak çıkanı $x_1$ ve $x_2$ ile eşitleyelim. $$\begin{array}{rl}C{r}_1+D{r}_2& =x_1\\ & (5)\\ C(r_1{)}^2+D(r_2{)}^2& =x_2\end{array}$$ sistemini elde ettik. Şansımız var da $C,D$ katsayılarını $(5)$ sisteminden çözebilirsek gerçekten de $(4)$ bize dizinin tüm terimlerini verecektir. Yaptıklarımızı bazı örneklerde izleyelim:

1. $x_1=6,x_2=0$ başlangıç değerleri ve $x_{n+2}=5x_{n+1}–6x_n$ bağıntısı ile verilen diziyi bulalım. Önce birkaç terim hesaplayalım: bağıntıda sırayla $$\begin{array}{rl}& n=1\text{ için }{x}_3=5x_2–6x_1=-36\\ & n=2\text{ için }{x}_4=5x_3–6x_2=-180\\ & n=3\text{ için }{x}_5=5x_4–6x_3=-684\end{array}$$ gibi istediğimiz sayıda terimi hesaplayabiliriz. Şimdi yukarıda geliştirdiğimiz yönteme bakalım. $(3)$ denklemi $r^2–5r+6=0$, kökleri $r_1=2,r_2=3$ olduğundan, $(5)$ sistemini buluruz: $$\begin{array}{rl}2C+3D& =6\\ 4C+9D& =0\end{array}$$ Sistemden $C=9,D=-4$ buluruz. O halde dizimiz için $x_n=9\cdot 2^n–4\cdot 3^n$ formülünü elde ettik. (Formülü $n=1,2,3,4,5$ için hesapladığımız değerlerle karşılaştırınız.)
2. Fibonacci dizisinin genel terimini bulalım. $(3)$ denklemi $r^2–r–1=0$, kökleri ise $r_{1,2}=\frac{1+\sqrt{5}}{2}$ olduğundan, $(5)$ sisteminden $C$ ve $D$ katsayılarını bulursak $n$-inci terim 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)$$ formülünü elde ederiz.
3. Bulduğumuz yöntemin kolayca genelleştirilebileceğini söylemiştik, buna bir örnek verelim:
   $x_1=2,x_2=8,x_3=8$ ve $x_{n+3}=2x_{n+2}+x_{n+1}–2x_n$ ile tanımlanan diziyi ele alalım. Burada $k=3$ olduğundan yukarıdaki adımları uygun şekilde genellememiz gerekecek. İlk olarak geometrik diziler için $(3)$ yerine $r^3–2r^2–r+2=0$ denkelmini buluruz. Kökler $1,-1,2$ olduğundan $(4)$ yerine $x_n=A+B(-1{)}^n+C\cdot 2^n$ koymalıyız. Başlangıç değerlerini alınca $(5)$ sistemi yerine $$\begin{array}{r}A–B+2C=2\\ A+B+4C=8\\ A–B+8C=8\end{array}$$ sistemini buluruz. $A=2,B=2,C=1$ olduğundan, $x_n=2+2(-1{)}^n+2^n$ olmalıdır.
4. $(1)$ türünden olmayan bazı bağıntılar biraz oynayarak istenen türe benzetilebilir. İlk terimi $4$, ondan sonraki her terimi bir öncekinin iki katından $3$ fazla diziye bakalım. Bağıntı $x_{n+1}=2x_n+3$ şeklindedir. Bu $(1)$ türünden değildir. (Neden?) Ancak bağıntıda $n$ yerine $n+1$ koyarsak $x_{n+2}=2x_{n+1}+3$ olur. Bundan ilkini çıkarırsak, $x_{n–2}–x_{n–1}=2(x_{n–1}–x_n)$, düzenlersek $x_{n+2}=3x_{n–1}–2x_n$ olur. Bu $(1)$ türündendir. Ancak başlangıç değerleri olarak $x_1$ ve $x_2$ gerekecek; $x_1=4$ verilmişti, $x_2$ için en baştaki bağıntıdan ($n=1$ için yazarak) $x_2=2x_1+3=11$ buluruz. Gerekli işlemlerden sonra $x_n=-3+7\cdot 2^{n–1}$ çıkar. Bazı dizilerin genel terimlerini bulmak için bir yöntem geliştirdik. Genelde bir dizinin yalnızca terimlerini bulmak yetmez, onunla ilgili bazı özellikleri bulmamız gerekebilir. Bu özellikler ya bulacağımıız formül yardımıyla ya da indirgeme bağıntısını doğrudan kullanarak gösterilebilir. Buna birkaç örnek verelim:
5. Fibonacci dizisinin ilk $8$ teriminden $3$ ve $6$-ncı terimler çift, diğerleri tektir. Bu acaba hep doğru olur mu, yani $3k$-ıncı terimler hep çift, diğerleri hep tek midir? Bu soruya yanıt ararken bulduğumuz $x_n$ ifadesi pek işe yaramaz. İndirgeme bağıntısı ise çok şey söyler. Kanıtlamak istediğimiz terimlerin tek-tek-çift-tek-tek-çift-$\dots$ olduğu. $x_n$ ve $x_{n+1}$ tek olsunlar. İndirgeme bağıntısından $x_{n+2}=x_{n+1}+x_n$ olacaktır, yani $x_{n+2}=$ tek $+$ tek $=$ çifttir. Devam edelim, $n$ yerine $n+1$ koyarsak, $x_{n+3}=x_{n+2}+x_{n+1}=$ çift $+$ tek $=$ tektir. Aynı yolla $x_{n+4}$’ün tek olduğu vb. gösterilir. Aslında burada (farkına varmadan) tümevarımla istediğimizi kanıtlamış olduk. (Neden?)
6. Yüksek bir merdivenin ilk basamağındaki bir kurbağa sıçrayarak yukarı çıkıyor. Kurbağa her seferinde ya bir basamak ya da iki basamak sıçrayabiliyor. Bu şekilde kurbağanın 38-inci basamağa varabilmesi için kaç değişik yol vardır?
   Problemi tanımaya çalışalım. İkinci basamağa kurbağa tek sıçrayışta çıkar. Yani ikinci basamağa çıkmak için tek yol vardır. 3. basamak için iki yol vardır, ya teker teker sıçrar, ya da iki basamak birden sıçrar. Bu şekilde devam etmeye çalışırsak, 4. basamakta bile hesap karışıyor. Mademki konumuz diziler, bir dizi tanımlayalım. $n$-inci basamağa çıkan değişik yolların sayısına $y_n$ diyelim, $y_2=1$, $y_3=2$ olduğunu bulduk. ($y_1$ ne olabilir?) $y_{n+2}$’ye bakalım. Kurbağa $n+2$-nci basamağa nasıl çıkabilir? Bir sıçrayış önce ya $n+1$ ya da $n$-inci basamakta olacaktı. O halde $n+2$’ye varan iki tür yol vardır, ya $n$’ye gelip çift sıçrayan yollar (bunların sayısı $y_n$ idi), ya da $n+1$’e gelip son adımda tek sıçrayan yollar (bunların da sayısı $y_{n+1}$ idi). O halde $y_{n+2}=y_{n+1}+y_n$ bağıntısını bulduk. Artık $y_{38}$’i hesaplayabiliriz.
7. Fibonacci dizisinin ardışık terimlerinden büyüğün küçüğe oranına bakalım. Bu oranlar sırasıyla $1/1=13/2=1.55/3=1.6668/5=1.613/8=1.62521/13=1.61534/21=1.619$ diye gitmekte. Oranların $1.618$ gibi bir sayıya yaklaştığını görüyoruz. Bunu kanıtlayabilir miyiz? $x_n$ için yukarıda bulduğumuz ifadeyi yakından inceleyelim. $\frac{1–\sqrt{5}}{2}$ sayısı -1 ile 0 arasındadır, $n$-inci kuvvetleri $n$ büyüdükçe sıfıra yaklaşır. O halde büyük $n$ değerleri için $x_n$ terimi $\frac{1}{\sqrt{5}}{\left(\frac{1+\sqrt{5}}{2}\right)}^n$ sayısına yakındır, yani terimlerin birbirine oranı $\frac{1+\sqrt{5}}{2}=1.61803\dots$ sayısına yaklaşır. Altın oran adı verilen bu sayının Eski Yunan’dan beri sanat ve mimarlıkta önemli yeri vardır. Klasik mimarlıkta kapı, pencere gibi dikdörtgen formların kenarları hep bu oranda yapılır.

Fibonacci dizisinin yukarıdakilerden başka pek çok ilginç özelliği var. Adını 13. yüzyıl başlarında yaşamış İtalyan matematikçisi Leonardo Fibonacci’den alan diziye aynı zamanda doğada da sık sık rastlanmakta. Bu ilginç dizi hakkında daha fazla bilgi almak için Nazif Tepedelenlioğlu’nun “Kim Korkar Matematikten” (Bilim ve Sanat Yayınları, 1983) adlı kitabına bakmanızı öneririz. İndirgemeli dizilerin burada değinmediğimiz özellikleri için ise A.I.Markuschewitz’in, Türkçeye çevirisi yapılmış bulunan “İndirgemeli Diziler” (Matematik Derneği Yayınları, Sayı: 18, 1963) kitabına bakabilirsiniz.

Bu yazıyı aralarında bazı Olimpiyat hazırlık problemleri bulunan sorularla bitirelim. Olimpiyat problemimiz gelecek sayıda çıkacak!

Sorular

1. $x_1=1$, $x_2=3$, $x_{n+2}=2x_{n+1}–x_n$ bağıntısıyla verilen diziyi bulunuz. Yöntemimiz işledi mi? $(5)$ sistemi için ‘şansımız varsa’ $C$, $D$’yi çizebiliriz demiştik; eğer $r_1\ne r_2$ ise şansımızın olduğunu gösteriniz. $k=3$ durumunda (örnek 3’teki gibi) benzer bir şey kanıtlayabilir misiniz?
2. $x_1=1$, $x_2=10$ ve $x_{n+2}=(x_{n+1}{)}^3/(x_n{)}^2$ bağıntısıyla verilen diziyi bulunuz.
3. Fibonacci dizisinde hangi terimler 3’le tam olarak bölünebilir? Hangi terimler 5’le tam olarak bölünebilir? Yanıtlarınızı kanıtlayınız.
4. Fibonacci dizisinden terimlerin birler basamağındaki rakamlarla yeni bir dizi oluşturalım. Bu dizi bir süre sonra kendini tekrarlar mı?
5. Elimizdeki $p_0$ milyon lirayı bankaya yatırmak istiyoruz. A bankası yılda $$ net faiz veriyor, ancak hizmetine karşılık her yıl $1.000.000$ lira ücret kesiyor. B bankası yılda net $$ faiz veriyor ama ücret almıyor. Hangi bankayı tercih edelim? Parayı bankada çok uzun süre tutacaksak tercihimiz ne olmalı? (Tercihimiz $p_0$ miktarına ve bankada tutacağımız süreye bağlı olacak. Soruda bir de açıklanmamış bir şey var; A bankası önce faiz verip sonra mı ücretini alıyor – ya da tersini mi yapıyor? Hangi durum bizim için daha iyi?)
6. Bir merdivenin ilk basamağındaki kurbağa sıçrayarak yukarı çıkıyor. Kurbağa her sıçrayışta eşit olasılıkla ya 1 basamak, ya da 2 basamak sıçrıyor. 38-inci basamak kırık; kurbağanın bu basamağa düşme olasılığı nedir, bu basamağa düşmeden 75-inci basamağa gelme olasılığı nedir?
7. Üçgenler gezegeninde iki tür üçgen yaşıyor; geniş açılılar ($G$) ve dar açılılar ($D$). Her yılın son günü üçgenler bölünüyorlar; öyle ki her $G$ bir $G$ ve bir $D$’ye, her $D$ ise bir $G$ ve iki $D$’ye bölünüyor. Yıl boyunca büyüyen üçgenler ertesi yıl sonunda yine aynı şekilde bölünüyorlar. Gezegenin iki efsanesi var. Birine göre yaşam tek bir $D$ ile başlamış. İkinci efsane ise $D$’lerin sayısının $G$’lerinkine oranı $5/3$’ten büyük olursa gezegen patlayacak diyor. Gezegenin patlama tehlikesi var mı, varsa ne zaman patlayabilir?