חישוב מספרי Fibonacci בעזרת פונקציות יוצרות

1 ההגדרה של סדרת פיבונצ׳י

סדרת פיבונצ’י \(\{f_n\}_{n=0}^\infty\) היא אחת הסדרות המפורסמות ביותר במתמטיקה. מגדירים \(f_0=0\) ו-\(f_1=1\), ואז עבור \(n\ge2\), מגדירים את הסדרה לפי נוסחת נסיגה:

\(\displaystyle (1) \quad f_n=f_{n-1}+f_{n-2}\)

במילים, כל איבר מתקבל כסכום שני קודמיו. לכן, למשל, \(f_2=f_1+f_0=1+0=1\), \(f_3=f_2+f_1=1+1=2\).

שלושה עשר המספרים הראשונים בסדרת פיבונצ’י הם:

\(\displaystyle 0,1,1,2,3,5,8,13,21,34,55,89,144\)

2 פונקציות יוצרות

במאמר הזה נמצא נוסחה מפורשת לאיבר הכללי \(f_n\) בסדרת פיבונצ’י. למטרה זו ננצל כלי הנקרא פונקציות יוצרות. אבל תחילה, עלינו להזכיר מספר עובדות בנוגע לטור גיאומטרי.

נתבונן בטור

\(\displaystyle \sum_{n=0}^\infty y^n=1+y+y^2+\cdots\)

כאשר \(y\) הוא מספר ממשי. טור נקרא גיאומטרי כאשר היחס בין כל איבר לקודמו הוא קבוע, ואכן כך אצלנו: \(\frac{y^{n+1}}{y^n}=y\) לכל \(n\). נסמן

\(\displaystyle S_n=\sum_{i=0}^ny^i=1+y+y^2+\cdots +y^n\)

מתקיים \(yS_n=y(1+y+\cdots+y^n)=y+y^2+\cdots+y^{n+1}\). לכן,

\(\displaystyle (1-y)S_n=S_n-yS_n=1-y^{n+1}\)

אם \(y\neq1\), נוכל לחלק ומתקבל \(S_n=\frac{1-y^{n+1}}{1-y}\). אם \(|y| \lt 1\), אז כש- \(n\) שואף ל-\(\infty\), \(y^{n+1}\) שואף ל-0, ואנו מגיעים למסקנה כי אם \(|y| \lt 1\) אז

\(\displaystyle (2) \quad \sum_{n=0}^\infty y^n=\lim_{n\to\infty} S_n=\lim_{n\to\infty}\frac{1-y^{n+1}}{1-y}=\frac1{1-y}\)

אבל אם \(y>1\), אז כש- \(n\) שואף ל-\(\infty\), \(y^{n+1}\) שואף ל-\(\infty\), ואנו מגיעים למסקנה כי

\(\displaystyle \sum_{n=0}^\infty y^n=\lim_{n\to\infty} S_n=\lim_{n\to\infty}\frac{y^{n+1}-1}{y-1}=\infty\)

אם \(y=1\), ברור ש- \(\sum_{n=0}^\infty y^n=\infty\). הקורא יכול לחקור את המקרה ש- \(y \lt -1\); לא נצטרך את המקרה הזה כאן. כעת נציג את הכלי של פונקציות יוצרות. אנו בונים פונקציה \(F(x)\) לפי הנוסחה

\(\displaystyle (3) \quad F(x)=\sum_{n=0}^\infty f_nx^n\)

כאשר \(\{f_n\}_{n=0}^\infty\) היא סדרת פיבונצ’י. טור כזה נקרא טור חזקות. מכיוון ש- \(f_0=0\), מתקיים \(F(x)=\sum_{n=0}^\infty f_nx^n=\sum_{n=1}^\infty f_nx^n\). שימו לב כי הטור שמגדיר את \(F(x)\) אינו טור גיאומטרי; אכן היחס בין האיבר ה- \(n\)-י לאיבר ה-\((n+1)\)-י בו הוא \(\frac{f_{n+1}}{f_n}x=\frac{f_{n+1}x^{n+1}}{f_n x^n}\), וזה תלוי ב- \(n\), כלומר אינו מספר קבוע.

 3 פרק לפדנטים שבינינו – מדוע טור החזקות מתכנס

