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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
Nuvola apps edu mathematics blue-p.svg

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

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

בניסוח פורמלי יותר, הגדרה רקורסיבית של הסדרה ניתנת על-ידי תנאי ההתחלה F_1 = F_2 = 1, ונוסחת הנסיגה F_{n+1} = F_n+F_{n-1}. אברי הסדרה נקראים מספרי פיבונאצ'י.

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

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

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

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

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

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

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

\tfrac{F_{16}}{F_{15}} = \tfrac{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}.

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

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

  • כל מספר שלישי בסדרה הוא זוגי;
  • כל מספר רביעי הוא כפולה של 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=(\tfrac{5}{p})\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.

משפט זקנדורף[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – משפט זקנדורף

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

הצגת הזקנדורף של מספר היא הצגתו כסכום של מספרי פיבונאצ'י בדרך המתוארת. קיים אלגוריתם חמדן המחשב את הצגת הזקנדורף של מספר. ההצגה דומה להצגה של בסיסים, במיוחד של בסיס בינארי ויוצרת את בסיס פיבונאצ'י: ניתן להציג כל מספר ב"בסיס פיבונאצ'י" או "בסיס זקנדורף" כאשר הספרה הראשונה מימין מייצגת את  F_2 ובאופן כללי הספרה ה-n מימין מייצגת את  F_{n+1}. אם הספרה היא '1' סימן שמספר פיבונאצ'י המתאים משתתף בסכום, ואם היא '0' סימן שהוא לא משתתף. למשל הצגת זקנדורף של מאה היא:  100 = F_{11}+F_6+F_4 = 1000010100_Z והבסיס משמש בתורת הקודים עקב הייחודיות של ההצגה.

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

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

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

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

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

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

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

אפשר לקבל את אברי הסדרה בצורה ישירה על פי הנוסחה \ F_n = \tfrac{1}{\sqrt{5}}(\phi_+^{n} - \phi_-^{n}) כאשר \ \phi_\pm = \tfrac{1 \pm \sqrt{5}}{2} הם הפתרונות של המשוואה \phi^2 - \phi - 1\ = 0 המאפיינת את יחס הזהב. יש המייחסים לאדוארד לוקאס את גילוי הנוסחה.‏[1] אולם הנוסחה הייתה ידועה כבר לז'אק פיליפ מארי בינה בשנת 1843,‏[2] ואולי אף ללאונרד אוילר ב-1765 ואפילו לאברהם דה-מואבר ב-1730.‏‏[3][4]

מכיוון ש- \ \phi_-^{n} \rightarrow 0, מתקיים F_n \approx \tfrac{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.

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

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