Advanced Counting: Recurrence Relations

Giriş

Recurrence Relations (Tekrarlayan İlişkiler), matematikte ve özellikle Discrete Mathematics (Ayrık Matematik) alanında önemli bir kavramdır. Bir dizinin terimlerini önceki terimlerine dayalı olarak tanımlamak, karmaşık dizileri anlamamızı ve çözmemizi sağlar. Bu makalede, recurrence relation kavramını, derecesini, başlangıç koşullarını ve genel terimin nasıl bulunacağını inceleyeceğiz.

Genel Terim ve Recurrence Relation Karşılaştırması

Bir diziyi tanımlamanın en bilinen yollarından biri, genel terimi (general term) kullanmaktır. Genel terim, dizinin her bir terimini doğrudan hesaplamamıza olanak tanıyan bir fonksiyon şeklinde ifade edilir. Örneğin:

$$a_n = 3n + 7$$

Bu genel terimi kullanarak, herhangi bir $n$ değerine karşılık gelen $a_n$ terimini kolayca bulabiliriz. Örneğin:

• $a_{40} = 3 \times 40 + 7 = 127$
• $a_{12} = 3 \times 12 + 7 = 43$

Ancak, dizileri tanımlamanın başka bir yolu da recurrence relation (tekrarlayan ilişki) kullanmaktır. Recurrence relation, bir dizinin terimlerini önceki terimlere bağlı olarak tanımlar.

Recurrence Relation Nedir?

Recurrence relation, bir dizinin her bir teriminin, önceki terim(ler)e bağlı olarak ifade edilmesidir. Örneğin:

$$a_n = 2a_{n-1} + 3a_{n-2}$$

Bu ifade, $n$'inci terimin, bir önceki terim ($a_{n-1}$) ve iki önceki terim ($a_{n-2}$) kullanılarak hesaplandığını gösterir. Bu tür bir tanımlamada, bir terimi bulmak için önceki terimleri bilmemiz gerekir.

Örnek

Eğer başlangıç koşulları olarak $a_0 = 1$ ve $a_1 = 3$ verilirse, $a_2$'yi bulabiliriz:

$$a_2 = 2a_{1} + 3a_{0} = 2 \times 3 + 3 \times 1 = 6 + 3 = 9$$

Benzer şekilde $a_3$'ü hesaplayabiliriz:

$$a_3 = 2a_{2} + 3a_{1} = 2 \times 9 + 3 \times 3 = 18 + 9 = 27$$

Bu şekilde, dizinin terimlerini adım adım hesaplayabiliriz. Ancak, dikkat edin ki terimleri bulmak genel terime göre daha fazla işlem gerektirir.

Recurrence Relation'ın Derecesi (Degree) ve Başlangıç Koşulları

Bir recurrence relation'ın derecesi (degree veya order), terimin en fazla kaç önceki terime bağlı olduğunu belirtir. Örneğin:

• $a_n = 2a_{n-1} + 3a_{n-2}$

Bu recurrence relation'ın derecesi 2'dir, çünkü $a_n$, $a_{n-1}$ ve $a_{n-2}$ terimlerine bağlıdır.

Derece, $n$ ile en düşük indeksli terim arasındaki farktır. Yani $n - (n - k) = k$ ise, derece $k$'dır.

Neden Başlangıç Koşulları Gerekir?

Derecesi $k$ olan bir recurrence relation'ı çözebilmek için $k$ adet başlangıç koşuluna (initial conditions) ihtiyacımız vardır. Bu başlangıç koşulları, dizinin ilk $k$ terimini belirler ve diğer terimlerin hesaplanmasına olanak sağlar.

Örneğin, derecesi 2 olan bir recurrence relation için $a_0$ ve $a_1$ gereklidir.

Başka Bir Örnek

Derecesi 3 olan bir recurrence relation düşünelim:

$$a_n = a_{n-1} + a_{n-3}$$

Bu durumda, $a_n$ terimi, bir önceki terim ($a_{n-1}$) ve üç önceki terim ($a_{n-3}$) ile tanımlanır. Burada derece 3'tür çünkü en fazla üç önceki terime bağlıdır.

Bu recurrence relation'ı çözmek için $a_0$, $a_1$ ve $a_2$ başlangıç koşullarına ihtiyacımız vardır.

Recurrence Relation Çözümü ve Genel Terim

Recurrence relation'ların asıl amacı, dizinin genel terimini (general term) bulmaktır. Genel terim, dizinin herhangi bir terimini, önceki terimlere bağlı olmaksızın doğrudan hesaplamamızı sağlar.

Bir recurrence relation verildiğinde, "Solve the recurrence relation" ifadesi, bizden $a_n$'i, yani genel terimi bulmamızı ister.

Örnek Recurrence Relation

Verilen recurrence relation:

$$a_n = 4a_{n-1} + 2a_{n-3}$$

Başlangıç koşulları:

• $a_0 = 6$
• $a_1 = 8$
• $a_2 = 8$

Burada derece 3'tür çünkü $a_n$, $a_{n-1}$ ve $a_{n-3}$ terimlerine bağlıdır.

Terimlerin Hesaplanması

$a_3$'ü bulmak için:

$$a_3 = 4a_{2} + 2a_{0} = 4 \times 8 + 2 \times 6 = 32 + 12 = 44$$

$a_4$'ü bulmak için:

$$a_4 = 4a_{3} + 2a_{1} = 4 \times 44 + 2 \times 8 = 176 + 16 = 192$$

Bu şekilde devam ederek terimleri bulabiliriz. Ancak amacımız genel terimi bulmaktır.

Sonuç

Recurrence Relations, dizileri önceki terimlere dayalı olarak tanımlamamızı sağlayan güçlü bir araçtır. Derecesine bağlı olarak yeterli sayıda başlangıç koşulu ile dizinin tüm terimlerini hesaplayabiliriz. Ancak, asıl hedefimiz dizinin genel terimini bulmaktır. Genel terim sayesinde, herhangi bir terimi doğrudan ve kolayca hesaplayabiliriz.

İlerleyen bölümlerde, farklı yöntemlerle recurrence relation'ların nasıl çözüleceğini ve genel terimin nasıl bulunacağını inceleyeceğiz.