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

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

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

=
הגדרה רקורסיבית ונוסחה ישירה
=
בסגנון רשמי: F1=1; F2=1; ולכל n הבאים F_{n+1}=F_n+F_{n-1}. זו דוגמה פשוטה לסדרה המוגדרת ברקורסיה (הגדרה שמגדירה איבר מתוך איברים קודמים).
יש גם נוסחה ישירה (נוסחת בינט) שמקשרת את האיברים ליחס הזהב ולשורש החמישה. הנוסחה משתמשת ב־√5 ובערכים שנקראים φ+ ו־φ−, והיא נותנת את F_n בלי לחשב את כל האיברים הקודמים.

=
מספרי פיבונאצ'י ויחס הזהב
=
היחס בין איברים עוקבים שואף ליחס הזהב, מספר אי־רציונלי בערך 1.61803398... כבר יחס של F11 ל־F10 שווה ל־89/55≈1.61818, וביחס של F16 ל־F15 הדיוק גבוה יותר.
אפשר להראות זאת גם כשבר המשולב שאינו נגמר; קיצוץ של השבר נותן יחס בין שני מספרי פיבונאצ'י עוקבים.

=
הצגה גאומטרית של מספרי פיבונאצ'י
=
ניתן לבנות ריבועים שצלעם הם איברי פיבונאצ'י: ריבוע 1×1, עוד 1×1, אז 2×2, 3×3, 5×5 וכן הלאה. חיבור הריבועים יוצר מלבנים שנוטים לצורת מלבן הזהב, שאורכו בערך פי 1.618 מרוחבו.

=
תכונות ותוצאות חשובות
=
זהות קאסיני: מתקיים כמעט תמיד יחס פשוט בין ריבוע של איבר לבין מכפלת השכנים שלו; ההפרש ביניהם הוא 1 או −1, בהתאם למיקום. דוגמה פשוטה: בעשרת האיברים 3,5,8 נבחן ש־5^2=25 ואילו 3·8=24.

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

תכונות מודולריות: כאשר מסתכלים על שאריות האיברים בחלוקה ל־m, הסדרה מחזורית. עבור m קיים מחזור, ובכלליות אורך המחזור אינו עולה על 6m.

משפט זקנדורף: כל מספר טבעי מקבל הצגה יחידה כסכום של מספרי פיבונאצ'י שונים שאין ביניהם שניים עוקבים. אפשר למצוא הצגה זו בעזרת אלגוריתם חמדן. למשל 100 = 89 + 8 + 3.

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

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

=
סדרת פיבונאצ'י
=
סדרת פיבונאצ'י מתחילה ב־1, 1. כל מספר אחר הוא סכום שני המספרים שלפניו. לדוגמה: 1, 1, 2, 3, 5, 8, 13, 21...

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

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

=
בניית ריבועים
=
מוסיפים ריבועים שצלעם הם איברים בסדרה: 1×1, עוד 1×1, 2×2, 3×3, 5×5 ועוד. כך מקבלים צורת סריג שמתקרבת למלבן שיש לו יחס של 1.618.

=
חידות פשוטות
=
השאלה על הארנבים מובילה ישירות לסדרה. עוד חידה: כמה דרכים יש להגיע לקומה אם אפשר לעלות צעד אחד או שניים? התשובה קשורה לפיבונאצ'י.

=
הצגת זקנדורף
=
כל מספר אפשר לכתוב כאוסף מספרי פיבונאצ'י שאינם סמוכים זה לזה. זו הצגה יחידה לכל מספר. למשל 100 = 89 + 8 + 3.

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