أعداد فيبواناشي (فيبوناتشي)

أعداد فيبواناشي (فيبوناتشي)
صورة محترف

ليناردو فيبوناشي Fibonacci ويدعى أيضا ليناردو بيزا Leonard of Pisa نسبة الى مدينة بيزا الإيطالية. ليناردو ابن لـ Guglielmo والذي كان يكنى Bonacci . عاش فيبوناشي في الفترة (117 - 1250) وقد اطلق عليه اسم فيبوناشي بعد وفاته وهو مشتق من filius Bonacci وتعني ابن بوناشي. ارتحل في شبابه مع والده عدة مرات الى بعض البلاد العربية كالجزائر ومصر والشام عبر بوابتها في شمال افريقيا على زمن دولة الموحدين التي حكمت شمال افريقيا والأندلس وتعلم على يد عظماء الرياضيين العمسلمين آنذاك وأخذ عنهم النظام العربي الهندي في الأعداد (وهو نظام عشري) ثم نشر هذا النظام في اوروبا عند عودته لمسقط رأسه بيزا من خلال كتابه Liber Abaci والذي احتوى أيضا على متتابعة الأعداد التي اشتهر بها وحملت اسمه "أعداد فيبواناشي" وسميت بذلك بعد وفاته. ولفيبوناشي كتاب آخر قدمه في 1220م بعنوان Practica geometriae احتوى حصيلة وافرة من الهندسة وحساب المثلثات.

أعداد فيبوناشي عبارة عن متتابعة (F_n )معرفة بالعلاقة التكرارية التالية:

F_0 = 0,\quad F_1 = 1,\quad F_n = F_{n - 1} + F_{n - 2} ,\;\forall n > 1

أي أنه ابتداء من الحد الثالث فإن كل حد عبارة عن مجموع الحدين السابقين له. هذه بعض حدود المتتابعة والتي يطلق عليها أحيانا متتابعة فيبوناشي.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584,....

لكن ماذا لو أردنا معرف الحد F_{100} هل يجب علينا المضى قدما حتى نصل اليه, ألا يوجد طريقة لحسابة مباشرة؟ جوابا على هذا السؤال يوجدصورة مغلقة للحد النوني في متتابعة فيبوناشي وهي :

F_n = \frac{1}{{\sqrt 5 }}\left( {\varphi ^n - ( - \varphi )^{ - n} } \right)

حيث \varphi = \frac{{1 + \sqrt 5 }}{2} وتسمى النسبة الذهبية. وحيث \varphi ^{ - 1} = 1 - \varphi \varphi جذر للمعادلة المميزة فإن \varphi ^{ - 1} = 1 - \varphi وبالتالي يمكن كتابة الصورة المغلقة على الشكل

F_n = \frac{1}{{\sqrt 5 }}\left( {\varphi ^n - (1 - \varphi )^n } \right)

ونستطيع إثبات هذه الصورة المغلقة بعدة طرق نناقش هنا بعضها

1) طريقة دالة التوليد لمتتابعة فيبوناشي. وهي المتسلسلة S(x) = \sum\limits_{n = 0}^\infty {F_n x^n } . يمكنا ان نوجد مجموع هذه المتسلسلة باستخدام العلاقة التكرارية F_{n + 2} = F_{n + 1} + F_n حيث

S(x) = F_0 + F_1 + \sum\limits_{n = 0}^\infty {F_{n + 2} x^{n + 2} }

استبدل الآن معاملات المجموع باستخدام العلاقة التكرارية

S(x) = F_0 + xF_1 + \sum\limits_{n = 0}^\infty {(F_{n + 1} + F_n )x^{n + 2} } = x + \sum\limits_{n = 0}^\infty {F_{n + 1} x^{n + 2} } + \sum\limits_{n = 0}^\infty {F_n x^{n + 2} }

نستخرج عامل مناسب من هذه المتسلسلات لنحصل على صورة S

S(x) = x + x\sum\limits_{n = 0}^\infty {F_{n + 1} x^{n + 1} } + x^2 \sum\limits_{n = 0}^\infty {F_n x^n }

وحيث F0=0 فيمكن إضافته للمجموع الأول من جهة اليسار وبالتالي