אנחנו נרצה לפעול על טור החזקות שבנוסחה (3), ואת הפעולות האלה צריך להצדיק. מתמטיקה, אחרי הכל, היא מקצוע מדויק!

ברור שהפונקציה \(x^n\) עולה עבור \(x\ge0\); כלומר אם \(x_2\gt x_1 \ge 0\),אז מתקיים \(x_2^n>x_1^n\). לכן גם \(F(x)\) היא פונקציה עולה עבור \(x\ge0\) (כיוון ש- \(f_n>0\) לכל \(n\).) בפרט, אם \(F(x_0)=\infty\), עבור איזה \(x_0>0\), אז בהכרח \(F(x)=\infty\) עבור כל \(x \gt x_0\). או באופן שקול, אם \(F(x_1) \lt \infty\), עבור איזה \(x_1 \gt 0\), אז בהכרח \(F(x) \lt \infty\), עבור כל \(x\) המקיים \(0 \le x \lt x_1\). מזה נובע שאחת משלוש האפשריות הבאות בתוקף:

(1) קיים \(R\ge0\) כך ש- \(F(x) \lt \infty\), עבור \(0 \le x \lt R\), ו- \(F(x)=\infty\), עבור \(x \gt R\) (לא נדבר כאן מה קורה עבור \(x=R\));

(2) \(F(x)=\infty\) עבור כל \(x \gt 0\);

(3) \(F(x) \lt \infty\) עבור כל \(x\ge0\).

במקרה הראשון אנו מגדירים \(R=0\) ובמקרה השלישי \(R=\infty\). המספר \(R\) נקרא רדיוס ההתכנסות של טור החזקות. (אם \(F(x) \lt \infty\), אנו אומרים שהטור מתכנס עבור ה- \(x\) הזה, ואם \(F(x)=\infty\), אומרים שהטור מתבדר עבור ה- \(x\) הזה.) חשוב לציין שכל הנ”ל נוגע למקרה שבו איברי הטור חיוביים; אחרת הסיפור יותר מסובך.

תפקידנו הראשון הוא להראות ש- \(R \gt 0\); אחרת כל הפעולות האלגבריות שנפעיל בהמשך תהיינה חסרות משמעות. (יש טורים עם \(R=0\); כלומר טורים שאינם מתכנסים עבור אף \(x \gt 0\); למשל \(\sum_{n=1}^\infty n!x^n\).) בשלב הזה, נעשה חישוב גס כדי להראות ש- \(R \gt 0\). (עד תום המאמר נקבל את \(R\) במדויק.) הסדרה \(\{f_n\}_{n=0}^\infty\) עולה; כלומר \(f_{n+1} \gt f_n\) לכל \(n\). (זה נראה מובן מאליו ואפשר להוכיח אותו באינדוקציה). אז \(f_n=f_{n-1}+f_{n-2} \lt 2f_{n-1}\). לאור זה, איברי הסדרה \(\{g_n\}_{n=0}^\infty\), המקיימת \(g_0=0\), \(g_1=1\), ו- \(g_n=2g_{n-1}\), עבור \(n\ge2\), הם גדולים מאיברי הסדרה המקורית \(\{f_n\}_{n=0}^\infty\); כלומר, \(g_n\ge f_n\), לכל \(n\ge0\). (נסו להוכיח את זה באינדוקציה: מתקיים \(g_0\ge f_0\) ו- \(g_1\ge f_1\); כעת נניח ש- \(g_n\ge f_n\) ובעזרת הנחה זו וההגדרות של הטורים (\(f_n=f_{n-1}+f_{n-2},\ g_n=2g_{n-1}\)), הוכיחו כי \(g_{n+1}\ge f_{n+1}\).)

מכיוון ש- \(g_n\ge f_n\ge0\), על פי השוואה נובע שאם \(\sum_{n=1}^\infty g_nx^n \lt \infty\), עבור איזה \(x \gt 0\), אז בהכרח \(\sum_{n=0}^\infty f_nx^n \lt \infty\) עבור אותו \(x\). הסדרה \(\{g_n\}_{n=1}^\infty\) פשוטה לחישוב: \(\ g_3=2g_2=2^2\ ,g_2=2g_1=2 \) ובאופן כללי \(g_n=2^{n-1}=\frac12 2^n\), עבור \(n\ge1\). לכן מתקיים

