הצגת המקור של הדף "סדרת פיבונאצ'י"

{{סימון מתמטי}}

ב[[מתמטיקה]], '''סדרת פיבונאצ'י''' (Fibonacci) היא ה[[סדרה (מתמטיקה)|סדרה]] ששני איבריה הראשונים הם 1,1 וכל איבר לאחר מכן שווה לסכום שני קודמיו. בהתאם לכך, איבריה הראשונים של הסדרה הם: <math display="block">1,1,2,3,5,8,13,21,34,55,89,144...</math>

איברי הסדרה נקראים "'''מספרי פיבונאצ'י'''".{{הערה|1={{כ}}({{OEIS|A000045}})}}

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

למעט ה[[סדרה חשבונית|סדרות החשבוניות]] וה[[סדרה הנדסית|הנדסיות]], ושילובים שלהן, סדרת פיבונאצ'י היא הדוגמה הפשוטה ביותר לסדרה המוגדרת ב[[רקורסיה]].
בניסוח פורמלי יותר, [[הגדרה רקורסיבית]] של הסדרה ניתנת על ידי תנאי ההתחלה <math>F_1 = 1; F_2 = 1</math>, ו[[נוסחת נסיגה|נוסחת הנסיגה]] <math>F_{n+1} = F_n+F_{n-1}</math>.

למספרי פיבונאצ'י יש תכונות רבות הנחשבות למעניינות. ספרים שלמים נכתבו עליהם ואף קיים כתב עת מתמטי, The Fibonacci Quarterly,{{הערה|[http://www.fq.math.ca/ The Fibonacci Quarterly]|כיוון=שמאל}} שמוקדש כולו לתגליות במספרי פיבונאצ'י והכללות שלהם. כמו כן, נוסדה אגודת פיבונאצ'י{{הערה|[http://www.mathstat.dal.ca/fibonacci/ The Fibonacci Association]|כיוון=שמאל}} שמטרתה לגלות מופעים חדשים של סדרת פיבונאצ'י.