S(x) = x + x\sum\limits_{n = 0}^\infty {F_n x^n } + x^2 \sum\limits_{n = 0}^\infty {F_n x^n } = x + xS(x) + x^2 S(x)

بحل هذه المعادلة بالنسبة لـ S نحصل على مجموع المتسلسلة أو الصورة المغلقة لدالة التوليد لمتتابعة فيبوناشي.

S(x) = \sum\limits_{n = 0}^\infty {F_n x^n } = \frac{x}{{1 - x - x^2 }}

الآن من خلال هذه الطرف الأيمن نوجد صورة أخرى لهذه المتسلسلة. فمن قانون حل معادلة الدرجة الثانية نحصل على

1 - x - x^2 = - (x + \varphi )(x + \psi ),\quad \varphi = \frac{{1 + \sqrt 5 }}{2},\quad \psi = \frac{{1 - \sqrt 5 }}{2}

خذ الآن \varphi \psi عامل مشارك مع ملاحظة ان هذا الضرب = -1 ينتج لنا

- (x + \varphi )(x + \psi ) = - \varphi \psi (\varphi ^{ - 1} x + 1)(\psi ^{ - 1} x + 1) = (1 + \varphi ^{ - 1} x)(1 - \varphi x)

إذا

S(x) = \frac{x}{{1 - x - x^2 }} = \frac{x}{{(1 + \varphi ^{ - 1} x)(1 - \varphi x)}} = \frac{1}{{\sqrt 5 }}\left( {\frac{1}{{1 - \varphi x}} - \frac{1}{{1 + \varphi ^{ - 1} x}}} \right)

S(x) = \frac{1}{{\sqrt 5 }}\left( {\frac{1}{{1 - \varphi x}} - \frac{1}{{1 - ( - \varphi ^{ - 1} )x}}} \right) = \frac{1}{{\sqrt 5 }}\left( {\sum\limits_{n = 0}^\infty {\varphi ^n x^n } - \sum\limits_{n = 0}^\infty {( - \varphi )^{ - n} x^n } } \right)

S(x) = \frac{1}{{\sqrt 5 }}\sum\limits_{n = 0}^\infty {\left( {\varphi ^n - ( - \varphi )^{ - n} } \right)x^n } = \sum\limits_{n = 0}^\infty {\frac{1}{{\sqrt 5 }}\left( {\varphi ^n - ( - \varphi )^{ - n} } \right)x^n } = \sum\limits_{n = 0}^\infty {F_n x^n }

وبالمقارنة يتبين ان F_n = \frac{1}{{\sqrt 5 }}\left( {\varphi ^n - ( - \varphi )^{ - n} } \right).

2) هناك طريقة أخرى باستخدام المعادلة المميزة y^2 = y + 1 للعلاقة التكرارية F_{n + 1} = F_n + F_{n - 1} . بحل المعادلة نجد أن لها الجذرين:

\varphi = \frac{{1 + \sqrt 5 }}{2},\quad \psi = \frac{{1 - \sqrt 5 }}{2}

إذا الصورة المغلقة لهذه العلاقة التكرارية على الشكل

F_n = a\varphi ^n + b\psi ^n = F_n = a\varphi ^n + b( - \varphi ^{ - 1} )^n = a\varphi ^n + b( - \varphi )^{ - n}

مع ملاحظة , \varphi \psi = - 1. تحديد a,b يتم من خلال معرفتنا بالحدين F_0 = 0,\;F_1 = 1, وبالتعويض بهما في العلاقة أعلاه . إذا

\begin{array}{l} 0 = F_0 = a + b \\ 1 = F_1 = a\varphi + b( - \varphi )^{ - 1} \\ \end{array}

وبالتالي a = \frac{1}{{\sqrt 5 }} = - b , إذا

F_n = \frac{1}{{\sqrt 5 }}\left( {\varphi ^n - ( - \varphi )^{ - n} } \right)

3) هناك طريقة ثالثة لاثبات العلاقة المغلقة بواسطة الاستقراء الرياضي ولعل هذه الطريقة تعتبر الأسهل ولكنها لا تجيب عن السؤال الطبيعي, كيف وصلنا لهذه الصورة؟.

