معادله بازگشتی (Recurrence Relation)، در ریاضیات (Mathematics)

انواع معادلات (Equation) را در آموزش زیر شرح دادیم :

معادله بازگشتی (Recurrence Relation) :

🔍 تعریف: معادله بازگشتی رابطه ای است که هر جمله یک دنباله را بر حسب جملات قبلی آن تعریف می کند. این معادلات در علوم کامپیوتر، ریاضیات گسسته، و ترکیبیات بسیار رایج هستند.

\[ a_n = f(a_{n-1}, a_{n-2}, \dots, a_{n-k}) \]

📌 ویژگی های اصلی:

مرتبه: تعداد جملات قبلی که برای محاسبه جمله جدید نیاز است.

شرایط اولیه: برای شروع دنباله، به مقادیر اولین k جمله نیاز داریم.

انواع: خطی و غیرخطی، همگن و ناهمگن.

حل: برخی روابط بازگشتی (به ویژه خطی با ضرایب ثابت) را می توان به صورت تحلیلی حل کرد.

💡 مثال های متنوع:

🔹 مثال ۱ (فیبوناچی):

\[ F_n = F_{n-1} + F_{n-2} \]

، با

\[ F_0 = 0, F_1 = 1 \]

.

🔹 مثال ۲ (فاکتوریل):

\[ n! = n \cdot (n-1)! \]

، با

\[ 0! = 1 \]

.

🔹 مثال ۳ (تحلیل الگوریتم):

\[ T(n) = 2T(n/2) + n \]

(مرتب سازی ادغامی).

🔹 مثال ۴ (اعداد کاتالان):

\[ C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k} \]

، با

\[ C_0 = 1 \]

.

🔹 مثال ۵:

\[ a_n = a_{n-1} + 2^{n-1} \]

، با

\[ a_0 = 1 \]

.

🌍 کاربردها: تحلیل الگوریتم ها (زمان اجرای الگوریتم های بازگشتی)، ترکیبیات (شمارش ساختارهای ترکیبیاتی)، نظریه اعداد (دنباله های عددی)، و دینامیک جمعیت (مدل های گسسته).

📝 نکته جالب: اعداد کاتالان (که با یک رابطه بازگشتی غیرخطی تعریف می شوند) در مسائل شمارش مختلفی ظاهر می شوند، مانند تعداد روش های صحیح پرانتزگذاری، تعداد درخت های دودویی، و تعداد مسیرهای شبک های.

🧮 روش حل روابط بازگشتی خطی: برای روابط خطی با ضرایب ثابت، از معادله مشخصه استفاده می کنیم. برای روابط ناهمگن، از روش ضرایب نامعین یا تبدیل Z.

⚠️ نکته: روابط بازگشتی غیرخطی معمولا جواب تحلیلی ساده ندارند. برای تحلیل آنها از روش های عددی یا تحلیل مجانبی استفاده می شود.

📈 قضیه اصلی (Master Theorem): برای روابط بازگشتی از فرم

\[ T(n) = aT(n/b) + f(n) \]

(که در تحلیل الگوریتم های تقسیم و غلبه رایج است)، قضیه اصلی یک راه حل سریع برای یافتن مرتبه رشد T(n) ارائه می دهد.

🔬 مثال عددی: رابطه بازگشتی

\[ T(n) = 2T(n/2) + n \]

(مرتب سازی ادغامی) طبق قضیه اصلی جواب

\[ T(n) = \Theta(n \log n) \]

را دارد.