סדרת פיבונאצ'י יוצרת גם את שבלול פיבונאצ'י, אם נצייר ריבועים שהצלעות שלהם הם מספרי פיבונאצ'י ונעביר קשתות בין קודקודיהם ייווצר שבלול המכונה שבלול פיבונאצ'י.<ref>{{קישור כללי|כתובת=http://davidson.weizmann.ac.il/videos/online/mathcircle/clips/הקסם-של-מספרי-פיבונצי|כותרת=הקסם של מספרי פיבונצ'י|אתר=הקסם של מספרי פיבונצ'י|שפה=he|תאריך_וידוא=2020-03-09}}</ref>

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

<math>\tfrac{F_{11}}{F_{10}} = \tfrac{89}{55} = 1.6181818</math>

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

<math>\tfrac{F_{16}}{F_{15}} = \tfrac{987}{610} = 1.61803</math>

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

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

<math>\ \phi = 1 + \frac{1}{1+\frac{1}{1+\frac{1}{1}}}</math>

=== הצגה גאומטרית של מספרי פיבונאצ'י ===
[[קובץ:FibonacciBlocks.svg|שמאל|ממוזער|180px|מלבני הסדרה]]
[[קובץ:Diepholz Skulpturenpfad Fibonacci.JPG|ממוזער|180px|קוביות פיבונאצ'י: אורך צלעות הקוביות הוא לפי הסדרה.]]
[[קובץ:Aeonium tabuliforium 2 spirals 13.jpg|ממוזער|180px|סדרת פיבונאצ'י בטבע{{הבהרה}}]]
[[קובץ:FibonacciChamomile.PNG|ממוזער|180px|סדרת פיבונאצ'י בטבע{{הבהרה}}]]

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

לריבוע הראשון מתווסף ריבוע נוסף בגודל 1x1. שני הריבועים יוצרים [[מלבן]] שרוחבו 1 ואורכו 2 - כגודל שני האיברים F<sub>2</sub> ו-F<sub>3</sub>.

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

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

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

<math>\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}</math>

=== סדרת לוקאס ===
{{הפניה לערך מורחב|סדרת לוקאס}}
סדרה דומה לסדרת פיבונאצ'י היא סדרת לוקאס. הסדרה מוגדרת על ידי:

<math>L_1=1</math>

<math>L_2=3</math>

<math>L_{n+1}=L_n+L_{n-1}</math>

סדרת פיבונאצ'י וסדרת לוקאס הן סדרות מהסוג הבא:

<math>S(a_1,a_2)=\{a_1,a_2,a_3=a_1+a_2,a_4=a_2+a_3,\dots\}</math>

<math>F_n=S_n(1,1)</math>

<math>F_{n+1} = S_n (1,2)</math>

<math>F_{n-1} = S_n (0,1)</math>

<math>L_n = S_n (1,3)</math>

לכן <math>L_n= F_{n-1} + F_{n+1}</math>.

ישנה עוד נוסחה המקשרת בין שתי הסדרות:

<math>2F_{m+n} = F_mL_n +F_nL_m</math>

בנוסף, בדומה לנוסחה הכללית של סדרת פיבונאצ'י

<math>F_{n}=\frac{1}{\sqrt5}\left[\left(\frac{1+\sqrt5}{2}\right)^n-\left(\frac{1-\sqrt5}{2}\right)^n\right] </math>

גם לסדרת לוקאס יש נוסחה כללית:

<math> L_n=\left(\frac{1+\sqrt{5}}2\right)^n+ \left(\frac{1-\sqrt{5}}2\right)^n</math>

===תכונות מודולריות של סדרת פיבונאצ'י===
אחת הסיבות לחשיבותה של סדרת פיבונאצ'י ב[[תורת המספרים]] היא ההתנהגות המעניינת של השאריות שלה בחלוקה ל[[מספר ראשוני]] קבוע. לדוגמה,
*כל מספר שלישי בסדרה הוא זוגי;
*כל מספר רביעי הוא כפולה של 3;
*כל מספר חמישי הוא כפולה של 5.
*כל מספר שביעי הוא כפולה של 13.

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

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

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

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

==חידות שסדרת פיבונאצ'י היא פתרונן==
[[קובץ:FibHive.svg|שמאל|ממוזער|250px|בכמה דרכים שונות ניתן להגיע למשושה מס' 6?]]
ב[[ספר החשבונייה]] מספרי פיבונאצ'י מופיעים בהקשר ל[[חידה]] העוסקת בארנבים. על-פי החידה זוג ארנבים צעיר הופך לאחר שנה לזוג ארנבים מבוגר. לצורך החידה הארנבים לא מתים אף פעם. זוג ארנבים מבוגר בכל שנה מוליד זוג ארנבים נוסף. מתחילים מזוג ארנבים צעיר אחד, כמה זוגות ארנבים יהיו מעתה כל שנה?

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

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

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

==נוסחה ישירה לאברי הסדרה==
אפשר לקבל את אברי הסדרה בצורה ישירה על פי הנוסחה <math>\ F_n = \tfrac{1}{\sqrt5}(\phi_+^{n} - \phi_-^{n})</math> כאשר <math>\ \phi_\pm = \tfrac{1 \pm \sqrt{5}}{2}</math> הם הפתרונות של המשוואה
<math>\phi^2 - \phi - 1\ = 0</math> המאפיינת את [[יחס הזהב]]. יש המייחסים ל[[אדוארד לוקאס]] את גילוי הנוסחה.{{הערה|{{מתמטיקאי|Lucas}}}} אולם הנוסחה הייתה ידועה כבר ל[[ז'אק פיליפ מארי בינה]] בשנת [[1843]],{{הערה|[http://library.thinkquest.org/27890/biographies2.html Édouard Lucas, The Fibonacci Series]}} ואולי אף ל[[לאונרד אוילר]] ב-[[1765]] ואפילו ל[[אברהם דה-מואבר]] ב-[[1730]].{{כ}}{{הערה|{{MathWorld|BinetsFibonacciNumberFormula|Binets Formula}}}}{{הערה|[http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html#finder 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 יתקבלו ערכי הסדרה}}

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

את הנוסחה קל להוכיח ב[[אינדוקציה מתמטית|אינדוקציה]]. כדי לקבל אותה, כמו נוסחאות לסדרות רקורסיה ליניאריות אחרות, אפשר לכתוב את הגדרת הסדרה בעזרת [[מטריצה]] מתאימה:
:<math>
\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}
</math>
מכיוון שהמשוואה האופיינית ב[[מטריצה לכסינה|לכסון המטריצה]] היא משוואת יחס הזהב, אפשר לכתוב:
:<math>
\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}
</math>
והצבה בנוסחת הרקורסיה המטריציונית נותנת את הנוסחה הישירה עבור אברי הסדרה.
:ניתן להווכח בנכונות הנוסחה גם על ידי הנחה שכל חזקות יחס הזהב הם המספר בסדרה כפול יחס הזהב, ועוד המספר הקודם בסדרה.(שהרי יחס הזהב בריבוע הוא יחס הזהב ועוד 1) וכל הכפלה ביחס הזהב נותן את המספרים הבאים בסדרה.
:כעת אם תחבר את שני האיברים במונה תקבל את המספר בסדרה כפול 2 פעמים יחס הזהב פחות המספר בסדרה. ושורש של 5 הוא 2 פעמים יחס הזהב פחות 1.

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

==ראו גם==
*[[קבוע הופכיי מספרי פיבונאצ'י]]
*[[תיקון פיבונאצ'י]]

==לקריאה נוספת==
* [[מריו ליביו]], '''חיתוך הזהב - קורותיו של מספר מופלא''', [[הוצאת אריה ניר]], 2003
* [[אלי מיטב]], '''מספרים מכושפים - על חיתוך הזהב, סדרת פיבונאצ'י ועוד פנינים מתמטיות''', הוצאת שורש, 2008

==קישורים חיצוניים==
{{ויקישיתוף בשורה}}
*[http://shayfam.freevar.com/david/puzzles/puzzle6f.htm מהילברט עד פיבונאצ'י], חידות המתבססות על סדרת פיבונאצ'י
* [https://www.youtube.com/watch?v=u0ve1ZdF5bI הרצאה "מהי מתמטיקה" של יונתן ברויאר - החל מדקה 33 הסבר מפורט ובסיסי על סדרת פיבונאצ'י], באתר [[יוטיוב]]
* סדרת פיבונאצ'י - סרטון הסבר של [https://www.youtube.com/channel/UCOGeU-1Fig3rrDjhm9Zs_wg Vi Hart]: [https://www.youtube.com/watch?v=ahXIMUkSXX0&list=PLF7CBA45AEBAD18B8&index=8 חלק 1] [https://www.youtube.com/watch?v=lOIP_Z_-0Hs&list=PLF7CBA45AEBAD18B8&index=9 חלק 2] [https://www.youtube.com/watch?v=14-NdQwKz9w&index=10&list=PLF7CBA45AEBAD18B8 חלק 3] {{סרטונים}}
* [https://www.youtube.com/watch?v=_NmSEEhtc1U Sequences 3: Fibonacci] – סרטון הסבר של [https://www.youtube.com/channel/UCpDlKkcMDyQyHh5JHZ2HohA MathTV] על סדרת פיבונאצ'י {{באנגלית}} {{סרטונים}}
* [http://www.toolmenow.com/75/Fibonacci-Numbers-Calculator מחשבון לחישוב מספר פיבונאצ'י] {{אנגלית}}
* [http://icalc.co.il/index.php/מחשבונים-מתמטיים/265-מחשבון-סדרת-פיבונאצ-י.html מחשבון סדרת פיבונאצ'י] {{עברית}}
* פזיה מילר, [https://davidson.weizmann.ac.il/online/maagarmada/math_and_comp/פיבונאצ'י סדרת פיבונאצ'י], באתר [[מכון דוידסון]], יולי 2012
* יפעת אדלר בן יעקב, [https://davidson.weizmann.ac.il/online/mathcircle/clips/הקסם-של-מספרי-פיבונצי הקסם של מספרי פיבונאצ'י], באתר מכון דוידסון, דצמבר 2013
* יעל נוריק, [https://davidson.weizmann.ac.il/online/mathcircle/articles/מספרי-פיבונצי-ויחס-הזהב מספרי פיבונאצ'י ויחס הזהב], באתר [[מכון דוידסון]], מאי 2014
* {{אנציקלופדיה למתמטיקה|Fibonacci_numbers}}
* [https://photo-workshops.co.il/צילום-למתקדמים/קומפוזיציה-בצילום-ספירלת-פיבונאצי/ קומפוזיציה בצילום - ספירלת פיבונאצ'י ויחס הזהב] - באתר [https://photo-workshops.co.il/ המרכז לצילום אומנותי], מאת [[גוסטבו הוכמן]]

==הערות שוליים==
{{הערות שוליים}}

{{בקרת זהויות}}
[[קטגוריה:סדרת פיבונאצ'י|*]]
[[קטגוריה:סדרות של שלמים|פיבונאצ'י]]
[[קטגוריה:רקורסיה]]