\(\displaystyle \sum_{n=0}^\infty g_nx^n=\sum_{n=1}^\infty g_nx^n=\sum_{n=1}^\infty \frac122^nx^n=\frac12\sum_{n=1}^\infty (2x)^n\)

אבל זה טור גיאומטרי! לכן הטור מתכנס אם \(|2x| \lt 1\), ואז בפרט עבור \(0 \le x \lt \frac12\). לכן, על פי השוואה, הטור שלנו גם הוא מתכנס עבור \(0 \le x \lt \frac12\). אז הוכחנו ש- \(R\ge\frac12\); כלומר ש- \(F(x) \lt \infty\) לפחות עבור \(0\le x \lt \frac12\).

4 ועכשיו לעיקר – איך מקבלים נוסחה למספרי פיבונצ’י מן הפונקציה היוצרת שלהם?

כעת נבצע כמה פעולות אלגבריות פשוטות שתובלנה לנוסחה מפורשת ל- \(F\) (במקום במונחים של טור אינסופי). נכפול ב- \(x^n\) בשני צדדי (1):

\(\displaystyle (4) \quad f_nx^n=f_{n-1}x^n+f_{n-2}x^n\)

עכשיו נסכם את שני צדדי (4) על \(n\) מ- 2 ל- \(\infty\):

\(\displaystyle (5) \quad \sum_{n=2}^\infty f_nx^n=\sum_{n=2}^\infty f_{n-1}x^n+\sum_{n=2}^\infty f_{n-2}x^n\)

מתקיים

\(\displaystyle (6) \quad \sum_{n=2}^\infty f_nx^n=\sum_{n=1}^\infty f_nx^n-f_1x=F(x)-f_1x=F(x)-x\)

\(\displaystyle (7) \quad \sum_{n=2}^\infty f_{n-1}x^n=x\sum_{n=2}^\infty f_{n-1}x^{n-1}=x\sum_{n=1}^\infty f_nx^n=xF(x)\)

\(\displaystyle (8) \quad \sum_{n=2}^\infty f_{n-2}x^n=x^2\sum_{n=2}^\infty f_{n-2}x^{n-2}=x^2\sum_{n=0}^\infty f_nx^n=x^2F(x)\)

מ- (5)-(8) נובע כי \(F(x)-x=xF(x)+x^2F(x)\); או

\(\displaystyle (9) \quad (1-x-x^2)F(x)=x\)

כאן המקום להזכיר כי אנו יודעים ש- \(F(x) \lt \infty\) עבור \(0\le x \lt \frac12\).משום כך כל האלגברה הנ”ל היא “כשרה” עבור \(0\le x \lt \frac12\). וכך קיבלנו נוסחה ל-\(F(x)\):

\(\displaystyle (10) \quad sum_{n=0}^\infty f_nx^n=F(x)=\frac x{1-x-x^2}, \ 0\le x<\frac12\)

אם נדע לפתח את הפונקציה \(\frac{x}{1-x-x^2}\) לטור חזקות, כלומר נדע את המקדמים, נדע את מספרי פיבונצ’י. מתברר שלא כל כך קשה לפתח את הפונקציה הזאת לטור חזקות. עושים זאת בעזרת שיטה שנקראת שברים חלקיים.

הצעד הראשון בשיטה הזאת הוא לפרק את המכנה לגורמים ליניאריים. את זה אתם בוודאי יודעים לעשות – זה מצריך פתרון של המשוואה הריבועית \(x^2+x-1=0\). לפי הנוסחה לפתרון משוואה ריבועית, השורשים של \(x^2+x-1\) הם \(\frac{-1 \pm\sqrt5}2\); נסמן

\(\displaystyle r^+=\frac{-1+\sqrt5}2\approx.618,\ \ r^-=\frac{-1-\sqrt5}2\)

קל לחשב:

