סדרת פיבונאצ'י
בערך זה |
במתמטיקה, סדרת פיבונאצ'י (Fibonacci) היא הסדרה ששני איבריה הראשונים הם 1, 0 וכל איבר לאחר מכן שווה לסכום שני קודמיו. בהתאם לכך, איבריה הראשונים של הסדרה הם
סדרת פיבונאצ'י קרויה על שם לאונרדו מפיזה (הידוע בכינוי "פיבונאצ'י"), שתיאר אותה לראשונה באירופה בספרו "ספר החשבונייה" בשנת 1202 (קדמו לו מתמטיקאים הודים). שם הסדרה הוענק לה על ידי אדוארד לוקאס. פיבונאצ'י השתמש בסדרה כדי לתאר את מספר הארנבים במשפחה של זוג ארנבים, אם מניחים שכל זוג ארנבים שהגיע לגיל חודשיים, ממליט מדי חודש זוג נוסף. באוכלוסייה כזו, מספר זוגות הארנבים בחודש ה-n (כולל ההורים) יהיה שווה ל- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F_n} .
למעט הסדרות החשבוניות וההנדסיות, ושילובים שלהן, סדרת פיבונאצ'י היא הדוגמה הפשוטה ביותר לסדרה המוגדרת ברקורסיה. בניסוח פורמלי יותר, הגדרה רקורסיבית של הסדרה ניתנת על ידי תנאי ההתחלה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F_1 = 1; F_2 = 1} , ונוסחת הנסיגה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F_{n+1} = F_n+F_{n-1}} .
למספרי פיבונאצ'י יש תכונות רבות ומעניינות. ספרים שלמים נכתבו עליהם ואף קיים כתב עת מתמטי, The Fibonacci Quarterly,[2] שמוקדש כולו לתגליות במספרי פיבונאצ'י והכללות שלהם. כמו כן, נוסדה אגודת פיבונאצ'י[3] שמטרתה לגלות מופעים חדשים של סדרת פיבונאצ'י.
סדרת פיבונאצ'י יוצרת גם את שבלול פיבונאצ'י, אם נצייר ריבועים שהצלעות שלהם הם מספרי פיבונאצ'י ונעביר קשתות בין קודקודיהם ייווצר שבלול המכונה שבלול פיבונאצ'י.[4]
מספרי פיבונאצ'י ויחס הזהב
היחס בין שני איברים עוקבים של סדרת פיבונאצ'י שואף ליחס הזהב: מספר אי-רציונלי שערכו ...1.61803398, כפי שהראה לראשונה יוהאנס קפלר. יחס הזהב מושג בקירוב טוב כבר באיבר ה-11 של סדרת פיבונאצ'י:
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tfrac{F_{11}}{F_{10}} = \tfrac{89}{55} = 1.6181818}
ובאיבר ה-16 הדיוק משתפר לרמה של 5 ספרות אחרי הנקודה העשרונית:
תכונה זו אינה מפליאה אם מציגים את יחס הזהב כשבר המשולב: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \phi = 1 + \frac{1}{1+\frac{1}{1+\frac{1}{1+\cdots}}}} .
חלק סופי משבר אינסופי זה הוא יחס בין שני מספרי פיבונאצ'י עוקבים, אם קוטעים את החישוב במקום המתאים. לדוגמה, עבור האיברים 3 ו-5 השבר מקבל את הערך 1.666:
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \phi = 1 + \frac{1}{1+\frac{1}{1+\frac{1}{1}}}}
הצגה גאומטרית של מספרי פיבונאצ'י
אחת מההצגות הגאומטריות של הסדרה מתחילה בריבוע שאורך צלעו 1, כגודל האיבר הראשון, ומתווספים לו ריבועים באופן הבא:
לריבוע הראשון מתווסף ריבוע נוסף בגודל 1x1. שני הריבועים יוצרים מלבן שרוחבו 1 ואורכו 2 - כגודל שני האיברים F2 ו-F3.
בשלב הבא נוסיף ריבוע בגודל 2x2, ונקבל מלבן בגודל 2x3. תוספת של ריבוע בגודל 3x3 תוביל למלבן בגודל 3x5. התוצר של הבנייה על ידי הוספת ריבוע שצלעו כאיבר פיבונאצ'י מביאה למלבן שצלעותיו הן שני איברי פיבונאצ'י עוקבים.
בהמשך הבנייה, המלבנים מתקרבים יותר ויותר למלבן הזהב, שהוא מלבן שהיחס בין צלעותיו הוא יחס הזהב - 1.618 בקירוב. ליחס הזהב ולמלבן הזהב מופעים שונים בטבע, באדריכלות ובאמנות.
תכונות נוספות של הסדרה
זהות קאסיני
את הזהות גילה האסטרונום האיטלקי ג'ובאני דומניקו קאסיני. הזהות אומרת כי , כלומר מספר פיבונאצ'י בריבוע הוא כמעט מכפלת שני המספרים לידו, ההפרש ביניהם הוא 1. מי גדול יותר זו שאלה שתלויה בזוגיות של המיקום של מספר הפיבונאצ'י שלקחנו. למשל, בסדרה יש את הרצף 3,5,8, שבו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 5^2=25} ו- וההפרש ביניהם הוא באמת 1. את הזהות ניתן להוכיח בכמה דרכים: דרך אחת היא באמצעות אינדוקציה מתמטית, שכן כך הסדרה מוגדרת. דרך אחרת היא להשתמש בעובדה שדטרמיננטה היא כפלית ולרשום:
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{pmatrix} F_{n+1} & F_{n} \\ F_{n} & F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \cdot \begin{pmatrix} F_{n} & F_{n-1} \\ F_{n-1} & F_{n-2} \end{pmatrix}}
סדרת לוקאס
- ערך מורחב – סדרת לוקאס
סדרה דומה לסדרת פיבונאצ'י היא סדרת לוקאס. הסדרה מוגדרת על ידי:
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_1=1}
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_{n+1}=L_n+L_{n-1}}
סדרת פיבונאצ'י וסדרת לוקאס הן סדרות מהסוג הבא:
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F_n=S_n(1,1)}
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_n = S_n (1,3)}
לכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_n= F_{n-1} + F_{n+1}} .
ישנה עוד נוסחא המקשרת בין שתי הסדרות:
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2F_{m+n} = F_mL_n +F_nL_m}
בנוסף, בדומה לנוסחא הכללית של סדרת פיבונאצ'י
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F_{n}=\frac{1}{\sqrt5}\left[\left(\frac{1+\sqrt5}{2}\right)^n-\left(\frac{1-\sqrt5}{2}\right)^n\right] }
גם לסדרת לוקאס יש נוסחא כללית:
תכונות מודולריות של סדרת פיבונאצ'י
אחת הסיבות לחשיבותה של סדרת פיבונאצ'י בתורת המספרים היא ההתנהגות המעניינת של השאריות שלה בחלוקה למספר ראשוני קבוע. לדוגמה,
- כל מספר שלישי בסדרה הוא זוגי;
- כל מספר רביעי הוא כפולה של 3;
- כל מספר חמישי הוא כפולה של 5.
- כל מספר שביעי הוא כפולה של 13.
כאשר מתבוננים בסדרה מודולו כל מספר טבעי m, היא יכולה לקבל רק מספר סופי של ערכים, ולכן אין תימה שהסדרה מחזורית. כאשר בוחנים את הסדרה מודולו מספר ראשוני p, ישנם ארבעה מקרים: ראשית, מודולו p=2, סדרת השאריות היא ומחזורה 3. מודולו p=5 המחזור הוא 20. כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p\neq 5} , המספר מקיים , כאשר המקדם הוא סימן יעקובי, השווה ל-1 אם 5 הוא שארית ריבועית מודולו p (זה קורה כאשר p מסתיים בספרות 1,4,6 או 9), ול־1- אחרת. אם 5 הוא שארית ריבועית אז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \phi_{+}^p=\phi_{+}} וכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \phi_{-}^p=\phi_{-}} , וכך אפשר להוכיח שמחזור הסדרה מחלק את p-1. אם 5 איננו שארית ריבועית אז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \phi_{+}^p=\phi_{-}} ו- , ובמקרה זה (החישוב נובע מן התכונה ), והמחזור מחלק את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 2(p+1)} . תכונות אלה של סדרת פיבונאצ'י משמשות במבחני ראשוניות (ראו גם סדרת לוקאס).
לכל מספר טבעי m, אורך המחזור של סדרת פיבונאצ'י מודולו m הוא לכל היותר 6m. אורך המחזור הוא 6m אם ורק אם m שווה לכפליים חזקה של 5.
משפט זקנדורף
- ערך מורחב – משפט זקנדורף
כל מספר טבעי ניתן להצגה בצורה יחידה כסכום של מספרי פיבונאצ'י שונים שאין ביניהם שניים עוקבים (סמוכים זה לזה בסדרה). הצגה זו נקראת הצגת זקנדורף, על שמו של הרופא הצבאי הבלגי אדואר זקנדורף (1901-1983), שהיה מתמטיקאי חובב והוכיח שהיא אכן תמיד קיימת.
את הצגת זקנדורף אפשר למצוא באמצעות אלגוריתם חמדן. מכיוון שכל מספר פיבונאצ'י עשוי להופיע בסכום לכל היותר פעם אחת, ההצגה המתקבלת נראית כמו הצגה בינארית: הספרה '1' במקום ה-n מסמנת שמספר פיבונאצ'י הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F_{n+1}} משתתף בסכום, וספרת '0' מציינת שהמספר אינו משתתף. למשל הצגת זקנדורף של מאה היא: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 100 = F_{11}+F_6+F_4 = 1000010100_Z} .
חידות שסדרת פיבונאצ'י היא פתרונן
בספר החשבונייה מספרי פיבונאצ'י מופיעים בהקשר לחידה העוסקת בארנבים. על-פי החידה זוג ארנבים צעיר הופך לאחר שנה לזוג ארנבים מבוגר. לצורך החידה הארנבים לא מתים אף פעם. זוג ארנבים מבוגר בכל שנה מוליד זוג ארנבים נוסף. מתחילים מזוג ארנבים צעיר אחד, כמה זוגות ארנבים יהיו מעתה כל שנה?
הפתרון לחידה הוא סדרת פיבונאצ'י. הסדרה מופיעה גם כפתרון לחידות קומבינטוריות רבות. לדוגמה, דבורה יכולה להיכנס לכוורת שבאיור דרך המשושה המסומן ב־1, או דרך המשושה המסומן ב־2. הדבורה יכולה לעבור ממשושה מסוים לשכנו, בתנאי שמספרו של המשושה החדש גדול ממספרו של המשושה בו היא נמצאת. בכמה דרכים שונות יכולה הדבורה להגיע למשושה ה־n?
חידה נוספת: אם אדם צריך לעלות בסולם n שלבים, וכל פעם עליו להחליט אם לעלות שלב אחד או שניים, כמה אפשרויות יש לו?
גם הפתרון לחידה זו הוא סדרת פיבונאצ'י, מפני שיש להסתכל על המהלך הראשון, במהלך הראשון יכול האדם לעלות שלב אחד או שניים, אם יעלה שלב אחד - אזי מספר האפשרויות הנותרות יהיה בדיוק כמספר האפשרויות לעלות n-1 שלבים, ואם יעלה 2 שלבים יהיה מספר האפשרויות הנותרות כמספר האפשרויות לעלות n-2 שלבים.
נוסחה ישירה לאברי הסדרה
אפשר לקבל את אברי הסדרה בצורה ישירה על פי הנוסחה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ F_n = \tfrac{1}{\sqrt5}(\phi_+^{n} - \phi_-^{n})} כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \phi_\pm = \tfrac{1 \pm \sqrt{5}}{2}} הם הפתרונות של המשוואה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi^2 - \phi - 1\ = 0} המאפיינת את יחס הזהב. יש המייחסים לאדוארד לוקאס את גילוי הנוסחה.[5] אולם הנוסחה הייתה ידועה כבר לז'אק פיליפ מארי בינה בשנת 1843,[6] ואולי אף ללאונרד אוילר ב-1765 ואפילו לאברהם דה-מואבר ב-1730.[7][8][9]
מכיוון ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \phi_-^{n} \rightarrow 0} , מתקיים , ומכאן שהיחס בין אברי הסדרה שואף ליחס הזהב.
את הנוסחה קל להוכיח באינדוקציה. כדי לקבל אותה, כמו נוסחאות לסדרות רקורסיה ליניאריות אחרות, אפשר לכתוב את הגדרת הסדרה בעזרת מטריצה מתאימה:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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} }
מכיוון שהמשוואה האופיינית בלכסון המטריצה היא משוואת יחס הזהב, אפשר לכתוב:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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} }
והצבה בנוסחת הרקורסיה המטריציונית נותנת את הנוסחה הישירה עבור אברי הסדרה.
- ניתן להווכח בנכונות הנוסחה גם על ידי הנחה שכל חזקות יחס הזהב הם המספר בסדרה כפול יחס הזהב, ועוד המספר הקודם בסדרה.(שהרי יחס הזהב בריבוע הוא יחס הזהב ועוד 1) וכל הכפלה ביחס הזהב נותן את המספרים הבאים בסדרה.
- כעת אם תחבר את שני האיברים במונה תקבל את המספר בסדרה כפול 2 פעמים יחס הזהב פחות המספר בסדרה. ושורש של 5 הוא 2 פעמים יחס הזהב פחות 1
שימושים במדעי המחשב
ישנם אלגוריתמים ומבני נתונים כגון ערימת פיבונאצ'י המשתמשים בתכונות של מספרי פיבונאצ'י להוכחת סיבוכיות.
ראו גם
לקריאה נוספת
- מריו ליביו, חיתוך הזהב - קורותיו של מספר מופלא, הוצאת אריה ניר, 2003.
- אלי מיטב, מספרים מכושפים - על חיתוך הזהב, סדרת פיבונאצ'י ועוד פנינים מתמטיות, הוצאת שורש, 2008.
קישורים חיצוניים
- מהילברט עד פיבונאצ'י, חידות המתבססות על סדרת פיבונאצ'י.
- הרצאה "מהי מתמטיקה" של יונתן ברויאר - החל מדקה 33 הסבר מפורט ובסיסי על סדרת פיבונאצ'י, YouTube
- סדרת פיבונאצ'י - סרטון הסבר של Vi Hart: חלק 1 חלק 2 חלק 3
- Sequences 3: Fibonacci – סרטון הסבר של MathTV על סדרת פיבונאצ'י (באנגלית)
- מחשבון לחישוב מספר פיבונאצ'י (באנגלית)
- מחשבון סדרת פיבונאצ'י (בעברית)
- פזיה מילר, סדרת פיבונאצ'י, באתר מכון דוידסון, יולי 2012
- יפעת אדלר בן יעקב, הקסם של מספרי פיבונאצ'י, באתר מכון דוידסון, דצמבר 2013
- יעל נוריק, מספרי פיבונאצ'י ויחס הזהב, באתר מכון דוידסון, מאי 2014
- סדרת פיבונאצ'י, באתר אנציקלופדיה למתמטיקה (באנגלית)
שגיאות פרמטריות בתבנית:בריטניקה
פרמטרי חובה [ 1 ] חסרים
הערות שוליים
- ^ (סדרה A000045, באתר OEIS – האנציקלופדיה המקוונת לסדרות של מספרים שלמים)
- ^ The Fibonacci Quarterly
- ^ The Fibonacci Association
- ^ הקסם של מספרי פיבונצ'י, באתר הקסם של מספרי פיבונצ'י
- ^ ביוגרפיה של סדרת פיבונאצ'י, באתר MacTutor (באנגלית)
- ^ Édouard Lucas, The Fibonacci Series
- ^ Binets Formula, באתר MathWorld (באנגלית)
- ^ Binet's, de Moivre's or Euler's Formula?
- ^ נוסחה באקסל לחישוב ערכי הסדרה:=1/(5^0.5)*((((1+5^0.5)/2)^A1)-(((1-5^0.5))/2)^A1) בטור A יש להציב את המספרים הסודרים, בטור B יתקבלו ערכי הסדרה
32736882סדרת פיבונאצ'י