الدوال المولِّدة

توجد في الرياضيات المتقطعة (Discrete Mathematics) أداة بالغة القوة تُستخدم لمعالجة المتتاليات (Sequences)، وتُسمّى الدالة المولِّدة (Generating Function). وفكرتها هي الآتية: بدلًا من النظر إلى متتالية لا نهائية (مثلًا: $2, 3, 5, 8, 12, \ldots$)، ننظر إلى دالة واحدة ترمِّز المتتالية. لكنها ليست دالة تُعطي الحد ذا الفهرس $n$ بوصفه ناتجًا. بل هي دالة «تعرض» متسلسلة القوى (Power Series) الخاصة بها، كما في التفاضل والتكامل، حدود المتتالية. فمثلًا، ننظر إلى متسلسلة القوى $2 + 3x + 5x^2 + 8x^3 + 12x^4 + \cdots$، التي تعرض المتتالية $2, 3, 5, 8, 12, \ldots$ على هيئة معاملات (Coefficients).

متسلسلة القوى اللانهائية ليست سوى مجموع لا نهائي لحدود من الصورة $c_nx^n$، حيث $c_n$ ثابت ما. ولذلك يمكن أن نكتب متسلسلة القوى هكذا:

$$\begin{equation*} \sum_{k=0}^\infty c_k x^k\text{.} \end{equation*}$$

أو نكتبها موسَّعة هكذا:

$$\begin{equation*} c_0 + c_1x + c_2x^2 + c_3x^3 + c_4x^4 + c_5x^5 + \cdots\text{.} \end{equation*}$$

عندما ننظر إلى متسلسلة قوى كهذه في سياق الدوال المولِّدة، نسمّيها متسلسلة مولِّدة (Generating Series). وتولِّد المتسلسلة المولِّدة المتتالية:

$$\begin{equation*} c_0, c_1, c_2, c_3, c_4, c_5, \ldots\text{.} \end{equation*}$$

بعبارة أخرى، المتتالية التي تولِّدها متسلسلة مولِّدة ليست سوى متتالية معاملات كثيرة الحدود (Polynomial) اللانهائية.

مثال 6.1.1.

ما المتتالية التي تمثّلها المتسلسلة المولِّدة $3 + 8x^2 + x^3 + \frac{x^5}{7} + 100x^6 + \cdots\text{?}$

الحل. نقرأ ببساطة معامل كل حد من حدود $x^n$. إذن $a_0 = 3$، لأن معامل $x^0$ هو 3 (إذ إن $x^0 = 1$، فهذا هو الحد الثابت). فما قيمة $a_1$؟ إنها ليست 8، لأن 8 معامل $x^2$، ومن ثم فإن 8 هي الحد $a_2$ في المتتالية. لإيجاد $a_1$، علينا البحث عن معامل $x^1$، وهو في هذه الحالة 0. إذن $a_1 = 0\text{.}$ وبالمتابعة، نجد $a_2 = 8\text{,}$ و$a_3 = 1\text{,}$ و$a_4 = 0\text{,}$ و$a_5 = \frac{1}{7}\text{.}$ وهكذا نحصل على المتتالية:

$$\begin{equation*} 3, 0, 8, 1, 0, \frac{1}{7}, 100, \ldots\text{.} \end{equation*}$$

لاحظ أننا نبدأ متتاليتنا دائمًا بالحد $a_0$ عند مناقشة الدوال المولِّدة.

