סדרת פיבונאצ'י

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

במתמטיקה, סדרת פיבונאצ'י היא סדרה המתחילה במספרים 0 ו-1 ולאחר מכן כל איבר בסדרה הוא סכום של שני האיברים הקודמים לו. תחילתה של הסדרה היא המספרים: ...0,1,1,2,3,5,8,13,21,34,55

לדוגמה: ...3,5,8... 8=3+5.

הנוסחה המייצגת הגדרה זו משקפת את אופיה הרקורסיבי:

$F_n := F(n):= \begin{cases} 0 & \mbox{if } n = 0; \\ 1 & \mbox{if } n = 1; \\ F(n-1)+F(n-2) & \mbox{if } n > 1. \\ \end{cases}$ .

בשפת תכנות התומכת ברקורסיה קל לכתוב תוכנית שמממשת את ההגדרה. בשפת C, למשל, תוכנית שמחשבת את האיבר ה-n תיראה כך:

   int fibo(int n) {
       if (n <= 1) {
           return n;
       } else {
           return fibo(n-1) + fibo(n - 2);
       }
   }

(יש לשים לב כי חישוב איטרטיבי של הסדרה יעיל בהרבה, אך אינו ממחיש את אופייה הרקורסיבי).

תוכן עניינים

1 מקור הסדרה
2 תכונות הסדרה
- 2.1 תכונות מודולריות של סדרת פיבונאצ'י
3 נוסחה ישירה לאברי הסדרה
4 שימושים במדעי המחשב
5 לקריאה נוספת
6 קישורים חיצוניים

[עריכה] מקור הסדרה

סדרת פיבונאצ'י קרויה על שם ליאונרדו פיבונאצ'י שחשף אותה בספרו "ספר החשבוניה" בשנת 1202. האיברים בסדרת פיבונאצ'י קרויים מספרי פיבונאצ'י. פיבונאצ'י השתמש בסדרה כדי לתאר את התרבותה של אוכלוסיית ארנבים, כאשר מניחים שמתקיים:

האוכלוסייה מתחילה בזוג ארנבים שזה עתה נולדו.
ארנבים מתחילים להתרבות חודש לאחר הולדתם, וכל זוג ארנבים מוליד זוג נוסף מדי חודש.
הארנבים אינם מתים לעולם.

ניתן לראות כי מספר הארנבים בחודש n שווה לאיבר ה-n של סדרת פיבונאצ'י.

[עריכה] תכונות הסדרה

לסדרת פיבונאצ'י כמה תכונות יפות, שקל להוכיחן על-פי הגדרת הסדרה.

לדוגמה, ריבועו של מספר פיבונאצ'י הנמצא במקום איזוגי גדול ב-1 מסכום מכפלת המספרים משני צדדיו, וריבועו של מספר פיבונאצ'י הנמצא במקום זוגי קטן ב-1 ממכפלת המספרים משני צדדיו. כך למשל הריבוע של 5 שווה 25. משני צדדיו של 5 מוצאים את 3 ו-8. מכפלתם שווה 24. המספר 25 גדול ב-1 מן המספר 24. מספר פיבונאצ'י הבא אחרי 5 הוא 8. הריבוע של שווה 64. משני צדדיו של 8, מוצאים את 5 ו-13. מכפלתם שווה 65. המספר 64 קטן ב-1 מן המספר 65.

יוהנס קפלר הראה שהמנה של כל שני איברים רצופים בסדרה שואפת ליחס הזהב, מספר מעניין שיש לו מופעים שונים בטבע, באדריכלות ובאמנות.

המתמטיקאי הרוסי יורי מאטיאשביץ השתמש בסדרת פיבונאצ'י בשנת 1970, כדי לפתור את הבעיה העשירית של הילברט.

למספרי פיבונאצ'י יש תכונות רבות ומפליאות, וככל שחוקרים אותם מגלים בהם עוד ועוד תכונות מעניינות. ספרים שלמים נכתבו עליהם ואף קיים כתב עת מתמטי (Fibonacci quarterly) שמוקדש כולו לתגליות במספרי פיבונאצ'י והכללות שלהם. כמו כן, נוסדה אגודת פיבונאצ'י שמטרתה לגלות מופעים חדשים של סדרת פיבונאצ'י.

[עריכה] תכונות מודולריות של סדרת פיבונאצ'י

אחת הסיבות לחשיבותה של סדרת פיבונאצ'י בתורת המספרים היא ההתנהגות המעניינת של השאריות שלה בחלוקה למספר ראשוני קבוע. לדוגמה,

כל מספר שלישי בסדרה הוא זוגי;
כל מספר רביעי הוא כפולה של 3;
כל מספר חמישי הוא כפולה של 5.

