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

Fibonacci Number

ليناردو فيبوناشي 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)$ .

نبذة عن كاتب الموضوع

$User picture$

الإسم: محترف

عضو مؤسس في شبكة الرياضيات رمز.

علِّق

التعليق: *

Every instance heading tags will be modified to include an id attribute for anchor linking.
Every instance of "" in the input text will be replaced with a collapsible mediawiki-style table of contents. Accepts options for title, list style, minimum heading level, and maximum heading level as follows: . All arguments are optional and defaults are shown.
LaTeX formulas are automatically converted into images.
وسوم html المسموح بها: <a> <i> <p> <b> <em> <center> <strong> <cite> <code> <ul> <ol> <li> <dl> <dt> <div> <dir> <span> <style> <br> <br /> <blockquote> <h1> <h2> <h3> <h4> <h5> <h6> <hr> <img> <sub> <sup> <table> <tbody> <tfoot> <th> <thead> <tr> <td> <dd>
بإمكانك استخدام وسوم BBCode في النصوص URLs will automatically be converted to links.
تتحول مسارات مواقع وب و عناوين البريد الإلكتروني إلى روابط آليا.
Use [fn]...[/fn] (or <fn>...</fn>) to insert automatically numbered footnotes.
Use [# ...] to insert automatically numbered footnotes. Textile variant.
Web page addresses and e-mail addresses turn into links automatically. (Better URL filter.)
Link to content with [[some text]], where "some text" is the title of existing content or the title of a new piece of content to create. You can also link text to a different title by using [[link to this title|show this text]]. Link to outside URLs with [[http://www.example.com|some text]], or even [[http://www.example.com]].
Glossary terms will be automatically marked with links to their descriptions. If there are certain phrases or sections of text that should be excluded from glossary marking and linking, use the special markup, [no-glossary] ... [/no-glossary]. Additionally, these HTML elements will not be scanned: a, abbr, acronym, code, pre.
Images can be added to this post.

معلومات أكثر عن خيارات التنسيق

كلمة التحقق

This question is for testing whether you are a human visitor and to prevent automated spam submissions.