قد تسأل الآن، على نحو طبيعي جدًا، لماذا نفعل شيئًا كهذا. أحد الأسباب هو أن ترميز متتالية بمتسلسلة قوى يساعدنا على تتبّع موضع كل حد في المتتالية. فمثلًا، إذا كتبنا المتتالية $1, 3, 4, 6, 9, \ldots, 24, 41,\ldots$، يستحيل تحديد موضع الحد $24$ (حتى لو اتفقنا على أن الحد الأول يفترض أن يكون $a_0$). لكن إذا كتبنا المتسلسلة المولِّدة بدلًا من ذلك، فسنحصل على $1 + 3x + 4x^2 + 6x^3 + 9x^4 + \cdots + 24 x^{17} + 41 x^{18} + \cdots\text{.}$ أصبح من الواضح الآن أن 24 هو الحد ذو الفهرس 17 في المتتالية (أي إن $a_{17} = 24$). وبالطبع، للحصول على هذه الفائدة، كان بإمكاننا عرض متتاليتنا بطرق كثيرة، مثل $\fbox{1}_0 \fbox{3}_1 \fbox{4}_2 \fbox{6}_3 \fbox{9}_4 \cdots \fbox{24}_{17}\fbox{41}_{18}\cdots\text{,}$ لكننا لا نفعل ذلك. والسبب أن المتسلسلة المولِّدة تشبه متسلسلة قوى عادية (مع أننا نفسّرها بطريقة مختلفة)، ولذلك يمكننا أن نفعل بها ما نفعله عادة بمتسلسلات القوى، مثل كتابة ما تتقارب إليه.

مثلًا، نعرف من التفاضل والتكامل أن متسلسلة القوى $1 + x + \frac{x^2}{2} + \frac{x^3}{6} + \frac{x^4}{24} + \cdots + \frac{x^n}{n!} + \cdots$ تتقارب إلى الدالة $e^x\text{.}$ لذا يمكننا استخدام $e^x$ وسيلةً للحديث عن متتالية معاملات متسلسلة القوى الخاصة بالدالة $e^x\text{.}$ عندما نكتب دالة لطيفة موجزة لها متسلسلة قوى لا نهائية ننظر إليها بوصفها متسلسلة مولِّدة، نسمّي تلك الدالة دالة مولِّدة. وفي هذا المثال نقول:

$$\begin{equation*} 1, 1, \frac{1}{2}, \frac{1}{6}, \frac{1}{24}, \ldots, \frac{1}{n!}, \ldots \mbox{ لها الدالة المولِّدة } e^x\text{.} \end{equation*}$$

قسم فرعي: بناء الدوال المولِّدة

مثال $e^x$ محدَّد جدًا. لدينا متتالية غريبة بعض الشيء، والسبب الوحيد لمعرفتنا دالتها المولِّدة هو أننا نعرف مصادفةً متسلسلة تايلور (Taylor Series) الخاصة بالدالة $e^x\text{.}$ هدفنا الآن جمع بعض الأدوات لبناء الدالة المولِّدة لمتتالية معيّنة معطاة.

لنرَ ما الدوال المولِّدة لبعض المتتاليات البسيطة جدًا. أبسطها على الإطلاق: 1، 1، 1، 1، 1، …. كيف تبدو المتسلسلة المولِّدة؟ إنها ببساطة $1 + x + x^2 + x^3 + x^4 + \cdots\text{.}$ هل يمكننا الآن إيجاد صيغة مغلقة (Closed Formula) لمتسلسلة القوى هذه؟ نعم! هذه المتسلسلة بالتحديد ليست في الحقيقة سوى متسلسلة هندسية (Geometric Series) أساسها (Common Ratio) $x\text{.}$ لذا، إذا استخدمنا تقنية «الضرب والإزاحة والطرح» من القسم 4.4، فلدينا:

$$\begin{align*} S \amp = 1 + x + x^2 + x^3 + \cdots\\ \underline{-\qquad xS} \amp \underline{\,\, = ~~~~~~ x + x^2 + x^3 + x^4 + \cdots}\\ (1-x)S \amp = 1 \end{align*}$$

وعليه نرى أن:

$$\begin{equation*} 1 + x + x^2 + x^3 \cdots = \dfrac{1}{1-x}\text{.} \end{equation*}$$

قد تتذكر من التفاضل والتكامل أن هذا لا يصح إلا على فترة التقارب (Interval of Convergence) لمتسلسلة القوى، أي في هذه الحالة عندما يكون $|x| \lt 1\text{.}$ وهذا صحيح هنا أيضًا، لكنه لا يهمنا. لن نعوّض أبدًا بأي قيمة عن $x$، ولذلك ما دامت توجد قيمة ما لـ$x$ تتفق عندها الدالة المولِّدة والمتسلسلة المولِّدة، فهذا يرضينا. وفي هذه الحالة نحن راضون.