\(\displaystyle r^-r^+=(\frac{-1-\sqrt5}2)(\frac{-1+\sqrt5}2)=-1\)

(הדבר נובע גם מנוסחת ויאטה — מכפלת השורשים היא האיבר החופשי.)

מכאן נובע ש: \((x-r^+)(x-r^-)=-r^-r^+(x-r^+)(x-r^-)=-(xr^-+1)(xr^++1)\).

כעת נשתמש בשיטת השברים החלקיים כדי להציג את הפונקציה \(\frac x{1-x-x^2}\) כטור חזקות עם מקדמים מפורשים. מתקיים

\(\displaystyle x^2+x-1=(x-r^+)(x-r^-)=-(xr^-+1)(xr^++1)\)

לכן מתקיים

\(\displaystyle (11) \quad \frac x{1-x-x^2}=\frac x{(xr^-+1)(xr^++1)}\)

נרשום

\(\displaystyle (12) \quad \frac x{(xr^-+1)(xr^++1)}=\frac \alpha{xr^-+1}+\frac \beta{xr^++1}\)

שיטת השברים החלקיים אומרת שבהכרח קיימים \(\alpha\) ו-\(\beta\) שמקיימים את השוויון הזה. ואמנם, אנחנו נמצא אותם. מתקיים

\(\displaystyle \frac \alpha{xr^-+1}+\frac \beta{xr^++1}=\frac{x(\alpha r^++\beta r^-)+(\alpha+\beta)}{(xr^-+1)(xr^++1)}\)

לכן

\(\displaystyle \frac x{(xr^-+1)(xr^++1)}=\frac{x(\alpha r^++\beta r^-)+(\alpha+\beta)}{(xr^-+1)(xr^++1)}\)

על פי השוואת מקדמים, אפשר להסיק כי \(\alpha r^++\beta r^-=1\) ו- \(\alpha+\beta=0\). פותרים את שתי המשוואות האלה ומקבלים \(\alpha=\frac1{r^+-r^-}=\frac1{\sqrt5}\) ו- \(\beta=\frac1{r^–r^+}=-\frac1{\sqrt5}\). אנו מציבים עבור \(\alpha\) ו- \(\beta\) ב- (12) ומשתמשים ב- (11) כדי לקבל

\(\displaystyle (13) \quad \frac x{1-x-x^2}=\frac1{\sqrt5}\Big(\frac1{1+xr^-}-\frac1{1+xr^+}\Big)\)

נתבונן ב- \(\frac1{1+xr^-} = \frac1{1-(-xr^-)}\). אם נסמן \(y=-xr^-\), נוכל ליישם את (2) ל- \(\frac1{1+xr^-}\) אם \(x\) מקיים \(|-xr^-|<1\); כלומר, אם

\(\displaystyle |x| \lt \frac1{|r^-|}=\frac2{1+\sqrt{5}}=\frac{\sqrt{5}-1}2\)

באופן דומה, אם נסמן \(y=-xr^+\), נוכל ליישם את (2) ל- \(\frac1{1+xr^+}\) אם \(x\) מקיים \(|-xr^+| \lt 1\); כלומר, אם

\(\displaystyle |x| \lt \frac1{|r^+|}=\frac2{-1+\sqrt{5}}=\frac{\sqrt{5}+1}2\)

מכיוון ש-\(\frac{\sqrt{5}+1}2 \gt \frac{\sqrt{5}-1}2\), נוכל ליישם את (2) גם ל- \(\frac1{1+xr^-}\) וגם ל- \(\frac1{1+xr^+}\) עבור \(x\) שמקיים \(|x| \lt \frac{\sqrt{5}-1}2\). אז מתקיים

\(\displaystyle (14) \quad \frac1{1+xr^-}=\sum_{n=0}^\infty(-xr^-)^n=\sum_{n=0}^\infty(\frac{1+\sqrt5}2)^nx^n\)

ו-

\(\displaystyle (15) \quad \frac1{1+xr^+}=\sum_{n=0}^\infty(-xr^+)^n=\sum_{n=0}^\infty(\frac{1-\sqrt5}2)^nx^n\)

מ- (13)-(15) אנו מגיעים למסקנה כי

