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

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

במתמטיקה, סדרת פיבונאצ'י היא הסדרה שאיבריה הראשונים הם: 1,1,2,3,5,8,13,21,34,55,89,144... . המספרים בסדרה נקראים מספרי פיבונאצ'י.

איבריה הראשונים של הסדרה הם 1 ו-1, וכל איבר אחר בה שווה לסכום שני קודמיו. הסדרה, שאת איבריה מקובל לסמן באות \ F, מוגדרת ברקורסיה על ידי נוסחת נסיגה ותנאי ההתחלתי:

  • \ F_{n+1} = F_n+F_{n-1}
  • \ F_1 = F_2 = 1

ניתן גם להגדיר את הסדרה לפי האיבר \ F_0 = 0.

היא קרויה על שם לאונרדו מפיזה, הידוע בכינוי "פיבונאצ'י", שתיאר אותה לראשונה באירופה בספרו ספר החשבוניה בשנת 1202 (קדמו לו מתמטיקאים הודים). שם הסדרה הוענק לה על ידי אדוארד לוקאס. פיבונאצ'י השתמש בסדרה כדי לתאר את מספר הצאצאים של זוג ארנבים אחד, אם מניחים שכל זוג ארנבים שהגיע לגיל חודשיים, ממליט מדי חודש זוג נוסף. באוכלוסייה כזו, מספר זוגות הארנבים בחודש ה-n יהיה שווה ל- \ F_n.

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

מספרי פיבונאצ'י ויחס הזהב[עריכת קוד מקור | עריכה]

היחס בין שני איברים עוקבים של סדרת פיבונאצ'י שואף ליחס הזהב: מספר אי-רציונלי שערכו ...1.61803398, כפי שהראה לראשונה יוהנס קפלר. יחס הזהב מושג בקירוב טוב כבר באיבר ה-11 של סדרת פיבונאצ'י:


\frac{F_{11}}{F_{10}} = \frac{89}{55} = 1.6181818

ובאיבר ה-16 הדיוק משתפר לרמה של 5 ספרות אחרי הנקודה העשרונית:


\frac{F_{16}}{F_{15}} = \frac{987}{610} = 1.61803

תכונה זו אינה מפליאה אם מציגים את יחס הזהב כשבר המשולב: \ \phi = 1 + \frac{1}{1+\frac{1}{1+\frac{1}{1+\cdots}}}.

חלק סופי משבר אינסופי זה הוא יחס בין שני מספרי פיבונאצ'י עוקבים, אם קוטעים את החישוב במקום המתאים. לדוגמה, עבור האיברים 3 ו-5 השבר מקבל את הערך 1.666:

\ \phi = 1 + \frac{1}{1+\frac{1}{1+\frac{1}{1}}}

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

מלבני הסדרה

אחת מההצגות הגאומטריות של הסדרה מתחילה בריבוע שאורך צלעו 1, כגודל האיבר הראשון, ומתווספים לו ריבועים באופן הבא:

לריבוע הראשון מתווסף ריבוע נוסף בגודל 1x1. שני הריבועים יוצרים מלבן שרוחבו 1 ואורכו 2 - כגודל שני האיברים F2 ו-F3.

בשלב הבא נוסיף ריבוע בגודל 2x2, ונקבל מלבן בגודל 2x3. תוספת של ריבוע בגודל 3x3 תוביל למלבן בגודל 3x5. התוצר של הבנייה על ידי הוספת ריבוע שצלעו כאיבר פיבונאצ'י מביאה למלבן שצלעותיו הן שני איברי פיבונאצ'י עוקבים.

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

תכונות נוספות של הסדרה[עריכת קוד מקור | עריכה]

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

לדוגמה, תכונה שגילה האסטרונום הצרפתי ז'אן דומיניקו קאסיני היא שריבועו של מספר פיבונאצ'י הנמצא במקום זוגי קטן ב-1 מסכום מכפלת המספרים משני צדדיו (\ F_{2n}^2 = F_{2n-1} \cdot F_{2n+1} + 1), וריבועו של מספר פיבונאצ'י הנמצא במקום אי זוגי גדול ב-1 ממכפלת המספרים משני צדדיו (\ F_{2n+1}^2 = F_{2n} \cdot F_{2n+2} - 1). כך למשל הריבוע של 5 שווה 25. משני צדדיו של 5 מוצאים את 3 ו-8. מכפלתם שווה 24. המספר 25 גדול ב-1 מן המספר 24. מספר פיבונאצ'י הבא אחרי 5 הוא 8. הריבוע שלו שווה 64. משני צדדיו של 8, מוצאים את 5 ו-13. מכפלתם שווה 65. המספר 64 קטן ב-1 מן המספר 65.

קשר למשפט פיתגורס[עריכת קוד מקור | עריכה]

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

  • מכפלת האיבר הראשון ברביעי
  • מכפלת האיבר השני בשלישי, כפול שתיים
  • סכום הריבועים של האיבר השני והשלישי
כך, לדוגמה, עבור 1,1,2,3 תתקבל השלשה הפיתגורית {3,4,5}, ועבור 1,2,3,5 תתקבל השלשה {5,12,13}.


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

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

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

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

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

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

כאשר מתבוננים בסדרה מודולו כל מספר טבעי 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.

חידות שסדרת פיבונאצ'י היא פתרונן[עריכת קוד מקור | עריכה]

בכמה דרכים שונות ניתן להגיע למשושה מס' 6 ?

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

הפתרון לחידה הוא סדרת פיבונאצ'י. הסדרה מופיעה גם כפתרון לחידות קומבינטוריות רבות. לדוגמה, הדבורה שבאיור יכולה להיכנס לכוורת דרך המשושה המסומן ב־1, או דרך המשושה המסומן ב־2. הדבורה יכולה לעבור ממשושה מסוים לשכנו, בתנאי שמספרו של המשושה החדש גדול ממספרו של המשושה בו היא נמצאת. בכמה דרכים שונות יכולה הדבורה להגיע למשושה ה־n?

חידה נוספת היא - אם אדם צריך לעלות בסולם n שלבים, וכל פעם עליו להחליט אם לעלות שלב אחד או שניים, כמה אפשרויות יש לו?

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

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

אפשר לקבל את אברי הסדרה בצורה ישירה על פי הנוסחה \ 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 המאפיינת את יחס הזהב. יש המייחסים לאדוארד לוקאס את גילוי הנוסחה.[1] אולם הנוסחה הייתה ידועה כבר לז'אק פיליפ מארי בינה בשנת 1843,[2] ואולי אף ללאונרד אוילר ב-1765 ואפילו לאברהם דה-מואבר ב-1730.‏[3][4]

מכיוון ש- \ \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 \\ 0 \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.
  • אלי מיטב, מספרים מכושפים - על חיתוך הזהב, סדרת פיבונאצ'י ועוד פנינים מתמטיות, הוצאת שורש, 2008.

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]