علاقات ومتطابقات عديدة تربط بين حدود متتابعة فيبوناشي ومنها متطابقة كازيني Cassini's identity

F_n ^2 - F_{n - 1} F_{n + 1} = ( - 1)^{n + 1}

عممت هذه المتطابقة بواسطة Catalan وسميت متطابقة كاتلن Catalan's identity

F_n ^2 - F_{n - r} F_{n + r} = ( - 1)^{n + r} F_r ^2

وهنا إضافة لبعض المتطابقات الأخرى

F_n ^2 + F_{n - 1} ^2 = F_{2n - 1}

F_0 + F_1 + \cdots + F_n = F_{n + 2} - 1

F_1 + 2F_2 + 3F_3 + \cdots + nF_n = nF_{n + 2} - F_{n + 3} + 2

F_1 ^2 + F_2 ^2 + F_3 ^2 + \cdots + F_n ^2 = F_n F_{n + 1}

وهذه علاقة مصفوفية تربط بين أعداد فيبوناشي ويمكن استخادم المحددة لها في اثبات متطابقة كازيني :

\left( {\begin{array}{*{20}c} 1 & 1 \\ 1 & 0 \\\end{array}} \right)^n = \left( {\begin{array}{*{20}c} {F_{n + 1} } & {F_n } \\ {F_n } & {F_{n - 1} } \\\end{array}} \right)

من الحقائق الجميلة والقديمة حول قابلية القسمة بين أعداد فيبوناشي أن Fn يقسم Fm إذا وإذا فقط كان n يقسم m. في العام 1997 اثبت تعميما رائعا لهذه الحقيقة وهو:

F_n ^2 |F_{nr} إذا وإذا فقط F_n |r

وقد ساعدت هذه الحقيقة مكتشفها في تقديم حل لمسألة هلبرت العاشرة.

أيضا في متتابعة فيبوناشي, كل عددين متتابعين أوليان نسبيا. أي \gcd (F_n ,F_{n + 1} ) = 1 وذلك لكل عدد صحيح موجب n. بشكل أعم , كل ثلاثة أعداد فيبوناشي متتابعة هي أولية نسبيا ,تحديدا

\gcd (F_n ,F_{n + 1} ) = 1 = \gcd (F_n ,F_{n + 2} )

يمكن تعميم هذه النتيجة باثبات أن \gcd (F_m ,F_n ) = F_{\gcd (m,n)} , ونصل لهذه النتيجة باستخدام خوارزمية اقليدس Euclid's algorithm. مزيد من الخصائص العددية سجلتها في أسفل هذا الموضوع كتمارين.

تمارين:

* اثبت أن Fm يقسم Fmn لكل عدد صحيح موجب m,n. مثلا F3 يقسم F6. * اثبت أن F_{n + 3} \equiv F_n (\bmod 2) لكل عدد صحيح موجب n.* العدد 5 يقسم n إذ وإذا فقط 5 يقسم Fn.

* بين ان F_n = \left\lfloor {\frac{1}{{\sqrt 5 }}\varphi ^n + \frac{1}{2}} \right\rfloor , ارشاد \left| {\frac{{(\varphi )^{ - n} }}{{\sqrt 5 }}} \right| < \frac{1}{2}

* اثبت أن \mathop {\lim }\limits_{n \to \infty } \frac{{F_{n + 1} }}{{F_n }} = \varphi . ارشاد عبر عن F بالصيغة المغلقة وخذ عامل مشترك.

* استخدم العلاقة المصفوفية أعلاه وقانون ضرب المصفوفات لإثبات أن :

F_{n + 1} F_m + F_n F_{m - 1} = F_{m + n}

* أثبت ان \sum\limits_{k = 1}^n {\left( \begin{array}{l} n \\ k \\ \end{array} \right)F_k } = F_{2n} لكل عدد صحيح موجب n.

* أثبت أن \left( \begin{array}{l} F_{n + 2} \\ F_{n + 1} \\ \end{array} \right) = \left( {\begin{array}{*{20}c} 1 & 1 \\ 1 & 0 \\\end{array}} \right)\left( \begin{array}{l} F_{n + 1} \\ F_n \\ \end{array} \right).