$1,1,1,\ldots$.

الدالة المولِّدة للمتتالية $1,1,1,1,1,1,\ldots$ هي $\dfrac{1}{1-x}$.

لنستخدم هذه الدالة المولِّدة الأساسية لإيجاد دوال مولِّدة لمزيد من المتتاليات. ماذا لو استبدلنا $x$ بـ$-x$؟ نحصل على:

$$\begin{equation*} \frac{1}{1+x} = 1 - x + x^2 - x^3 + \cdots \mbox{ التي تولِّد } 1, -1, 1, -1, \ldots\text{.} \end{equation*}$$

إذا استبدلنا $x$ بـ$3x$، نحصل على:

$$\begin{equation*} \frac{1}{1-3x} = 1 + 3x + 9x^2 + 27x^3 + \cdots \mbox{ التي تولِّد } 1, 3, 9, 27, \ldots\text{.} \end{equation*}$$

باستبدال $x$ في $\frac{1}{1-x}$، يمكننا الحصول على دوال مولِّدة لمتتاليات متنوعة، ولكن ليس لكل المتتاليات. مثلًا، لا يمكنك التعويض بأي شيء عن $x$ للحصول على الدالة المولِّدة للمتتالية $2,2,2,2, \ldots\text{.}$ لكننا لم نفقد سبيلنا بعد. لاحظ أن كل حد في $2, 2, 2, 2, \ldots$ ينتج من ضرب حدود $1, 1, 1, 1, \ldots$ بالثابت 2. لذا اضرب الدالة المولِّدة في 2 أيضًا.

$$\begin{equation*} \frac{2}{1-x} = 2 + 2x + 2x^2 + 2x^3 + \cdots \mbox{ التي تولِّد } 2, 2, 2, 2, \ldots\text{.} \end{equation*}$$

وبالمثل، لإيجاد الدالة المولِّدة للمتتالية $3, 9, 27, 81, \ldots\text{,}$ نلاحظ أن هذه المتتالية تنتج من ضرب كل حد في $1, 3, 9, 27, \ldots$ في 3. ولأننا نعرف الدالة المولِّدة للمتتالية $1, 3, 9, 27, \ldots$، يمكننا أن نقول:

$$\begin{equation*} \frac{3}{1-3x} = 3\cdot 1 + 3\cdot 3x + 3\cdot 9x^2 + 3\cdot 27x^3 + \cdots \mbox{ التي تولِّد } 3, 9, 27, 81, \ldots\text{.} \end{equation*}$$

وماذا عن المتتالية $2, 4, 10, 28, 82, \ldots\text{?}$ تزيد الحدود هنا دائمًا بمقدار 1 على قوى العدد 3. أي إننا جمعنا المتتاليتين $1,1,1,1,\ldots$ و$1,3,9, 27,\ldots$ حدًا بحد. ولذلك يمكننا الحصول على دالة مولِّدة بجمع الدالتين المولِّدتين المقابلتين:

$$\begin{align*} 2 + 4x + 10x^2 + 28x^3 + \cdots \amp = (1 + 1) + (1 + 3)x + (1 + 9)x^2 + (1 + 27)x^3 + \cdots\\ \amp = 1 + x + x^2 + x^3 + \cdots + 1 + 3x + 9x^2 + 27x^3 + \cdots\\ \amp = \frac{1}{1-x} + \frac{1}{1-3x} \end{align*}$$

ولا تتوقف المتعة هنا: إذا استبدلنا $x$ في دالتنا المولِّدة الأصلية بـ$x^2$، نحصل على:

$$\begin{equation*} \frac{1}{1-x^2} = 1 + x^2 + x^4 + x^6\cdots \mbox{ التي تولِّد } 1, 0, 1, 0, 1, 0, \ldots\text{.} \end{equation*}$$