כאשר מתבוננים בסדרה מודולו כל מספר טבעי m, היא יכולה לקבל רק מספר סופי של ערכים, ולכן אין תימה שהסדרה מחזורית. כאשר בוחנים את הסדרה מודולו מספר ראשוני p, ישנם ארבעה מקרים: ראשית, מודולו p=2, סדרת השאריות היא $\ 0,1,1,0,1,1,...$ ומחזורה 3. מודולו p=5 המחזור הוא 20. כאשר $\ p\neq 5$ , המספר $\ \delta=\sqrt{5}$ מקיים $\ \delta^p=\left(\frac{5}{p}\right)\delta$ , כאשר המקדם הוא סימן יעקובי, השווה ל- 1 אם 5 הוא שארית ריבועית מודולו p (זה קורה כאשר p מסתיים בספרות 1,4,6 או 9), ול- 1- אחרת. אם 5 הוא שארית ריבועית אז $\ \phi_{+}^p=\phi_{+}$ וכן $\ \phi_{-}^p=\phi_{-}$ , וכך אפשר להוכיח שמחזור הסדרה מחלק את p-1. אם 5 איננו שארית ריבועית אז $\ \phi_{+}^p=\phi_{-}$ ו- $\ \phi_{-}^p=\phi_{+}$ , ובמקרה זה $\ F_{p+1+i}=-F_i$ (החישוב נובע מן התכונה $\ \phi_+\phi_-=-1$ ), והמחזור מחלק את $\ 2(p+1)$ . תכונות אלה של סדרת פיבונאצ'י משמשות במבחני ראשוניות; ראו גם סדרת לוקאס.

לכל מספר טבעי m, אורך המחזור של סדרת פיבונאצ'י מודולו m הוא לכל היותר 6m. אורך המחזור הוא 6m אם ורק אם m שווה לכפליים חזקה של 5.

[עריכה] נוסחה ישירה לאברי הסדרה

אפשר לקבל את אברי הסדרה בצורה ישירה על פי הנוסחה $\ F_n = \frac{1}{\sqrt{5}} \left( \phi_+^{n} - \phi_-^{n} \right)$ כאשר $\ \phi_\pm = \frac{1 \pm \sqrt{5}}{2}$ הם הפתרונות של המשוואה $\phi^2 - \phi - 1\ = 0$ המאפיינת את יחס הזהב.

מכיוון ש- $\ \phi_-^{n} \rightarrow 0$ , מתקיים $F_n \approx \frac{1}{\sqrt{5}} \phi_+^{n}$ , ומכאן שהיחס בין אברי הסדרה שואף ליחס הזהב.

את הנוסחה קל להוכיח באינדוקציה. כדי לקבל אותה, כמו נוסחאות לסדרות רקורסיה לינאריות אחרות, אפשר לכתוב את הגדרת הסדרה בעזרת מטריצה מתאימה:

$\begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix}= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} 1 \\ 1 \end{pmatrix}$

מכיוון שהמשוואה האופיינית בליכסון המטריצה היא משוואת יחס הזהב, אפשר לכתוב

$\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n = \left[ \frac{1}{\sqrt{5}} \begin{pmatrix} \phi_+ & \phi_- \\ 1 & 1 \end{pmatrix} \begin{pmatrix} \phi_+ & 0 \\ 0 & \phi_- \end{pmatrix} \begin{pmatrix} 1 & - \phi_- \\ -1 & \phi_+ \end{pmatrix} \right]^n = \frac{1}{\sqrt{5}}\begin{pmatrix} \phi_+ & \phi_- \\ 1 & 1 \end{pmatrix} \begin{pmatrix} \phi_+^n & 0 \\ 0 & \phi_-^n \end{pmatrix} \begin{pmatrix} 1 & - \phi_- \\ -1 & \phi_+ \end{pmatrix}$

והצבה בנוסחת הרקורסיה המטריציונית נותנת את הנוסחה הישירה עבור אברי הסדרה.

[עריכה] שימושים במדעי המחשב

ישנם אלגוריתמים ומבני נתונים כגון ערימת פיבונאצ'י המשתמשים בתכונות של מספרי פיבונאצ'י להוכחת סיבוכיותם.

[עריכה] לקריאה נוספת

מריו ליביו, חיתוך הזהב - קורותיו של מספר מופלא, הוצאת אריה ניר, 2003.

[עריכה] קישורים חיצוניים

מהילברט עד פיבונאצ'י, חידות המתבססות על סדרת פיבונאצ'י.
מספרי פיבונאצ'י וחתך הזהב, אתר מקיף העוסק בסדרת פיבונאצ'י ובנושאים קשורים.
אתר שמלמד על סדרת פיבונאצ'י, ומספק הסברים מפורטים ועם תמונות.

מקור: http://he.wikipedia.org../../../%D7%A1/%D7%93/%D7%A8/%D7%A1%D7%93%D7%A8%D7%AA_%D7%A4%D7%99%D7%91%D7%95%D7%A0%D7%90%D7%A6%27%D7%99.html

קטגוריות: סדרות של שלמים | מתמטיקה

See also ebooksgratis.com: no banners, no cookies, totally FREE.

סדרת פיבונאצ'י

מתוך ויקיפדיה, האנציקלופדיה החופשית

תוכן עניינים

[עריכה] מקור הסדרה

[עריכה] תכונות הסדרה

[עריכה] תכונות מודולריות של סדרת פיבונאצ'י

[עריכה] נוסחה ישירה לאברי הסדרה

[עריכה] שימושים במדעי המחשב

[עריכה] לקריאה נוספת

[עריכה] קישורים חיצוניים

Views

ניווט

קהילה

חיפוש

שפות אחרות