שלום, היום נמשיך בעיסוק שלנו בסדרות ונפגוש סדרה מאד מפורסמת אני משוכנע שכולכם נתקלתם בה בשלב זה או אחר סדרה הידועה בשם סדרת פיבונאצ'י. פיבונאצ'י היה כינויו של מתמטיקאי איטלקי בן המאה ה-12 וה-13 ששמו היה לאונרדו מפיזה, זה היה הכינוי האחר שלו או פיבונאצ'י. פיבונאצ'י המציא את אותה הסדרה שנושאת את שמו כשהוא חקר מודלים מתמטיים שהיו רלוונטים לחקלאים, במקרה זה התרבות של ארנבים. אני אתאר קודם בצורה מילולית את אותו תהליך שפיבונאצ'י ניסה למדל אז היתה לו הנחת יסוד שאנחנו מתחילים במצב התחלתי מזוג ארנבים- זכר ונקבה בני יומם. העיגול הזה ייצג זוג ארנבים. והנחת המודל שלו, הנחה מלאכותית למדי, היא שלוקח חודש מרגע לידתם של זוג של ארנבים עד שהם יכולים להתחיל ולתת צאצאים בעצמם וברגע שהנקבה בהיריון לוקח חודש עד שנולד זוג של גורים, במקרה זכר ונקבה, כאמור מודל מאד מלאכותי, ואותו זוג חדש רק כעבור חודש יגיע לפרקו ויוכל להתרבות. בנוסף המודל מניח שארנבים לעולם אינם מתים והם גם פוריים לנצח ובואו נראה אם כן מה חוזה המודל של פיבונאצ'י מבחינת אוכלוסיית זוגות של ארנבים בכל חודש וחודש אז כאמור, בנקודת המוצא יש לנו זוג של ארנבים בני יומם, אני מייצג את זה באמצעות עיגול ריק. כעבור חודש אחד זוג הארנבים הזה פורה. אז אני אייצג זוג ארנבים פוריים בעיגול מלא. כעבור חודש בנוסף לאותו הזוג שהתחלנו ממנו יהיה גם זוג של ארנבים שהם הצאצאים של הזוג שהתחלנו ממנו אז נקודת המוצא, כעבור חודש, כעבור חודשיים. מה יהיה כעבור שלושה חודשים? אז הזוג הזה שוב יהרה ויתן לנו זוג חדש של ארנבים בני יומם. הזוג הזה, לעומת זאת, יגיע לגיל חודש ומעתה יהיה פורה. אז יהיה לנו את הזוג ההתחלתי שהוא פורה, הזוג הראשון שנולד שעכשיו גם הוא פורה וזוג חדש, צאצאים שלהם, בני יומם. עבר עוד חודש. הפעם גם אלה וגם אלה הולידו צאצאים, ואלה הגיעו לגיל חודש. אז... כן, אלה שלושת הזוגות האלה, כשאלה מאז גדלו ועוד זוג חדש. וכך התהליך נמשך. אז בואו רק נשים לב שאם אנחנו מונים בכל שלב כמה זוגות של ארנבים יש, היה לנו זוג אחד, בשלב הבא עדיין רק זוג אחד אבל אז שניים, שלושה, חמישה. בואו בלי לצייר רק כיצד זה יימשך, אז בשלב הבא אלה יגיעו לפרקם, אבל לא נקבל מהם זוגות חדשים, אבל נקבל מאלה זוגות חדשים כך שיהיה לנו בסך הכל חמישה ועוד שלושה- שמונה. זה יהיה בשלב הבא ובכן סדרת פיבונאצ'י נולדה מהדוגמה הזאת של הארנבים כשנסמן ב-Fn את מספר זוגות הארנבים N בחודש זאת סדרה שהראשית שלה, הרישא שלה F 1 זה אחד, לאחר מכן עדיין אחד 2, 3, 5, 8 אבל לפחות בשלב הזה אנחנו לכאורה לפחות לא יודעים כיצד הסדרה תימשך. מה שיש לנו כאן זה תיאור מילולי של סדרה שאם נפרוט את המלל הזה, למשל באופן שאני עשיתי את זה, עשיתי פה, כן, איורים, נוכל להמשיך ולבנות את האיברים הבאים בסדרה. פיבונאצ'י לא עצר כאן. השלב הבא היה לנסות ובאמת לייצג באופן מתמטי את המבנה של הסדרה ולהבין כיצד לגזור את האיברים הבאים מהאיברים הקודמים. אז Fn כאמור מייצג את מספר זוגות הארנבים בחודש ה-N. מה אפשר לומר בהינתן Fn על Fn ועוד אחד? כמה זוגות ארנבים יהיו בחודש ה-N ועוד אחד? אז לאור זה שהארנבים האלה לא מתים לעולם, אז יהיו כל אלה שהיו בחודש ה-N, אבל אליהם יתווספו אלה החדשים שנולדו. כמה כאלה יהיו? האם כל Fn הזוגות שהיו בחודש ה-N יילדו? אכן התשובה היא לא, ראינו את זה בדוגמאות האלה, כי תמיד יש זוגות בני יומם שעדיין לא יכולים להתרבות. כמה יהיו בשלב ה-N כאלה שלפחות בני חודש כך שהם יכולים להתרבות? התשובה היא שכל אלה שלפחות בני חודש בשלב ה-N היו כבר בשלב ה-N פחות אחד, כך ש- Fn פחות אחד מספר זוגות הארנבים בחודש ה-N פחות אחד, הם עדיין כיוון שהם לא מתים הם כולם ולכן עדיין קיימים גם בחודש מספר N, והם אלו שיכולים אז להתרבות ולכן הם אלה שתורמים לתוספת בין החודש ה-N לחודש ה-N ועוד אחד. מה שקיבלנו כאן היא נוסחה רקורסיבית לתיאור סדרת פיבונאצ'י. שימו לב להבדל הגדול בין הנוסחה הרקורסיבית הזאת לנוסחאות הרקורסיביות שהכרנו בהקשרים של סדרות חשבוניות והנדסיות. בשתי הדוגמאות ההן איבר היה נקבע לפי האיבר שקדם לו. במקרה זה, איבר נקבע לפי שני איברים, האיברים שקדמו לו. אם כן תזכרו גם שנוסחה רקורסיבית כזאת עדיין לא קובעת באופן יחיד סדרה. בהקשר של סדרות החשבוניות וההנדסיות היינו צריכים לציין במפורש גם מה הוא האיבר הראשון בסדרה. פה מכיוון שכל איבר בסדרה נקבע לפי שני איברים שקודמים לו, כדי שהסדרה תהייה מוגדרת היטב עלינו לציין לא רק מה הוא האיבר הראשון, אלא גם מה הוא האיבר השני, ואז באמצעות הנוסחה הרקורסיבית נוכל למצוא את האיבר השלישי, וכן הלאה, הרביעי, החמישי ואת כל איברי הסדרה. במקרה שלפנינו שני האיברים הראשונים הם 1 ולכן, סדרת פיבונאצ'י מוגדרת באמצעות הנוסחה הרקורסיבית הזאת שקושרת בין איבר לבין שני האיברים שקדמו לו ומציינת במפורש את שני האיברים הראשונים בסדרה. כעת נוכל, מבלי לצייר עיגולים מלאים וריקים להמשיך ולמצוא את איברי הסדרה. אז האיבר השלישי בסדרה, אם לא ציינתי זאת, השתמשתי פה באות F לציון איברי הסדרה... האות הראשונה בשמו של פיבונאצ׳י. האיבר השלישי בסדרה במקרה זה שזה סכום האיבר הראשון ועוד האיבר השני אלה 1 ו-1, אלה מההתחלה של הסדרה שלנו ולכן הוא באמת שווה ל-2 כפי שראינו האיבר הרביעי שווה לסכום שני האיברים שקודמים לו. האיבר החמישי, 5 שווה לסכום שני האיברים שקודמים לו. 8 זה 3 ועוד 5 אם כן ברגע שהבנו את המבנה האיבר הבא שצריך להיות שווה לסכום שני האיברים שקודמים הוא 13 האיבר הבא יהיה 8 ועוד 13, 21 וכן הלאה מהו האיבר ה-100? בסדרת פיבונאצ׳י הוא שווה לסכום האיבר ה-99 והאיבר ה-98 וכדי למצוא את אלה צריך למצוא באופן רקרוסיבי לחזור אחורה עד לאיברים הראשונים הנתונים. נתקלנו בסיטואציה הזאת גם בסדרות הקודמות ובכל המקרים האלה מה שעשינו היה לעבור מהיצוג הרקורסיבי ליצוג מפורש, לנוסחה מפורשת שתאמר לנו כפונקציה של N מהו ערכו של האיבר ה-N בסדרה. זאת אומרת מטרתנו היא לקבל ביטוי מפורש ל-FN כפונקציה של N שאז נציב N שווה 100 ונמצא מהו האיבר ה-100 בסדרת פיבונאצ׳. אלא שאם נתחיל קצת לשחק עם איברים הסדרה נגלה שמה שהיה די קל, מאוד שקוף, במקרה של סדרות חשבוניות והנדסיות נראה פה הרבה יותר מסובך. לא ברור ואני מציע לכולכם לנסות קצת ולשחק עם זה לא ברור, מה יהיה ביטוי לאיבר הכללי בסדרה. בואו רגע נסכל שוב על האיברים הראשונים בסדרה. הסדרה מתחילה מ-1. 1, 2, 3, 5, 8 13, 21, 34. שימו לב תמיד כל איבר אני מסתכל על השניים שקודמים ואני מסכם אותם, 55, 89 ו-144 אני אעצור כאן. 1 הדברים שאנחנו רואים זה שהסדרה גדלה כמובן כל איבר גדול מקודמו. אבל גם שיעור הגידול הולך וגדל. מבחינה מסוימת זה מזכיר לנו קצת את הסדרה ההנדסית. ואתם יכולים לתהות האם באמת יש מנה קבועה בין שני איברים עוקבים. תבדקו, פשוט תסתכלו על המנה בין איברים עוקבים. תראו שהמנה אינה קבועה. אבל בגלל הדמיון לסדרה הנדסית, אני רוצה רגע לתהות קצת יותר לעומק בשאלה האם ייתכן? שהאיבר ה-N של סדרה כדוגמת סדרה פיבונאצ׳י יהיה שווה כמו במקרה של סדרה הנדסית לביטוי מהצורה A כפול Q בחזקת N פחות 1. לו זה היה נכון. כן, היינו צריכים להציב את הביטוי הזה בנוסחת הרקורסיה והיינו רואים שאכן מקבלים שיוויון בשני אגפים. בואו רגע נבדוק את זה. אם זה הביטוי הכללי לאיבר ה-N אז כמובן שהאיבר ה-N ועוד 1 שווה האיבר ה-N פחות 1 שווה ל-A כפול Q בחזקת N שווה ל-AQ בחזקת N פחות 2 וכדי שהביטוים המפורשים האלה יקיימו את נוסחת הרקורסיה הרי שצריך להתקיים ש-AQ בחזקת N יהיה שווה ל-Q, A בחזקת N פחות 1 ועוד A בחזקת QN פחות 2 מה שאני עושה פה זו טכניקה שמשתמשים בה לא מעט במתמטיקה לנסות לנחש מבנה של פתרון ולראות האם הוא אכן קונסיסטנטי קיים פתרון מהצורה הזאת. שימו לב שבמשוואה הזאת בהנחה ש-A שונה מאפס הרי שהוא מתבטל ובאותו אופן בהנחה ש-Q שונה מאפס אז גם אפשר לצמצם Q בחזקת N פחות 2 ולהישאר עם המשוואה הבאה Q בריבוע שווה ל-Q ועוד 1 זו משוואה ריבועית שאתם כמובן יודעים לפתור ואם אכן נפתור אותה נגלה שיש לה שני פתרונות פתרון 1 הוא 1 ועוד שורש 5 חלקי 2. מספר מאוד מפורסם ידוע בשם יחס הזהב. אני לא אכנס כאן להקשרים שלו אבל בהחלט אני ממליץ לקרוא על זה והפתרון השני למשוואה הזאת הוא 1 פחות שורש 5 חלקי 2. מה שזה עתה למדנו בעצם, זה שכל סדרה מהצורה A, אחד ועוד שורש 5 חלקי 2 בחזקת N פחות 1. בואו ניתן שם לסדרה הזאת נקרא לה AN כל סדרה מצורה זו מקיימת את נוסחת הרקורסיה של פיבונאצ׳י. אבל לא רק היא כי באותה מידה יכולתי לבחור בתור מנת הסדרה את הפתרון השני של המשוואה הריבועית זה גם יהיה נכון לומר שכל סדרה מהצורה B ניתן עכשיו שם אחר לקבוע, 1 פחות שורש 5 חלקי 2 בחזקת N פחות 1 גם הסדרה הזו, לא משנה מה הערך של B מקיימת את נוסחת הרקורסיה של פיבונאצ׳י. אני מניח שבשלב זה את קצת מבולבלים, אנחנו מחפשים ביטוי לסדרה שזו נוסחת הרקורסיה שלה ונראה שלמעשה קיבלתי שני ביטויים מפורשים שונים. ששניהם מקיימים את נוסחת הרקורסיה. האם אחד מאלה אבל הוא באמת הביטוי המפורש שחיפשנו לסדרת פיבונאצ׳י? שימו לב שכדי שסדרה תהיה סדרת פיבונאצ׳י, בנוסף לכך שהיא תקיים את נוסחת הרקורסיה הזאת היא צריכה גם לקיים את הערכים האלה של האיבר הראשון והאיבר השני שהם שניהם צריכים להיות 1. אז בואו נקח למשל את הסדרה הראשונה. בואו נתבונן בסדרה AN שווה לקבוע שאותו עוד נוכל לקבוע בהמשך. 1 ועוד שורש 5 חלקי 2 בחזקת M פחות 1. ונשאל האם קיים ערך של A שעבורו הסדרה הזו גם תקיים את נוסחת הרקורסיה שהאיבר ה-N ועוד 1 הוא הסכום של שני האיברים שקדמו לו וגם האיבר הראשון יהיה 1 וגם האיבר השני יהיה 1. אז כדי שהאיבר הראשון יהיה 1, הרי האיבר הראשון בסדרה שלפנינו שווה ל-A כפול מספר בחזקת אפס, כלומר כפול 1. זאת אומרת A הוא האיבר הראשון ואנחנו רוצים שהוא יהיה שווה ל-1 ולכן A שווה 1. האיבר השני לעומת זאת, שווה ל-A כפול 1 ועוד שורש 5 חלקי 2 וגם זה אנחנו רוצים שהוא יהיה 1. אז יש לנו פה 2 משוואות עבור A וברור לנו ששתיהן תתקיימנה בו זמנית. לא קיים A כך שגם המשוואה הזו תהיה נכונה וגם המשוואה הזו. זאת אומרת אנחנו מצאנו גם כאן וגם כאן סדרות שמקיימות את נוסחת הרקורסיה שכל איבר הוא סכום שני איברים שקדמו לו, אבל כל אחת מהן לא משנה כיצד נבחר את הקבועים A ו-B לא יכולה לקיים את שני תנאי ההתחלה של סדרת פיבונאצ׳י. כיצד ניתן אפשר לצאת מהמבוי הסתום שלכאורה הגענו אליו? אחד המאפיינים של משחק הרקורסיה של פיבונאצ׳י זה לינארית. יש לנו פה קשר בין איברי סדרה שכולם הם בחזקה ראשונה נאמר. אוקי, אם חושבים על מה שכתוב כפונקציה של האיברים, האיברים האלה מופיעים בחזקה ראשונה זה מושג הלינאריות אחד המאפיינים של משוואות לינאריות, זה שאם יש לנו שני פתרונות שונים למשוואה שהם שניהם פתרון של המשוואה אז, גם הסכום שלהם הוא פתרון למשוואה. במילים אחרות, טענתי היא, בגלל המבנה הלינארי של נוסחת הרקורסיה של פיבונאצ׳י אם נתבונן בנוסחה כללית שצורתה קבוע 1 ועוד שורש 5 חלקי 2 בחזקת N פחות 1 ועוד קבוע אחר כלשהו: 1 פחות שורש 5 חלקי 2 בואו נקרא לדבר הזה עכשיו FN בחזקת N פחות 1 וזה משהו שארצה שתבדקו בעצמכם כחלק משיעורי הבית שאכן סדרה שזאת צורתה לא משנה מה הערכים של A ו-B מקיימת את נוסחת הרקורסיה של פיבונאצי. שאכן FN ועוד 1 שווה ל-FN ועוד FN פחות 1 המצב עכשיו שונה לחלוטין ממה שהוא היה לפני רגע שכן, עכשיו בידנו סדרה, עדין לא מסוימת יש פה שני קבועים שלא נקבעו שמקיימת את נוסחת הרקורסיה אבל עכשיו יש בידנו שני קבועים שנוכל לשחק איתם שנוכל לקבוע אותם כרצוננו ובאמצעותם לקיים את שני האילוצים שהסדרה צריכה לקיים לגבי הזהות של האיבר הראשון שלה והאיבר השני שלה. אני טוען שמעצם העובדה שעכשיו אין לנו רק קבוע אחד אלא שניים יש ביכולתינו לדאוג לכך ששני אילוצים יתקיימו. כיצד, אז בואו נכתוב, בהנחה שזו הצורה של הסדרה, מה האיבר הראשון אז האיבר הראשון הוא A כפול 1 כי זה חזקת 0 ועוד B כפול 1 האיבר השני שווה ל-A כפול 1 ועוד שורש 5 חלקי 2 בחזקת 1 פה ועוד B כפול 1 פחות שורש 5 חלקי 2 ועכשיו אנחנו רוצים שזה יהיה שווה ל-1 וגם זה יהיה שווה ל-1 שימו לב שלפנינו מערכת של שתי משוואות לינאריות בה נעלמים A ו-B אלה משוואות מהסוג שלמדתם כבר בחטיבת ביניים לפתור זה לא קשה ואני פשוט אומר לכם מה הפתרון במקרה זה זה באמת אלגברה מאוד פשוטה. A במקרה זה יוצא 1 ועוד שורש 5 חלקי פעמיים שורש 5 ו-B שווה לשורש 5 ועוד 1 חלקי פעמיים שורש 5. כל מה שנשאר עכשיו הוא לקחת את הביטוי הזה עבור A להציב אותו חזרה לקחת את הביטוי הזה עבור B להציב אותו כאן. ואם נעשה זאת נקבל סוף סוף את הביטוי המפורש של איברי סדרת פיבונאצ׳י FN האיבר ה-N של סדרת פיבונאצ׳י שווה ל-1 חלקי שורש 5 כפול 1 ועוד שורש 5 לחלק ל-2 בחזקת N. החזקה הפכה ל-N כי יש לנו פה חזקת N פחות 1 אבל אנחנו שוב כופלים ב-1 ועוד שורש 5 ועוד 2, לכן החזקה עכשיו היא חזקה N פחות 1 חלקי שורש 5, 1 פחות שורש 5 חלקי 2 בחזקת N, אני רק אוודא שכתבתי את הדברים בצורה נכונה והתשובה היא שכן ועכשיו באמת כדי, מי שלא מאמין מה שהוא צריך לעשות זה באמת לכתוב בצורה מפורשת את הביטוי ל-FN ועוד 1 FN פחות 1, לבדוק שהמשוואה הזאת מתקיימת להציב N שווה 1 ולראות שמתקבל 1, להציב N שווה 2 לראות שמתקבל 1 ובזאת להשתכנע שזאת הנוסחה המפורשת לאיברי סדרת פיבונאצ׳י ועכשיו אם אנחנו רוצים לדעת מהו האיבר ה-100 בסדרה לא צריך לחשב את כל האיברים שקדמו לו אלא מספיק להציב 100 במקום שבו כתוב N ולקבל ביטוי מפורש שימו לב אולי קצת מפתיע שנוסחה שמופיעים בה השורשים האלה לכל N שנציב יתקבל בסופו של דבר מספר טבעי האמת היא שאני מאוד ממליץ לכם, הרי למדתם בבית ספר לחשב ביטויים מהצורה A ועוד B בחזקת N בוודאי עבור N שווה 1, 2, 3 או 4 אני מאוד ממליץ לכם להציב מפורשות ערכים פה N לפחות עד N שווה 4 ולהשתמש בנוסחת הבינום כדי להעריך את הביטוי הזה ולראות איך השורשים של 5 דואגים תמיד להתבטל ולקבל כמו שאנחנו מצפים כמובן מסדרת פיבונאצי׳ שכל האיברים הם תמיד איברים שלמים. תודה!