كيف يمكننا الحصول على $0,1,0,1,0,1,\ldots\text{?}$ ابدأ بالمتتالية السابقة ثم أزِحها (Shift) بمقدار 1. لكن كيف تفعل ذلك؟ لنرَ كيف تعمل الإزاحة، بمحاولة إيجاد الدالة المولِّدة للمتتالية $0, 1, 3, 9, 27, \ldots\text{.}$ نعرف أن $\frac{1}{1-3x} = 1 + 3x + 9x^2 + 27x^3 + \cdots\text{.}$ للحصول على الصفر في البداية، نحتاج إلى أن تكون المتسلسلة المولِّدة على الصورة $x + 3x^2 + 9x^3 + 27x^4+ \cdots$ (بحيث لا يوجد حد ثابت). والضرب في $x$ يحقّق هذا الأثر. لذا فإن الدالة المولِّدة للمتتالية $0, 1, 3, 9, 27, \ldots$ هي $\frac{x}{1-3x}\text{.}$ وينجح هذا أيضًا في الحصول على الدالة المولِّدة للمتتالية $0,1,0,1,0,1,\ldots\text{:}$

$$\begin{equation*} \frac{x}{1-x^2} = x + x^3 + x^5 + \cdots \mbox{ التي تولِّد } 0, 1, 0, 1, 0 , 1 \ldots\text{.} \end{equation*}$$

ماذا لو جمعنا المتتاليتين $1,0,1,0,1,0,\ldots$ و$0,1,0,1,0,1,\ldots$ حدًا بحد؟ ينبغي أن نحصل على $1,1,1,1,1,1\ldots\text{.}$ ماذا يحدث عندما نجمع الدالتين المولِّدتين؟ تنجح الطريقة (جرّبها)!

$$\begin{equation*} \frac{1}{1-x^2} + \frac{x}{1-x^2} = \frac{1}{1-x}\text{.} \end{equation*}$$

إليك حيلة خفية: ماذا يحدث إذا أخذت المشتقة (Derivative) للدالة $\frac{1}{1-x}\text{?}$ نحصل على $\frac{1}{(1-x)^2}\text{.}$ من جهة أخرى، إذا اشتققنا متسلسلة القوى حدًا بحد، نحصل على $(1 + x + x^2 + x^3 + \cdots)' = 1 + 2x + 3x^2 + 4x^3 + \cdots$، وهي المتسلسلة المولِّدة للمتتالية $1, 2, 3, 4, \ldots\text{.}$ وهذا يعني:

$1,2,3,\ldots$.

الدالة المولِّدة للمتتالية $1, 2, 3, 4, 5, \ldots$ هي $\d\frac{1}{(1-x)^2}\text{.}$

خذ مشتقة ثانية: $\frac{2}{(1-x)^3} = 2 + 6x + 12x^2 + 20x^3 + \cdots\text{.}$ إذن $\frac{1}{(1-x)^3} = 1 + 3x + 6x^2 + 10x^3 + \cdots$ دالة مولِّدة للأعداد المثلثية (Triangular Numbers)، $1,3,6,10\ldots$ (مع أن لدينا هنا $a_0 = 1$، بينما عادةً يكون $T_0 = 0$).

قسم فرعي: أخذ الفروق (Differencing)

رأينا كيف نجد دوال مولِّدة انطلاقًا من $\frac{1}{1-x}$ باستخدام الضرب (بثابت أو بـ$x$)، والتعويض، والجمع، والاشتقاق. لاستخدام كل من هذه العمليات، عليك أن تلاحظ طريقة لتحويل المتتالية $1,1,1,1,1\ldots$ إلى المتتالية التي تريدها. وهذا ليس سهلًا دائمًا. كما أنه ليس في الحقيقة الطريقة التي حلّلنا بها المتتاليات. أحد الأمور التي تناولناها كثيرًا هو متتالية الفروق بين حدود متتالية. وسيتبيّن أن هذا مفيد أيضًا في إيجاد الدوال المولِّدة. غالبًا ما تكون متتالية الفروق أبسط من المتتالية الأصلية. لذا، إذا عرفنا دالة مولِّدة للفروق، نود استخدام ذلك لإيجاد دالة مولِّدة للمتتالية الأصلية.

