Defining Recurrence
التعريف
هي معادلة تعبر عن الحد $a_n$ بدلالة واحد أو أكثر من الحدود السابقة ($a_{n-1}, a_{n-2}, \dots$).
لابد من وجود شروط ابتدائية (Initial Conditions) لتحديد القيم بدقة.
Initial: $a_0 = 3, a_1 = 5$
أمثلة شهيرة :
- Fibonacci: $f_n = f_{n-1} + f_{n-2}$ (نمو الأرانب).
- Compound Interest: $P_n = (1.11) P_{n-1}$ (الفائدة المركبة).
- Tower of Hanoi: $H_n = 2H_{n-1} + 1$.
Solving Linear Homogeneous Relations
الخوارزمية السحرية (The Algorithm)
لحل علاقة مثل $a_n = c_1 a_{n-1} + c_2 a_{n-2}$، نتبع الخطوات التالية :
عوض عن $a_n$ بـ $r^n$. نقسم على أصغر أس لنحصل على:
$$ r^2 - c_1 r - c_2 = 0 $$
أوجد جذور المعادلة ($r_1, r_2$).
• إذا كانت الجذور مختلفة: $a_n = \alpha_1 r_1^n + \alpha_2 r_2^n$.
• إذا كانت مكررة ($r_1 = r_2$): $a_n = \alpha_1 r_1^n + \alpha_2 n r_1^n$.
استخدم الشروط الابتدائية ($a_0, a_1$) لعمل نظام معادلات وحله.
Divide & Conquer Algorithms
Binary Search
نقسم المشكلة إلى نصف واحد (1 subproblem of size n/2).
الـ +2 تمثل المقارنات (Comparison) .
Merge Sort
نقسم المشكلة إلى نصفين (2 subproblems of size n/2) ثم ندمج.
الـ +n تمثل عملية الدمج (Merge).
Is it Linear Homogeneous؟
- $a_n = a_{n-1} + a_{n-2}^2$ ❌ (ليس خطياً بسبب التربيع).
- $a_n = 2a_{n-1} + 1$ ❌ (ليس متجانساً بسبب الثابت 1).
- $a_n = n a_{n-1}$ ❌ (المعاملات ليست ثابتة Constant Coefficients).
- $a_n = 3a_{n-1} - 4a_{n-2}$ ✅ (Linear, Homogeneous, Constant Coeff).
Fibonacci Closed Form
المعادلة: $r^2 - r - 1 = 0$.
الجذور: $\frac{1 \pm \sqrt{5}}{2}$ (النسبة الذهبية).
الحل العام: $f_n = \frac{1}{\sqrt{5}} (\frac{1+\sqrt{5}}{2})^n - \frac{1}{\sqrt{5}} (\frac{1-\sqrt{5}}{2})^n$.