المعادلة التكرارية الخطية من الرتبة الأولى

First Order Linear Recurrence Equation

من تعريف المعادلات التكرارية الخطية فإن المعادلة التكرارية الخطية من الرتبة الأولى لها الصورة

$x_n = A(n)x_{n - 1} + B(n)$

نبدأ بالحقيقة التالية الخاصة بالمعادلة المتجانسة من الرتبة الأولى ذات المعاملات المتغيرة.

حقيقة1: المعادلة التكرارية $x_n = A(n)x_{n - 1}$ بالشرط الابتدائي $x_0 = c$ لها الحل الوحيد ( $x_n$ ) حيث $x_0 = c$ و بقية الحدود بالعلاقة

$x_n = c\prod\limits_{i = 1}^n {A(i)}$

البرهان: يتم بالاستقراء الرياضي.

مثال 1: حل المعادلة $x_{n + 1} = (n + 1)x_n ,\quad x_0 = 1$ . باستبدال m محل n=1 تصبح المعادلة $x_m = mx_{m - 1}$ ومن النظرية A(i)=i وبالتالي

$x_n = c\prod\limits_{i = 1}^n {A(i)} = \prod\limits_{i = 1}^n i = n!$

من الأساليب المتبعة في حل المعادلات التكرارية البسيطة أسلوب تخمين الحل, حيث نقوم بالتعويض عن n بأعداد طبيعية حتى يتبين لنا صيغة معينة ثم نسعى لإثبات صحتها بالاستقراء الرياضي أو غيره. مثلا لو كان لدينا العلاقة التكرارية

$x_n = 2x_{n - 1} + 5,\quad x_0 = 3$

إذا

[Unparseable or potentially dangerous latex formula. Error 5 : 1403x132]

من هذا نستطيع تخمين صورة الحد النوني

$x_n = 3 \cdot 2^n + 5(2^{n - 1} + 2^{n - 2} + \cdots + 2^2 + 2 + 1)$

ما بين القوسين متتابعة هندسية منتهية, إذا

$x_n = 3 \cdot 2^n + 5 \cdot \frac{{2^n - 1}}{{2 - 1}}$

ثم بعد ذلك نثبت صحة هذا التخمين باستخدام الاستقراء الرياضي وبذلك نكون قد حصلنا على حل المعادلة التكرارية. ما نقصده من تقديم هذا المثال هو استقراء الخصائص في المعادلة الخطية من الرتبة الأولى $x_n = 2x_{n - 1} + 5$ التي مكنت من الوصول لصورة مغلقة للمتتابعة ( $x_n$ ).

إذا أرجعنا النظر في الحساب أعلاه نستنتج أن ثبوت A,B كان كافيا تماما للوصول إلى الصورة المغلقة المتوقعة وفي النظرية التالية تعميم لهذا الأسلوب والذي ينتج منه قوانين وصيغ مباشرة للحل.

نظرية 1: المعادلة التكرارية $x_n = Ax_{n - 1} + B$ بالشرط $x_0 = c$ والثوابت A,B لها الحل الوحيد ( $x_n$ ) حيث

$x_n = cA^n + B \cdot \frac{{1 - A^n }}{{1 - A}},\quad A \ne 1$

أما إذا كانت A=1 فالحل الوحيد هو $x_n = c + Bn$ .

البرهان: لنقوم بالتعويض المباشر لتخمين الصورة المغلقة

$\begin{array}{l} x_0 = c \\ x_1 = cA + B \\ x_2 = A(cA + B) + B = cA^2 + AB + B \\ x_3 = A(cA^2 + AB + B) + B = cA^3 + A^2 B + AB + B \\ \end{array}$

إذا الصورة المتوقعة هي

$x_n = cA^n + A^{n - 1} B + A^{n - 2} B + \cdots + B = cA^n + B \cdot \frac{{A^n - 1}}{{A - 1}}$

أما إذا كانت A=1 فإن الصورة المتوقعة هي

$x_n = c + B + B + \cdots + B = c + Bn$

ما تبقى من البرهان عبارة عن خطوات تقليدية تترك للقارئ يستخدم فيها الاستقراء الرياضي في إثبات صحة التوقع الذي وصلنا إليه.

لو لاحظنا في الصورة المتوقعة خلال الإثبات أن الحد B اخذ كعامل مشترك ولذلك عندما تكون B متغيره فإننا لا نستطيع أخذ B مشترك ولذلك ستبقى الحدود بعد الحد الأول كما هي .النظرية التالية تعطي الصورة المغلقة للحل ويمكن أن تبرهن بواسطة الاستقراء الرياضي.

نظرية 2: المعادلة التكرارية $x_n = Ax_{n - 1} + B(n)$ بالشرط $x_0 = c$ والمعاملات الثابتة لها الحل الوحيد ( $x_n$ ) حيث $x_0 = c$ و بقية الحدود بالعلاقة

$x_n = cA^n + \sum\limits_{i = 1}^n {A^{n - i} } B(i)$

مسائل

* طريقة تخمين الصورة العامة تكون أحيانا مناسبة في معادلات أخرى. استخدم هذه الطريقة في إثبات أن $x_n = 3 + \ln n!$ هي الصورة المغلقة للمعادلة التكرارية