\(\displaystyle (16) \quad \frac x{1-x-x^2}=\sum_{n=0}^\infty\frac1{\sqrt5}\Big((\frac{1+\sqrt5}2)^n-(\frac{1-\sqrt5}2)^n \Big)x^n, \ 0\le x \lt \frac{\sqrt{5}-1}2\)

אם נשווה את (10) ו- (16), נוכל להסיק ש:

\(\displaystyle (17) \quad \sum_{n=0}^\infty f_nx^n=\sum_{n=0}^\infty\frac1{\sqrt5}\Big((\frac{1+\sqrt5}2)^n-(\frac{1-\sqrt5}2)\Big)x^n,\ 0\le x \lt \frac12\)

עכשיו אנו מזכירים משפט יסודי מחדו”א.

תהיינה \(\{a_n\}_{n=0}^\infty\) ו- \(\{b_n\}_{n=0}^\infty\) סדרות ויהא \(C \gt 0\). נניח שטור החזקות \(\sum_{n=0}^\infty a_nx^n\) מתכנס עבור \(0\le x \lt C\), ושמתקיים \(\sum_{n=0}^\infty a_nx^n=\sum_{n=0}^\infty b_nx^n\), עבור \(0\le x \lt C\). אזי \(a_n=b_n\) לכל \(n\).

מיישמים את המשפט הנ”ל ל- (17), כאשר \(a_n=f_n\), \(b_n=\frac1{\sqrt5}\Big((\frac{1+\sqrt5}2)^n-(\frac{1-\sqrt5}2)\Big)\) ו-\(C=\frac12\); המסקנה היא שהנוסחה המפורשת עבור האיבר ה- \(n\)-י בסדרת פיבונצ’י היא

\(\displaystyle f_n=\frac1{\sqrt5}\Big((\frac{1+\sqrt5}2)^n-(\frac{1-\sqrt5}2)^n\Big)\)

עכשיו שיש בידינו נוסחה מפורשת ל- \(f_n\), נוכל להראות בקלות שרדיוס ההתכנסות האמיתי של \(\sum_{n=0}^\infty f_nx^n\) הוא \(\frac2{1+\sqrt{5}}\approx.618\). אנו משאירים את זה לקורא – הטור \(\sum_{n=0}^\infty f_nx^n\) הוא הפרש של שני טורים גיאומטריים. רצוי להדגיש כמה חשוב היה הצד הראשון בהוכחתנו – חישוב גס המראה שרדיוס ההתכנסות הוא חיובי אפשר לנו להפעיל את המשפט הנ”ל עם \(C=\frac12\).

שימו לב כי \(\frac{1+\sqrt5}2\approx1.618\) ו- \(\frac{1-\sqrt5}2\approx-.618\).מכיוון ש- \(\frac{1-\sqrt5}2 \lt 0\), הסימן של \((\frac{1-\sqrt5}2)^n\) מתחלף – שלילי עבור \(n\) אי-זוגי וחיובי עבור \(n\) זוגי. הרבה יותר חשוב, שימו לב כי לכל \(n\ge0\) מתקיים

\(\displaystyle |\frac1{\sqrt{5}}(\frac{1-\sqrt5}2)^n|\le \frac1{\sqrt{5}} \lt \frac12\)

לכן, מכיוון ש- \(f_n\) הוא מספר שלם, נובע כי \(f_n\) הוא המספר השלם הקרוב ביותר ל- \(\frac1{\sqrt5}(\frac{1+\sqrt5}2)^n\). למשל, חישוב במחשבון מגלה כי \(\frac1{\sqrt5}(\frac{1+\sqrt5}2)^{50}\approx12586269024.99998\); לכן \(f_{50}=12,586,269,025\).

אכן הפונקציה \(F(x)=\frac x{1-x-x^2}\) “יצרה” לנו את מספרי פיבונצ’י!

2 תגובות על חישוב מספרי Fibonacci בעזרת פונקציות יוצרות

  • מאת Doron Zeilberger‏:

    Very nice article, BUT the part for the “pedants” is meyutar
    Everything makes sense in the context of the fully rigorous algebra of
    “formal power series” and using analysis is nit necessary.

  • מאת admin‏:

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