مثلًا، انظر إلى المتتالية $2, 4, 10, 28, 82, \ldots\text{.}$ كيف يمكننا الانتقال إلى متتالية الفروق الأولى (First Differences): $2, 6, 18, 54,\ldots\text{?}$ نريد طرح 2 من 4، و4 من 10، و10 من 28، وهكذا. لذا، إذا طرحنا (حدًا بحد) المتتالية $0, 2, 4, 10, 28,\ldots$ من $2, 4, 10, 28\ldots\text{,}$ نكون قد حقّقنا المطلوب. يمكننا الحصول على الدالة المولِّدة للمتتالية $0,2,4,10,28,\ldots$ من الدالة المولِّدة للمتتالية $2,4,10,28\ldots$ بالضرب في $x\text{.}$ استخدم $A$ لتمثيل الدالة المولِّدة للمتتالية $2, 4, 10, 28, 82, \ldots$. عندئذ:

$$\begin{align*} A \amp = 2 + 4x + 10x^2 +28x^3 + 82x^4 + \cdots\\ \underline{-\qquad xA} \amp \underline{\,\,= 0 + 2x + 4x^2 + 10x^3 + 28 x^4 + 82x^5 + \cdots}\\ (1-x)A \amp = 2 + 2x + 6x^2 + 18x^3 + 54x^4 + \cdots \end{align*}$$

مع أننا لا نحصل على متتالية الفروق بالضبط، فإننا نحصل على شيء قريب منها. في هذه الحالة بالتحديد، نعرف الدالة المولِّدة $A$ بالفعل (وجدناها في القسم السابق)، لكننا سنستخدم غالبًا تقنية أخذ الفروق هذه لإيجاد $A$: إذا كانت لدينا الدالة المولِّدة لمتتالية الفروق، أمكننا بعد ذلك حل المعادلة لإيجاد $A\text{.}$

مثال 6.1.2.

أوجد دالة مولِّدة للمتتالية $1, 3, 5, 7, 9,\ldots\text{.}$

الحل. لاحظ أن متتالية الفروق ثابتة. نعرف كيف نجد الدالة المولِّدة لأي متتالية ثابتة. لذا لنرمز إلى الدالة المولِّدة للمتتالية $1, 3, 5, 7, 9, \ldots$ بالرمز $A\text{.}$ لدينا:

$$\begin{align*} A \amp = 1 + 3x + 5x^2 + 7x^3 + 9x^4 + \cdots\\ \underline{-\qquad xA} \amp \underline{\,\,= 0 + x + 3x^2 + 5x^3 + 7x^4 + 9x^5 + \cdots}\\ (1-x)A \amp = 1 + 2x + 2x^2 + 2x^3 + 2x^4 + \cdots \end{align*}$$

نعرف أن $2x + 2x^2 + 2x^3 + 2x^4 + \cdots = \dfrac{2x}{1-x}\text{.}$ ومن ثم:

$$\begin{equation*} (1-x)A = 1 + \frac{2x}{1-x}\text{.} \end{equation*}$$

حل الآن لإيجاد $A$:

$$\begin{equation*} A = \frac{1}{1-x} + \frac{2x}{(1-x)^2} = \frac{1+x}{(1-x)^2}\text{.} \end{equation*}$$

هل هذا معقول؟ قبل أن نبسّط الكسرين إلى كسر واحد، كنا نجمع الدالة المولِّدة للمتتالية $1,1,1,1,\ldots$ مع الدالة المولِّدة للمتتالية $0, 2, 4, 6, 8, 10, \ldots$ (تذكّر أن $\frac{1}{(1-x)^2}$ تولِّد $1,2,3,4,5, \ldots\text{,}$ وأن الضرب في $2x$ يزيحها، فيضع الصفر في البداية ويضاعف كل حد). إذا جمعنا هاتين المتتاليتين حدًا بحد، نحصل على المتتالية الصحيحة $1,3,5,7, 9, \ldots\text{.}$

بعد أن أصبحت لدينا دالة مولِّدة للأعداد الفردية، يمكننا استخدامها لإيجاد الدالة المولِّدة للمربعات:

مثال 6.1.3.

أوجد الدالة المولِّدة للمتتالية $1, 4, 9, 16, \ldots\text{.}$ لاحظ أننا نأخذ $1 = a_0\text{.}$

الحل. نسمّي الدالة المولِّدة للمتتالية $A$ مرة أخرى. باستخدام أخذ الفروق:

$$\begin{align*} A \amp = 1 + 4x + 9x^2 + 16x^3 + \cdots\\ \underline{-\qquad xA} \amp \underline{\,\, = 0 + x + 4x^2 + 9x^3 + 16x^4 + \cdots}\\ (1-x)A \amp = 1 + 3x + 5x^2 + 7x^3 + \cdots \end{align*}$$

بما أن $1 + 3x + 5x^2 + 7x^3 + \cdots = \d\frac{1+x}{(1-x)^2}$، فإن لدينا $A = \d\frac{1+x}{(1-x)^3}\text{.}$

في كل مثال من الأمثلة السابقة، أوجدنا الفرق بين الحدود المتتالية، فحصلنا على متتالية فروق نعرف دالة مولِّدة لها. ويمكننا تعميم هذا على علاقات أكثر تعقيدًا بين حدود المتتالية. فمثلًا، ماذا لو عرفنا أن المتتالية تحقّق العلاقة العودية (Recurrence Relation) $a_n = 3a_{n-1} - 2a_{n-2}\text{?}$ بعبارة أخرى، إذا أخذنا حدًا من المتتالية وطرحنا منه ثلاثة أمثال الحد السابق ثم أضفنا مثلي الحد الذي يسبق ذلك، نحصل على 0 (لأن $a_n - 3a_{n-1} + 2a_{n-2} = 0$). يصح هذا لكل حدود المتتالية ما عدا الحدين الأولين. لذا، بعد الحدين الأولين، تكون متتالية نتائج هذه الحسابات متتالية أصفار، ونعرف بالتأكيد دالة مولِّدة لها.

مثال 6.1.4.

تحقّق المتتالية $1, 3, 7, 15, 31, 63, \ldots$ العلاقة العودية $a_n = 3a_{n-1} - 2a_{n-2}\text{.}$ أوجد الدالة المولِّدة للمتتالية.

الحل. سمِّ الدالة المولِّدة للمتتالية $A\text{.}$ لدينا:

$$\begin{align*} A \amp = 1 + 3x + 7x^2 + 15x^3 + 31x^4 + \cdots + a_nx^n + \cdots\\ -3xA \amp = 0 - 3x - 9x^2 - 21x^3 - 45x^4 - \cdots - 3a_{n-1}x^n - \cdots\\ \underline{+~~~2x^2A_{~}^{~^{~}}} \amp \underline{\,\, = 0 + 0x + 2x^2 + 6x^3 + 14x^4 + \cdots + 2a_{n-2}x^n + \cdots}\\ (1-3x+2x^2)A \amp = 1 \end{align*}$$

ضربنا $A$ في $-3x$، مما يزيح كل حد موضعًا واحدًا ويضربه في $-3\text{.}$ وفي السطر الثالث، ضربنا $A$ في $2x^2$، مما أزاح كل حد موضعين وضربه في 2. عندما نجمع الحدود المتناظرة، نأخذ كل حد، ونطرح منه ثلاثة أمثال الحد السابق، ونضيف مثلي الحد الذي يسبق ذلك. يحدث هذا لكل حد بعد $a_1$، لأن $a_n - 3a_{n-1} + 2a_{n-2} = 0\text{.}$ عمومًا، قد يتبقّى لدينا حدّان من بداية المتسلسلة المولِّدة، مع أن الحد الثاني في هذه الحالة يصادف أنه 0 أيضًا.

كل ما نحتاج إليه الآن هو الحل لإيجاد $A$:

$$\begin{equation*} A = \frac{1}{1 - 3x + 2x^2}\text{.} \end{equation*}$$

قسم فرعي: الضرب والمجاميع الجزئية (Partial Sums)

ماذا يحدث للمتتاليات عندما تضرب دالتين مولِّدتين؟ لنرَ: $A = a_0 + a_1x + a_2x^2 + \cdots$ و$B = b_0 + b_1x + b_2x^2 + \cdots\text{.}$ لضرب $A$ و$B$، نحتاج إلى إجراء كثير من عمليات التوزيع (هل هي قاعدة ضرب الأول والخارجي والداخلي والأخير (FOIL) ولكن بصورة لا نهائية؟)، لكن تذكّر أننا سنجمع الحدود المتشابهة، ولا نحتاج إلا إلى كتابة الحدود القليلة الأولى لرؤية النمط. الحد الثابت هو $a_0b_0\text{.}$ ومعامل $x$ هو $a_0b_1 + a_1b_0\text{.}$ وهكذا. نحصل على:

$$\begin{equation*} AB = a_0b_0 + (a_0b_1 + a_1b_0)x + (a_0b_2 + a_1b_1 + a_2b_0)x^2 + (a_0b_3 + a_1b_2 + a_2b_1 + a_3b_0)x^3 + \cdots\text{.} \end{equation*}$$

مثال 6.1.5.

«اضرب» المتتالية $1, 2, 3, 4, \ldots$ في المتتالية $1, 2, 4, 8, 16, \ldots\text{.}$

الحل. الحد الثابت الجديد هو ببساطة $1 \cdot 1\text{.}$ والحد التالي هو $1\cdot 2 + 2 \cdot 1 = 4\text{.}$ ثم الحد التالي: $1 \cdot 4 + 2 \cdot 2 + 3 \cdot 1 = 11\text{.}$ وحد آخر: $1 \cdot 8 + 2 \cdot 4 + 3 \cdot 2 + 4 \cdot 1 = 26\text{.}$ المتتالية الناتجة هي:

$$\begin{equation*} 1, 4, 11, 26, 57, \ldots\text{.} \end{equation*}$$

بما أن الدالة المولِّدة للمتتالية $1,2,3,4, \ldots$ هي $\frac{1}{(1-x)^2}$، والدالة المولِّدة للمتتالية $1,2,4,8, 16, \ldots$ هي $\frac{1}{1-2x}\text{,}$ فإن الدالة المولِّدة للمتتالية $1,4, 11, 26, 57, \ldots$ هي $\frac{1}{(1-x)^2(1-2x)}$.

انظر إلى الحالة الخاصة التي تضرب فيها متتالية في $1, 1, 1, \ldots\text{.}$ مثلًا، اضرب $1,1,1,\ldots$ في $1, 2, 3, 4, 5\ldots\text{.}$ الحد الأول هو $1\cdot 1 = 1\text{.}$ ثم $1\cdot 2 + 1 \cdot 1 = 3\text{.}$ ثم $1\cdot 3 + 1\cdot 2 + 1 \cdot 1 = 6\text{.}$ والحد التالي سيكون 10. نحن نحصل على الأعداد المثلثية. وبصورة أدق، نحصل على متتالية المجاميع الجزئية للمتتالية $1,2,3,4,5, \ldots\text{.}$ بلغة الدوال المولِّدة، نأخذ $\frac{1}{1-x}$ (التي تولِّد $1,1,1,1,1\ldots$) ونضربها في $\frac{1}{(1-x)^2}$ (التي تولِّد $1,2,3,4,5,\ldots$)، فنحصل على $\frac{1}{(1-x)^3}\text{.}$ ولا ينبغي أن يفاجئنا ذلك، إذ وجدنا الدالة المولِّدة نفسها للأعداد المثلثية سابقًا.

المقصود هو أنك إذا احتجت إلى إيجاد دالة مولِّدة لمجموع الحدود الـ$n$ الأولى من متتالية معيّنة، وكنت تعرف الدالة المولِّدة لتلك المتتالية، فيمكنك ضربها في $\frac{1}{1-x}\text{.}$ وللرجوع من متتالية المجاميع الجزئية إلى المتتالية الأصلية، تنظر إلى متتالية الفروق. عند إيجاد متتالية الفروق، ينتهي بك الأمر إلى الضرب في $1-x$، أو، على نحو مكافئ، القسمة على $\frac{1}{1-x}\text{.}$ الضرب في $\frac{1}{1-x}$ يعطي المجاميع الجزئية، والقسمة على $\frac{1}{1-x}$ تعطي الفروق.

قسم فرعي: حل العلاقات العودية باستخدام الدوال المولِّدة

نختتم بمثال على أحد الأسباب الكثيرة التي تجعل دراسة الدوال المولِّدة مفيدة. يمكننا استخدام الدوال المولِّدة لحل العلاقات العودية.

مثال 6.1.6.

حل العلاقة العودية $a_n = 3a_{n-1} - 2a_{n-2}$ ذات الشروط الابتدائية (Initial Conditions) $a_0 = 1$ و$a_1 = 3\text{.}$

الحل. رأينا في مثال سابق أن هذه العلاقة العودية تعطي المتتالية $1, 3, 7, 15, 31, 63, \ldots$، التي لها الدالة المولِّدة $\dfrac{1}{1 - 3x + 2x^2}\text{.}$ فعلنا ذلك بتسمية الدالة المولِّدة $A$، ثم حساب $A - 3xA + 2x^2A$، الذي كان يساوي 1 فقط، لأن جميع الحدود الأخرى ألغت بعضها بعضًا.

لكن كيف تساعدنا معرفة الدالة المولِّدة؟ أولًا، جزِّئ الدالة المولِّدة إلى دالتين أبسط. لهذا الغرض، يمكننا استخدام التحليل إلى كسور جزئية (Partial Fraction Decomposition). ابدأ بتحليل المقام إلى عوامل:

$$\begin{equation*} \frac{1}{1-3x + 2x^2} = \frac{1}{(1-x)(1-2x)}\text{.} \end{equation*}$$

يخبرنا التحليل إلى كسور جزئية بأنه يمكننا كتابة هذا الكسر على هيئة مجموع كسرين (نحلّل الكسر المعطى):

$$\begin{equation*} \frac{1}{(1-x)(1-2x)} = \frac{a}{1-x} + \frac{b}{1-2x} \text{ ~~ لثابتين ما } a \text{ و } b\text{.} \end{equation*}$$

لإيجاد $a$ و$b$، نجمع الكسرين الناتجين عن التحليل باستخدام مقام مشترك. وهذا يعطينا:

$$\begin{equation*} \frac{1}{(1-x)(1-2x)} = \frac{a(1-2x) + b(1-x)}{(1-x)(1-2x)}\text{.} \end{equation*}$$

ومن ثم:

$$\begin{equation*} 1 = a(1-2x) + b(1-x)\text{.} \end{equation*}$$

يجب أن يصح هذا لكل قيم $x\text{.}$ إذا كان $x = 1$، تصبح المعادلة $1 = -a$، ومن ثم $a = -1\text{.}$ وعندما يكون $x = \frac{1}{2}$، نحصل على $1 = b/2$، ومن ثم $b = 2\text{.}$ وهذا يخبرنا بأنه يمكننا تحليل الكسر هكذا:

$$\begin{equation*} \frac{1}{(1-x)(1-2x)} = \frac{-1}{1-x} + \frac{2}{1-2x}\text{.} \end{equation*}$$

بهذا يكتمل التحليل إلى كسور جزئية. لاحظ أن هذين الكسرين دالتان مولِّدتان نعرفهما. بل ينبغي أن نستطيع توسيع كل منهما.

$$\begin{equation*} \frac{-1}{1-x} = -1 - x - x^2 -x^3 - x^4 - \cdots \mbox{ التي تولِّد } -1, -1, -1, -1, -1, \ldots\text{.} \end{equation*}$$ $$\begin{equation*} \frac{2}{1-2x} = 2 + 4x + 8x^2 + 16x^3 + 32x^4 + \cdots \mbox{ التي تولِّد } 2, 4, 8, 16, 32, \ldots\text{.} \end{equation*}$$

يمكننا إعطاء صيغة مغلقة للحد ذي الفهرس $n$ في كل من هاتين المتتاليتين. الأولى هي ببساطة $a_n = -1\text{.}$ والثانية هي $a_n = 2^{n+1}\text{.}$ والمتتالية التي تهمنا ليست سوى مجموعهما، لذا فإن حل العلاقة العودية هو:

$$\begin{equation*} a_n = 2^{n+1} - 1\text{.} \end{equation*}$$

يمكننا الآن إضافة الدوال المولِّدة إلى قائمة طرقنا لحل العلاقات العودية.