פונקציות יוצרות ומספרי קטלן

מבוא

בפוסט הקודם שלי כתבתי על מספרי קטלן, סדרת המספרים \( 1,1,2,5,14,42,\ldots \). הראיתי נוסחת נסיגה עבורה, \( C_{n+1}=\sum_{k=0}^{n}C_{k}C_{n-k} \); הראיתי נוסחה סגורה עבורה, \( C_{n}=\frac{1}{n+1}{2n \choose n} \); והראיתי שלל בעיות ספירה שמספרי קטלן פותרים, משילושים של מצולעים, עבור בעצים בינאריים וכלה במגדלי קפלר. רק דבר אחד לא הראיתי, למרות שהוא מושג מרכזי וחשוב בקומבינטוריקה באופן כללי: את הפונקציה היוצרת של מספרי קטלן. לא עשיתי את זה כי זה היה מעלה פי כמה את רמת הטכניות של הפוסט ומרחיק אותי מהנושא המעניין בו, שהוא מספרי קטלן עצמם; אבל עכשיו אחרי שהתרגלנו אליהם (או דילגנו לגמרי על הפוסט הקודם כי אנחנו רוצים את האקשן שיהיה כאן) אפשר להפנות זרקור אל פונקציות יוצרות בכלל, וזו של מספרי קטלן בפרט.

כמיטב מסורת הבלוג, כבר יש לי פוסט על הנושא הזה, כולל אזכור של מספרי קטלן, אבל הפעם אני רוצה לחפור ולהציג נושאים שרק נגעתי בהם בעבר ברמת פורמליות הרבה יותר גדולה. זה אומר שהפוסט יהיה טכני יחסית, ויילך ויסתבך ככל שאתקדם, אבל נגיע לפונקציה היוצרת של קטלן יחסית מהר; האתגר יהיה להבין למה הפונקציה היוצרת הזו “חוקית” וכמה אפשר להכליל את זה. אני אגלה מראש כבר עכשיו שהפונקציה היוצרת היא \( C\left(x\right)=\frac{1-\sqrt{1-4x}}{2x} \), אבל - מה זה בעצם אומר? ואיך מגיעים לזה? בשביל זה אני אצטרך לדבר קצת על דברים.

למה פונקציות יוצרות זה כמו פולינומים, רק פשוט יותר

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

\( a\left(x\right)=\sum_{n=0}^{d}a_{n}x^{n} \)

כאשר \( d \) הוא דרגת הפולינום - החזקה הגבוהה ביותר שלו שהמקדם שלה שונה מאפס. עכשיו, על פולינומים אפשר להגדיר פעולות חיבור וכפל, אז בשביל להדגים את זה בואו נציג שני פולינומים מדרגות \( d_{1},d_{2} \):

\( a\left(x\right)=\sum_{n=0}^{d_{1}}a_{n}x^{n} \)

\( b\left(x\right)=\sum_{n=0}^{d_{2}}b_{n}x^{n} \)

עכשיו החיבור מוגדר “איבר-איבר”:

\( a\left(x\right)+b\left(x\right)=\sum_{n=0}^{\max\left\{ d_{1},d_{2}\right\} }\left(a_{n}+b_{n}\right)x^{n} \)

וזה בסך הכל יפה מאוד חוץ מהאיכסה של ה-\( \max\left\{ d_{1},d_{2}\right\} \) למעלה שגם מצריך אותנו לענות על שאלות קשות כמו מה המקדמים של פולינום מעבר לדרגה המקסימלית שלו (אפס. הם אפס).

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

\( \left(a_{1}x+a_{0}\right)\left(b_{1}x+b_{0}\right)=a_{1}b_{1}x^{2}+\left(a_{0}b_{1}+a_{1}b_{0}\right)x^{1}+a_{0}b_{0}x^{0} \)

כדאי לחשב את הדוגמא הזו ידנית, או אפילו משהו עם איבר אחד נוסף לאחד הפולינומים, כדי לקבל תחושה טובה של “מה הולך פה”. מה שמקבלים הוא שהמקדם של כל חזקה של \( x^{n} \) הוא סכום של איברים, כשכל איבר הוא מכפלה של מקדם של \( a\left(x\right) \) ומקדם של \( b\left(x\right) \), כשהמקדמים נבחרים כך שסכום האינדקסים של שניהם יוצא \( n \).

כדי לכתוב נוסחה כללית עבור זה, קודם כל אני אכתוב

\( a\left(x\right)\cdot b\left(x\right)=\sum_{n=0}^{d_{1}+d_{2}}c_{n}x^{n} \)

ועכשיו אפשר להגיד מהו כל מקדם \( c_{n} \) שכזה:

\( c_{n}=\sum_{k=0}^{n}a_{k}b_{n-k} \)

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

ראשית, אפשר לחשוב על הפולינומים כאילו הם מקודדים סדרת מספרים - סדרת המקדמים שלהם. בצורה הזו, חיבור פולינומים מתורגם לחיבור נקודתי של שתי סדרות, וכפל פולינומים מתורגם לפעולת קונבולוציה של הסדרות. חיבור נקודתי אנחנו מכירים, אבל קונבולוציה היא פעולה שיכול לקחת זמן עד שפוגשים אותה בשם הזה לראשונה (אני נתקלתי בה בלימודים רק בסמסטר מתקדם יחסית - וכמובן, באותו סמסטר היא הופיעה שוב ושוב בשלל קורסים שונים ובלתי תלויים; עבורי במקום לומר “אפקט באדר-מיינהוף” אפשר לומר “אפקט הקונבולוציה”) אבל הנה, אנחנו רואים שבעצם הכרנו אותה מאז ומעולם, או לפחות מאז שהכרנו כפל פולינומים.

שנית, שתי הפעולות הללו של חיבור וכפל הופכות את הפולינומים לחוג. אני לא אניח שהמושג הזה מוכר כאן; לסטודנטים יכול לקחת טיפה זמן עד שהם נתקלים בו לראשונה, למרות החשיבות העצומה שלו למתמטיקה, אבל אני מניח שאנחנו כן מכירים שדות, כי כבר באלגברה לינארית מתעסקים איתם. שדות הן קבוצות עם פעולת חיבור וכפל שמתנהגות ממש נחמד - אפילו נחמד מדי. למשל, אפשר לחלק בכל איבר. כשעוברים לדבר על חוג אנחנו משאירים את הדרישות של ההתנהגות הנחמדה מפעולת החיבור, וממשיכים לדרוש את חוק הפילוג (“דיסטריביוטיביות”) אבל מכפל אנחנו דורשים הרבה פחות; שיהיה אסוציאטיבי וזהו בערך. עכשיו, פולינומים דווקא מתנהגים לא רע בכלל - הכפל הוא קומוטטיבי, יש לו יחידה ואי אפשר בטעות לקבל אפס על ידי הכפלה של שני איברים שאינם אפס: זה הופך פולינומים למה שנקרא תחום שלמות, שזה משהו שהאבטיפוס שלו הוא המספרים השלמים. כשהמקדמים של הפולינומים הם מעל שדה \( F \) אנחנו מסמנים את חוג הפולינומים המתאים ב-\( F\left[x\right] \), משתמשים בו לשלל מטרות יפות (למשל, בנייה של שדות שמרחיבים את \( F \)) וכולם מרוצים.

אבל אני לא רוצה לדבר על פולינומים. אני רוצה לדבר על טורי חזקות פורמליים.

מה ההבדל בין פולינומים לטורי חזקות פורמליים? פשוט מאוד. הנה פולינום:

\( a\left(x\right)=\sum_{n=0}^{d}a_{n}x^{n} \)

הנה טור חזקות פורמלי:

\( a\left(x\right)=\sum_{n=0}^{\infty}a_{n}x^{n} \)

כלומר, במקום סכום של \( d+1 \) איברים, יש לנו סכום של אינסוף איברים. לראות סכום כזה מייד מעלה את השאלה הקשה - למה זה מתכנס? אבל כשמדברים על “טור חזקות פורמלי” ה”פורמלי” אומר בדיוק שהטור קיים גם בלי לעמוד בדרישות התכנסות כלשהן. זו הנקודה שנשמעת הכי חשודה בסיפור אז בואו נעשה את זה לאט.

בהחלט יש משמעות לשאלות התכנסות כשאני לוקח טור כמו \( \sum_{n=0}^{\infty}\frac{1}{2^{n}} \) ושואל מה הסכום שלו. כאן יש לנו סדרה \( \left\{ a_{n}\right\} _{n=0}^{\infty} \)של מספרים ממשיים, \( a_{n}=\frac{1}{2^{n}} \). אנחנו יודעים לחבר שני מספרים ממשיים, ובאינדוקציה גם שלושה, ארבעה וכן הלאה - כל מספר סופי שלהם. אבל להתאים מספר קונקרטי לסכום של אינסוף מביניהם - זה כבר דורש טכניקות נוספות, ולא בהכרח תמיד יעבוד. אפשר לכתוב \( \sum_{n=0}^{\infty}\frac{1}{2^{n}}=2 \) בעזרת השיטה המקובלת לסכימה של טור אינסופי, אבל היא גם תאלץ אותנו לכתוב \( \sum_{n=0}^{\infty}2^{n}=\infty \). העניין הוא שבשני המקרים הללו, בין אם הטור מתכנס ובין אם לא, אף אחד לא חושב שיש בעיה עם קיום הסדרה: גם הסדרה \( \left\{ \frac{1}{2^{n}}\right\} _{n=0}^{\infty} \) וגם הסדרה \( \left\{ 2^{n}\right\} _{n=0}^{\infty} \) הן אובייקטים שאנחנו לא מערערים על הקיום שלהם, אלא רק תוהים לגבי השאלה האם לאותם אובייקטים אפשר להתאים מספר שיתאר במובן מסויים את הסכום שלהם.

עם טורי חזקות פורמליים זה אותו דבר. אם הסימון \( \sum_{n=0}^{\infty}a_{n}x^{n} \) מעורר בנו אי נוחות כי אנחנו מצפים, כשאנחנו רואים סכום, שהוא יתכנס למשהו, הרי שלראות את \( \left(a_{0},a_{1},a_{2},\ldots\right) \) לא יעורר בנו את אותו סוג של אי נוחות, אבל שני אלו הם פשוט סימונים שונים לאותו דבר. כמו שהרברט וילף כותב ב-generatingfunctionology שלו: פונקציות יוצרות הן חבל כביסה שעליו אנחנו תולים מספרים לתצוגה.

אחרי שאנחנו מוכנים לקבל את הקיום של אובייקט כמו \( a\left(x\right)=\sum_{n=0}^{\infty}a_{n}x^{n} \), אפשר לעבור לדבר על מה שעושים איתו - ומה שעושים איתו הוא אלגברה, כלומר פעולות כמו חיבור וכפל. ראינו את ההגדרה עבור פולינומים; איך היא תשתנה עבור טורי חזקות? ובכן, עבור חיבור היא תהפוך מ-

\( a\left(x\right)+b\left(x\right)=\sum_{n=0}^{\max\left\{ d_{1},d_{2}\right\} }\left(a_{n}+b_{n}\right)x^{n} \)

אל

\( a\left(x\right)+b\left(x\right)=\sum_{n=0}^{\infty}\left(a_{n}+b_{n}\right)x^{n} \)

עבור כפל היא תהפוך מ-

\( a\left(x\right)\cdot b\left(x\right)=\sum_{n=0}^{d_{1}+d_{2}}c_{n}x^{n} \)

אל

\( a\left(x\right)\cdot b\left(x\right)=\sum_{n=0}^{\infty}c_{n}x^{n} \)

כאשר בשני המקרים

\( c_{n}=\sum_{k=0}^{n}a_{k}b_{n-k} \)

במילים אחרות, ההגדרה הפכה להיות אלגנטית יותר כי לא צריך להסתבך עם הדרגות המעצבנות של הפולינומים. למה זה עובד, למרות שבטור חזקות יש אינסוף איברים? כי גם בהגדרת החיבור וגם בהגדרת הכפל, הערך של כל מקדם הוא סכום סופי של איברים. המקדמים הם לא איברים פורמליים בעצמם; הם מספרים ממשיים (או מרוכבים, או איברים בשדה אחר). אז ביטוי כמו \( a_{n}+b_{n} \) הוא סכום של שני מספרים ממשיים, וסכום כזה בוודאי קיים; וביטוי כמו \( \sum_{k=0}^{n}a_{k}b_{n-k} \) הוא סכום יותר מורכב אבל עדיין כזה שכולל רק מספר סופי של מחוברים. אם היו אינסוף מחוברים, אז היינו בצרות. אבל אנחנו לא בצרות, ובדיוק כמו שעבור הפולינומים קיבלנו חוג שמסומן ב-\( F\left[x\right] \), גם עבור טורי חזקות קיבלנו חוג, ואפילו תחום שלמות (ואפילו תחום שלמות עם כל מני תכונות אלגבריות נחמדות שלא אכנס אליהן) שמסומן ב-\( F\left[\left[x\right]\right] \).

קצת חימום טכני - הטור ההנדסי האינסופי ומספרי פיבונאצ'י

בואו נראה שתי דוגמאות פשוטות לעבודה עם פונקציות יוצרות. ראשית, ניקח את הסדרה הממש פשוטה \( a_{n}=1 \), כלומר את הפונקציה היוצרת \( 1+x+x^{2}+x^{3}+\ldots \). אם נכפול אותה ב-\( \left(1-x\right) \), שהוא הפונקציה היוצרת \( \sum_{n=0}^{\infty}b_{n}x^{n} \) עם

\( b_{n}=\begin{cases} 1 & n=0\\ -1 & n=1\\ 0 & n>1 \end{cases} \)

\( \left(1+x+x^{2}+x^{3}+\ldots\right)\left(1-x\right)=\sum_{n=0}^{\infty}c_{n}x^{n} \)

כאשר \( c_{0}=a_{0}b_{0}=1 \) ו-\( c_{1}=a_{0}b_{1}+a_{1}b_{0}=b_{1}+b_{0}=0 \)

ובאופן כללי, בגלל שכל ה-\( a_{n} \)-ים הם 1 אז בעצם \( \sum_{k=0}^{n}a_{k}b_{n-k}=\sum_{k=0}^{n}b_{n-k} \), ומכיוון שסכום כל ה-\( b \)-ים החל מ-\( b_{0} \) ועד למקום כלשהו הוא סכום של 1, מינוס 1 ועוד אפסים, נקבל \( c_{n}=0 \) לכל \( n>0 \). המסקנה היא ש-

\( \left(1+x+x^{2}+x^{3}+\ldots\right)\left(1-x\right)=1 \)

במילים אחרות, בחוג \( F\left[\left[x\right]\right] \) האיבר \( 1+x+x^{2}+\ldots \) הוא הפיך וההופכי שלו הוא \( \left(1-x\right) \). כדי לתאר את זה בצורה שקל לנו לעכל, אוהבים לסמן את זה כך:

\( 1+x+x^{2}+\ldots=\frac{1}{1-x} \)

קרוב לודאי שאתם מכירים את השוויון הזה בתור נוסחת הסכום של סדרה הנדסית מתכנסת - אבל כאן הוכחנו את הנכונות שלו בלי שיקולי התכנסות! ה”מחיר” הוא שאי אפשר להציב ערכים ב-\( x \) ולצפות שהשויון יתקיים עבורם; למשל אם נציב \( x=2 \) נקבל את הסכום הידוע לשמצה \( 1+2+4+8+\ldots=-1 \) (שנראה מופרך אבל הוא בעצם לא מופרך בכלל, אם אנחנו לא במספרים הממשיים אלא במקום קסום אחר).

בואו נעבור לדוגמא קצת יותר מחוכמת: סדרת פיבונאצ’י. הסדרה הזו מוגדרת על ידי הגדרה רקורסיבית: \( F_{0}=1,F_{1}=1 \) ו-\( F_{n}=F_{n-1}+F_{n-2} \). הגדרה רקורסיבית שכזו נותנת לנו דרך פשוטה לגלות מה הפונקציה היוצרת של הסדרה \( F_{0},F_{1},F_{2},\ldots \). ראשית כל, נכתוב

\( F\left(x\right)=\sum_{n=0}^{\infty}F_{n}x^{n} \)

עכשיו, היינו רוצים להציב במקום \( F_{n} \) את \( F_{n}=F_{n-1}+F_{n-2} \), אבל אי אפשר לעשות את זה מיידית, כי עבור \( n=0,1 \) הנוסחה הזו לא מתקיימת. אז נפריד את הסכום לשני האיברים הראשונים וכל היתר:

\( F\left(x\right)=\left(1\cdot x^{0}+1\cdot x^{1}\right)+\sum_{n=2}^{\infty}F_{n}x^{n}=\left(1+x\right)+\sum_{n=2}^{\infty}\left(F_{n-1}+F_{n-2}\right)x^{n} \)

\( =\left(1+x\right)+\sum_{n=2}^{\infty}F_{n-1}x^{n}+\sum_{n=2}^{\infty}F_{n-2}x^{n} \)

המטרה שלי היא לנסות לגרום לשני הסכומים הללו להיראות כמו הסכום המקורי שהגדיר את הפונקציה היוצרת של פיבונאצ’י. בואו נסתכל על \( \sum_{n=2}^{\infty}F_{n-2}x^{n} \) קודם - אני יכול לשנות את אינדקס הסכימה. כלל אצבע שקל לזכור הוא - אני יכול להגדיל את האינדקס באיזה ערך שאני רוצה (במקרה הנוכחי, 2) בתנאי שאני מקטין את הערך ההתחלתי באותה כמות. כלומר:

\( \sum_{n=2}^{\infty}F_{n-2}x^{n}=\sum_{n=0}^{\infty}F_{n}x^{n+2}=x^{2}\sum_{n=0}^{\infty}F_{n}x^{n}=x^{2}F\left(x\right) \)

עבור \( \sum_{n=2}^{\infty}F_{n-1}x^{n} \) זה יהיה טיפה טריקי יותר כי אם אני אגדיל את אינדקס הסכימה ב-1, אני עדיין לא אקבל את \( F\left(x\right) \) בסכום, כי:

\( \sum_{n=2}^{\infty}F_{n-1}x^{n}=\sum_{n=1}^{\infty}F_{n}x^{n+1}=x\sum_{n=1}^{\infty}F_{n}x^{n} \)

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

\( x\sum_{n=1}^{\infty}F_{n}x^{n}=x\left(\sum_{n=0}^{\infty}F_{n}x^{n}-1\right)=xF\left(x\right)-x \)

ולכן מכל זה קיבלנו

\( F\left(x\right)=\left(1+x\right)+x^{2}F\left(x\right)+xF\left(x\right)-x=\left(x^{2}+x\right)F\left(x\right)+1 \)

עכשיו אפשר להעביר את \( F\left(x\right) \) אגף ולהוציא גורם משותף - אלו פעולות תקינות בכל חוג. נקבל:

\( F\left(x\right)\left(1-x^{2}-x\right)=1 \)

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

\( F\left(x\right)=\frac{1}{1-x^{2}-x} \)

וזו הפונקציה היוצרת של מספרי פיבונאצ’י (כשהם מתחילים מ-1 ולא מ-0). בשביל מה זה היה טוב? מה אפשר לעשות איתה שלא יכלנו לעשות בלעדיה? זה סיפור אחר - אפשר למשל לקבל ממנה את הנוסחה הסגורה למספרי פיבונאצ’י, או הערכות אסימפטוטיות על קצב הגידול שלה; כל זה מצריך לקחת את הפונקציה היוצרת ולזרוק עליה כלים סטנדרטיים שיודעים לטפל באנליזה של פונקציות רציונליות. הדגש פה הוא על סטנדרטיים - זו הסיבה שמתמטיקאים אוהבים פונקציות יוצרות, זו דרך קומפקטית לייצר סדרות, שאחר כך אפשר להשתמש עליה בכל המתמטיקה שאנחנו מכירים.

כדי לסיים את החלק הזה אני צריך להוכיח את מה שטענתי קודם: ש-\( a\left(x\right)=\sum_{n=0}^{\infty}a_{n}x^{n} \) הוא הפיך אם ורק אם \( a_{0} \) הפיך. הרעיון בבסיסו הוא אותו רעיון כמו ההיפוך של \( 1+x+x^{2}+\ldots \) רק שהפעם במקום לזרוק מהשמיים את ההופכי אני אסביר איך מוצאים אותו.

אם קיים הופכי, \( b\left(x\right)=\sum_{n=0}^{\infty}b_{n}x^{n} \), מה המקדמים שלו חייבים להיות? אנחנו יודעים ש-\( a\left(x\right)b\left(x\right)=1 \) (כי זו ההגדרה של הופכי), כלומר אם נכתוב \( a\left(x\right)\cdot b\left(x\right)=\sum_{n=0}^{\infty}c_{n}x^{n} \) אז \( c_{0}=1 \) ו-\( c_{n}=0 \) לכל \( n>0 \).

מהשוויון הראשון אנחנו מקבלים \( a_{0}b_{0}=1 \). כלומר, אם \( a\left(x\right) \) היה הפיך אז השוויון הזה מראה לנו ש-\( a_{0} \) הפיך ו-\( b_{0} \) הוא ההופכי שלו; זה כיוון אחד של ההוכחה. הכיוון המורכב יותר הוא להניח ש-\( a_{0} \) הפיך ולכן באמת קיים לו הופכי \( b_{0} \), וזה נותן לנו את ההתחלה של הבניה של \( b\left(x\right) \), אבל צריך להראות שאפשר לבנות גם את יתר המקדמים.

למרבה המזל, יתר המקדמים מתקבלים מאליהם, בדרך אינדוקטיבית. נניח שכבר ידועים לנו המקדמים \( b_{0},\ldots,b_{n-1} \) ונבנה את \( b_{n} \). מכיוון ש-\( n>0 \) אז \( c_{n}=0 \) ולכן השוויון \( c_{n}=\sum_{k=0}^{n}a_{k}b_{n-k} \) שמגדיר את המקדם במכפלה נותן לנו:

\( 0=\sum_{k=0}^{n}a_{k}b_{n-k} \)

כלומר

\( a_{0}b_{n}=-\sum_{k=1}^{n}a_{k}b_{n-k} \)

עכשיו, אמרנו כבר ש-\( a_{0} \) הפיך, אז אפשר לחלק בו - כלומר, לכפול ב-\( b_{0} \), ולקבל:

\( b_{n}=-b_{0}\sum_{k=1}^{n}a_{k}b_{n-k} \)

אגף ימין מורכב כולו מפעולת חוקיות בחוג \( F \) שמעליו אנחנו מגדירים את \( F\left[\left[x\right]\right] \), כך שהבניה עובדת וזה מסיים את ההוכחה! לא רק שהוכחנו ש-\( a\left(x\right) \) הפיך, גם עשינו את זה בדרך קונסטרוקטיבית שמוצאת את ההופכי שלו.

הפונקציה היוצרת של מספרי קטלן

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

יש כמה דרכים להגיע אל הפונקציה היוצרת של מספרי קטלן, ואחת הפשוטות שבהן היא להניח שכבר מצאנו את נוסחת הנסיגה שלהם, שראינו בפוסט הקודם: \( C_{n+1}=\sum_{k=0}^{n}C_{k}C_{n-k} \), עם תנאי ההתחלה \( C_{0}=1 \). הנוסחה הזו גם מזכירה קצת את זו של פיבונאצ’י ולכן הטכניקה שבה השתמשנו עבור פיבונאצ’י נראית מבטיחה כאן - אבל אפילו עוד יותר מכך, הנוסחה הזו מזכירה את איך שמכפלת פולינומים עובדת: \( c_{n}=\sum_{k=0}^{n}a_{k}b_{n-k} \). רק הקטע הזה עם ה-\( n+1 \) טיפה שונה. בואו נראה איך זה יסתדר לנו.

נתחיל עם להגדיר את הפונקציה היוצרת: \( C\left(x\right)=\sum_{n=0}^{\infty}C_{n}x^{n} \). עכשיו, בואו נכפיל את \( C\left(x\right) \) בעצמה כדי לנסות לקבל משהו שנראה כמו הנוסחה למכפלת פולינומים. אני אסמן את ההכפלה של \( C\left(x\right) \) בעצמה ב-\( C\left(x\right)^{2} \) - גם זה סימון סטנדרטי לגמרי בחוגים באופן כללי, ואני מקפיד על הפדנטיות הזו רק כי עוד רגע יגיעו דברים לא לגמרי סטנדרטיים.

\( C\left(x\right)^{2}=\sum_{n=0}^{\infty}A_{n}x^{n} \)

כאשר

\( A_{n}=\sum_{k=0}^{n}C_{k}C_{n-k} \)

זה מה שנובע מהנוסחה למכפלת פולינומים. אבל בנוסף לכך אנחנו מכירים את נוסחת הנסיגה של קטלן, \( C_{n+1}=\sum_{k=0}^{n}C_{k}C_{n-k} \), ולכן משילוב של שתיהן אנחנו מקבלים ש-

\( A_{n}=C_{n+1} \)

כלומר

\( C\left(x\right)^{2}=\sum_{n=0}^{\infty}C_{n+1}x^{n} \)

הייתי רוצה להשתמש באותו טריק כמו פיבונאצ’י כדי להמיר את אגף ימין ל-\( C\left(x\right) \), אבל יש לי כאן בעיה. קודם, בפיבונאצ’י, הסכימה התחילה ממשהו גדול מ-0, והמקדם בפנים היה בעל אינדקס קטן מ-\( n \), ולכן היה קל לתקן את זה - הגדלנו את האינדקס, הקטנו את הערך ההתחלתי. כאן, לעומת זאת, הסכימה מתחילה מ-0, כלומר מהערך הנכון, והאינדקס הוא גדול מ-\( n \). אז נעשה משהו טיפה שונה: קודם כל נכפול את שני האגפים ב-\( x \) (פעולה מותרת בחוג), ונקבל

\( xC\left(x\right)^{2}=\sum_{n=0}^{\infty}C_{n+1}x^{n+1}=\sum_{n=1}^{\infty}C_{n}x^{n}=\sum_{n=0}^{\infty}C_{n}x^{n}-C_{0}=C\left(x\right)-1 \)

אחרי העברת אגפים נקבל

\( xC\left(x\right)^{2}-C\left(x\right)+1=0 \)

וזו… משוואה ריבועית? עכשיו אפשר לנפנף ממש מהר בידיים כמו שחלק מהספרים עושים: להגיד שנוסחת השורשים מלמדת אותנו ש-\( C\left(x\right)=\frac{1\pm\sqrt{1-4x}}{2x} \) ושהפתרון ה”נכון” מבין השניים הוא זה עם המינוס, כי אם נסתכל על \( \frac{1+\sqrt{1-4x}}{2x} \) נראה שכש-\( x \) שואף ל-0 המונה שואף ל-2 ולכן הביטוי שואף לאינסוף למרות שהוא אמור לשאוף ל-\( C_{0}=1 \) ולעומת זאת עבור \( \frac{1-\sqrt{1-4x}}{2x} \) קל לראות שזה עובד עם כלל לופיטל, וסיימנו! גילינו את הנוסחה לפונקציה היוצרת של מספרי קטלן, \( C\left(x\right)=\frac{1-\sqrt{1-4x}}{2x} \). זהו, אפשר לסגור את הפוסט.

אפשר לסגור את הפוסט, או שלא

אוקיי, בואו לא נסגור עדיין את הפוסט.

חשוב לי להדגיש שכל מה שראינו פה הוא נכון. זה למעשה מה שאוילר עשה במכתב הראשון שבו הוא סיפר לגולדבך על מספרי קטלן. אבל בבירור לא עשיתי את זה ברמת הפורמליות שבה התייחסתי לטורי חזקות פורמליים בכל יתר הפוסט, ומה שעוד יותר גרוע - פתאום ברגע האחרון עירבתי מושגים מאנליזה ודיברתי על להשאיף את \( x \) לאפס ועל כלל לופיטל… זה בלאגן שלם. לכן אני רוצה להקדיש את החלק הזה של הפוסט, שיהיה יותר מורכב מתמטית ממה שעשינו עד עכשיו, כדי להסביר למה הכל בסדר.

הרגע האחרון שבו הכל היה באמת בסדר פורמלית היה כשקיבלתי את המשוואה \( xC\left(x\right)^{2}-C\left(x\right)+1=0 \). הדבר הבא שעשיתי היה להזכיר את נוסחת השורשים. נוסחת השורשים היא הכלי הסטנדרטי שלנו לפתרון משוואה ריבועית, והיא נכונה בהרבה סיטואציות, לא רק במספרים הממשיים והמרוכבים. בואו נראה את זה: אני נמצא בחוג \( R \) כלשהו, עם איברים \( a,b,c\in R \), ואני מחפש ערך של \( x\in R \) שמקיים

\( ax^{2}+bx+c=0 \)

יש לי פוסט שמסביר מה עושים עכשיו, אבל אני אתן פה תיאור טיפה שונה. ראשית, נכפול את שני אגפי המשוואה ב-\( 4a \) ונקבל

\( 4a^{2}x^{2}+4abx+4ac=0 \)

זה עדיין מתקיים בכל חוג \( R \). עכשיו, נסתכל על הביטוי \( \Delta=b^{2}-4ac \) (“הדיסקרימיננטה”). גם הביטוי הזה - קיים בכל חוג \( R \). נחבר אותו לשני האגפים ונקבל

\( 4a^{2}x^{2}+4abx+b^{2}=\Delta \)

עכשיו אגף שמאל נראה בדיוק כמו משהו בריבוע: \( 4a^{2}x^{2}+4abx+b^{2}=\left(2ax+b\right)^{2} \). גם זה עדיין נכון בכל חוג. כלומר, קיבלנו

\( \left(2ax+b\right)^{2}=\Delta \)

עכשיו מגיע המעבר ה”בעייתי”:

\( 2ax+b=\pm\sqrt{\Delta} \)

המעבר הזה בעייתי לא רק בגלל שאנחנו בחוג כללי - אפילו אם היינו עובדים מעל הממשיים, \( \mathbb{R} \), הוא עדיין היה בעייתי אם \( \Delta \) היה שלילי. אז במקום לראות אותו כ”בעייתי” אפשר לחשוב על זה כאילו אנחנו מוסיפים הנחה: אנחנו אומרים - נניח שקיים \( \alpha\in R \) כך ש-\( \alpha^{2}=\Delta \), אז במקרה הזה אפשר לכתוב \( \left(2ax+b\right)^{2}=\alpha^{2} \). אבל האם עכשיו אפשר להסיק ש-\( 2ax+b=\pm\alpha \)? ובכן, לא.

בואו נראה דוגמא: החוג \( R=\mathbb{Z}_{8}=\left\{ 0,1,\ldots,7\right\} \) עם חיבור וכפל מודולו 8. בחוג הזה מתקיים ש-\( 1^{2}=3^{2}=5^{2}=7^{2}=1 \), ולכן אם \( x^{2}=y^{2} \) זה לא אומר ש-\( x=\pm y \) כי למשל מה אם \( y=1 \) ואילו \( x=3 \)?

אז אילו תנאים צריך לדרוש מהחוג שלנו כדי ש-\( x^{2}=y^{2} \) יגרור \( x=\pm y \)? בואו ננסה להוכיח את זה ונראה את התנאים צצים בדרך.

נתחיל עם \( x^{2}=y^{2} \). נעביר את \( y \) אגף (לא דורש כלום) ונקבל \( x^{2}-y^{2}=0 \), שאפשר לכתוב גם בתור \( \left(x-y\right)\left(x+y\right)=0 \). הופס, הוספנו דרישה! רואים מה היא? השתמשתי בדיסטריביוטיביות, אבל זה לא העניין כאן אלא זה שאם נפתח את הסוגריים, נקבל

\( \left(x-y\right)\left(x+y\right)=x^{2}-yx+xy-y^{2} \)

כלומר, אני הנחתי ש-\( xy=yx \) וזה קורה באופן כללי רק אם החוג קומוטטיבי. אבל אוקיי, \( R\left[\left[x\right]\right] \) שלנו הוא קומוטטיבי אם \( R \) עצמו הוא קומוטטיבי (ואצלנו \( R \) הוא הממשיים/המרוכבים). אז בינתיים זו דרישה קלילה יחסית (אבל שמראה יפה כמה חוגים לא קומוטטיביים - למשל חוגי מטריצות - הם עולמות משוגעים בפני עצמם).

עכשיו, קיבלתי \( \left(x-y\right)\left(x+y\right)=0 \), כלומר יש לי מכפלה של שני איברים ששווה אפס. האם בכלל ייתכן שמכפלה של שני איברים תיתן אפס למרות ששניהם שונים מאפס? זה לא משהו שיש באינטואיציה המתמטית היומימית שלנו כי זה לא קורה בשלמים והרחבותיהם, אבל זה כן קורה ב-\( \mathbb{Z}_{8} \) שהבאתי כאן בתור דוגמה, למשל \( 2\cdot4=0 \). לכן בתורת החוגים יש מונחים סטנדרטיים לסיפור הזה: אנחנו אומרים ש-\( a,b \) הם מחלקי אפס אם \( ab=0 \) למרות ש-\( a,b\ne0 \), וקוראים לחוג (קומוטטיבי בד”כ) בלי מחלקי אפס תחום שלמות. בתחומי שלמות, ש-\( \mathbb{Z} \) הוא מעין אבטיפוס שלהם, אפשר לבצע “צמצום”: אם \( ax=ay \) אז \( x=y \) זו הדוגמא הפשוטה, אבל גם \( x^{2}=y^{2} \) גורר \( x=\pm y \) הוא דוגמא לצמצום, ואנחנו מקבלים אותו כי אם יש לנו \( \left(x-y\right)\left(x+y\right)=0 \) בתחום שלמות, או ש-\( x-y=0 \) או ש-\( x+y=0 \), אין אפשרות אחרת.

למרבה השמחה, \( R\left[\left[x\right]\right] \) הוא תחום שלמות אם \( R \) הוא תחום שלמות, כי אם \( a\left(x\right)b\left(x\right)=0 \) אז בפרט \( a_{0}b_{0}=0 \) ואם אנחנו מעל תחום שלמות אז בלי הגבלת הכלליות, \( b_{0}=0 \). עכשיו, \( a_{0}b_{1}+a_{1}b_{0}=0 \), כלומר \( a_{0}b_{1}=0 \) ונקבל שגם \( b_{1}=0 \) וכן הלאה באינדוקציה.

אם כן, חזרה למשוואות ריבועיות: מה שראינו הוא שמעל תחום שלמות, אם קיים \( \alpha \) כך ש-\( \alpha^{2}=\Delta \) אז אפשר לומר \( 2ax+b=\pm\alpha \). עכשיו אפשר להעביר אגף ולקבל

\( 2ax=-b\pm\alpha \)

כדי להתקדם מכאן, אנחנו צריכים שאפשר יהיה לחלק ב-\( 2a \) וזה כמובן לא נכון בכל חוג, אפילו לא בתחום שלמות, זה הרי לא נכון אפילו ב-\( \mathbb{Z} \). אבל אם אפשר לחלק ב-\( 2a \) - כלומר, אם \( 2a \) הוא הפיך בחוג שלנו - אז נקבל

\( x=\frac{-b\pm\alpha}{2a} \)

וכדי לא לכתוב \( \alpha \) מעדיפים לכתוב

\( x=\frac{-b\pm\sqrt{b^{2}-4ac}}{2a} \)

מתוך הבנה ש-\( \sqrt{b^{2}-4ac} \) הוא סימון שאומר “איבר בחוג שכשמעלים אותו בריבוע מקבלים \( b^{2}-4ac \), בהנחה שקיים כזה”.

זה האופן שבו צריך לקרוא את המשוואה \( C\left(x\right)=\frac{1\pm\sqrt{1-4x}}{2x} \) שקיבלנו עבור מספרי קטלן. מה שהיא אומרת, ברמה הפורמלית ביותר, הוא “אם קיים טור חזקות פורמלי \( a\left(x\right) \) כך ש-\( a\left(x\right)^{2}=1-4x \), אז \( C\left(x\right) \) הוא או \( \frac{1+a\left(x\right)}{2x} \) או \( \frac{1-a\left(x\right)}{2x} \), אנחנו לא סגורים על איזה משניהם נכון”.

אבל רגע, לא סיימנו! צריך להצדיק גם את החלוקה ב-\( 2x \). להצדיק חלוקה ב-\( 2 \) זה קל, הרי \( 2 \) הוא הפיך. אבל לחלק ב-\( 2x \)? הרי לפני רגע אמרתי שטור חזקות הוא הפיך אם ורק אם האיבר החופשי שלו הוא הפיך, וב-\( 2x \), כשאני חושב עליו בתור טור חזקות, האיבר החופשי הוא 0, כלומר לא הפיך. אופס.

העניין הוא שכן אפשר סוג של “לחלק” ב-\( x \). לפעמים. הנה דוגמא לאיך זה עובד. נניח ש-\( a\left(x\right)=a_{1}x+a_{2}x^{2}+\ldots \), כלומר יש לנו טור חזקות שהמקדם החופשי שלו הוא 0. אז אפשר להוציא החוצה את \( x \) ולקבל \( a\left(x\right)=x\left(a_{1}+a_{2}x+\ldots\right) \) ואז אפשר לכתוב \( a_{1}+a_{2}x+\ldots=\frac{a\left(x\right)}{x} \). כלומר, את הפעולה “חלוקה ב-\( x \)” אפשר לראות בתור “הזזה שמאלה של כל האיברים בסדרה שמתחילה ב-0” - אם היה לנו את הסדרה \( \left(0,a_{1},a_{2},\ldots\right) \) אחרי ביצוע הפעולה הזו קיבלנו את הסדרה \( \left(a_{1},a_{2},\ldots\right) \).

עוד יותר פורמלית, מה שאנחנו רואים במשוואה \( C\left(x\right)=\frac{1\pm a\left(x\right)}{2x} \) הוא בעצם את \( 2xC\left(x\right)=1\pm a\left(x\right)^{2} \). אם נגלה שיש \( a\left(x\right) \) כך ש-\( 1-a\left(x\right)=x\cdot b\left(x\right) \) כלשהו, אז נוכל לכתוב \( 2xC\left(x\right)=xb\left(x\right) \) ואז נוכל לצמצם ב-\( x \), כי אנחנו בתחום שלמות, ולקבל \( 2C\left(x\right)=b\left(x\right) \), כלומר \( C\left(x\right)=\frac{b\left(x\right)}{2} \). זה התוכן הפורמלי של הכתיב \( C\left(x\right)=\frac{1-\sqrt{1-4x}}{2x} \).

העניין הזה גם מסביר לנו למה אנחנו בוחרים מינוס ולא פלוס, גם בלי שנזדקק ישירות להסברים אנליטיים: אם קיים \( a\left(x\right) \) כך ש-\( a\left(x\right)^{2}=1-4x \), אז המקדם החופשי שלו מקיים \( a_{0}^{2}=1 \) (כי \( 1 \) הוא המקדם החופשי של המכפלה, \( 1-4x \)) ובגלל שאנחנו בתחום שלמות, \( a_{0}=\pm1 \). כשמשתמשים בסימן \( \sqrt{\cdot} \) עבור מספרים ממשיים הכוונה היא תמיד ללקיחת השורש החיובי, אז גם כאן נוכל להשתמש במוסכמה שלוקחים את ה-\( a\left(x\right) \) עם המקדם החופשי \( a_{0}=1 \). עכשיו, אם אנחנו רוצים שהביטוי \( \frac{1\pm a\left(x\right)}{2x} \) יהיה מוגדר היטב, צריך שהמקדם החופשי של \( 1\pm a\left(x\right) \) יהיה 0, וזה יעבוד עבור חיסור ולא יעבוד עבור חיבור.

כמובן, עדיין נותרה לנו שאלה אחת: למה אנחנו יודעים ש-\( \sqrt{1-4x} \) קיים בכלל? אני יכול לכתוב \( a\left(x\right)^{2}=1-4x \) ולנסות לפתור את המשוואה ולחלץ את המקדמים של \( a\left(x\right) \), כמו שעשיתי עבור הופכי. אבל אני יכול גם לחפור יותר עמוק…

חופרים יותר עמוק

אני מניח שאנחנו מכירים את הבינום של ניוטון, ואם לא - יש לי על זה פוסט. זו הנוסחה החביבה

\( \left(a+b\right)^{n}=\sum_{k=0}^{n}{n \choose k}a^{k}b^{n-k} \)

שנכונה לכל \( n \) טבעי ו-\( a,b \) כלשהם, אפילו איברים בחוג קומוטטיבי כללי.

זו נוסחה שימושית ונהדרת עם הוכחה קומבינטורית מקסימה וכל זה מתואר בפוסט שלי. אני רוצה לדבר הפעם על ההכללה שלה: מה קורה אם אנחנו רוצים ש-\( n \) לא יהיה מספר טבעי דווקא, אלא מספר ממשי כללי? ובכן, ניוטון דאג גם לזה, ובאמצעות חדו”א אפשר להוכיח את הנוסחה

\( \left(a+b\right)^{r}=\sum_{k=0}^{\infty}{r \choose k}a^{k}b^{r-k} \)

כאשר \( r\in\mathbb{R} \) הוא מספר ממשי כללי, והסימון \( {r \choose k} \) מוגדר בתור

\( {r \choose k}=\frac{r\left(r-1\right)\left(r-2\right)\cdots\left(r-k+1\right)}{k!} \)

זו ממש הכללה ישירה של הבינום הרגיל של ניוטון, שבו \( {n \choose k}=\frac{n!}{k!\left(n-k!\right)}=\frac{n\left(n-1\right)\left(n-2\right)\cdots\left(n-k+1\right)}{k!} \). העניין הוא שאם \( n \) הוא מספר טבעי, ואם \( k>n \), אז נקבל \( {n \choose k}=0 \) כי במכפלה \( \left(n-1\right)\ldots\left(n-k+1\right) \) יופיע מתישהו \( \left(n-n\right) \), כלומר כל המכפלה הזו מוכפלת ב-0 ושווה ל-0 ולכן אנחנו מקבלים ש-\( \left(a+b\right)^{n} \) הוא לא סכום אינסופי אלא סופי (ליתר דיוק - הוא סכום אינסופי שכל אבריו הם 0 החל ממקום מסויים).

אם לעומת זאת \( r \) הוא לא מספר טבעי, אז \( \left(r-r\right) \) לא יופיע במכפלה ולכן היא אף פעם לא תתאפס. לכן צריך לעבור לסכום אינסופי ולקוות ממש חזק שהוא יתכנס.

בואו נראה דוגמא. נניח ש- \( a=-4x \) ו-\( b=1 \) ו-\( r=\frac{1}{2} \), אז נקבל

\( \sqrt{1-4x}=\left(-4x+1\right)^{\frac{1}{2}}=\sum_{k=0}^{\infty}{1/2 \choose k}\left(-4x\right)^{k}=\sum_{k=0}^{\infty}\left(-4\right)^{k}{1/2 \choose k}x^{k} \)

הנוסחה הזו מאפשר חישוב פשוט של המקדמים של \( x^{k} \) עבור הערכים הראשונים של \( k \) (אני מציע לכם לנסות לחשב בעצמכם, גם אני “מרגיש” את הביטוי רק כשאני עושה את זה):

• \( \left(-4\right)^{0}{1/2 \choose 0}=1\cdot1=1 \)
• \( \left(-4\right)^{1}{1/2 \choose 1}=-4\cdot\frac{1}{2}=-2 \)
• \( \left(-4\right)^{2}{1/2 \choose 2}=16\cdot\frac{1}{2}\cdot\frac{1}{2}\cdot\left(-\frac{1}{2}\right)=-2 \)
• \( \left(-4\right)^{3}{1/2 \choose 3}=-64\cdot\frac{1}{2\cdot3}\cdot\frac{1}{2}\cdot\left(-\frac{1}{2}\right)\cdot\left(-\frac{3}{2}\right)=-4 \)

מכאן כבר יש לי מספיק אומץ לנסות לכתוב את הביטוי הכללי:

\( \left(-4\right)^{n}{1/2 \choose n}=\left(-1\right)^{n}2^{n}\cdot2^{n}\cdot\frac{1}{2\cdot3\cdots n}\cdot\frac{1}{2}\cdot\left(-\frac{1}{2}\right)\cdot\left(-\frac{3}{2}\right)\cdots\left(-\frac{2n-3}{2}\right) \)

\( =2^{n}\cdot\frac{3\cdot5\cdots\left(2n-3\right)}{2\cdot3\cdots n}=\frac{6\cdot10\cdots\left(4n-6\right)}{2\cdot3\cdots n} \)

מה שנותן לנו, אם נציב ערכים קונקרטיים:

\( \sqrt{1-4x}=1-2x-2x^{2}-4x^{3}-10x^{4}-28x^{5}-84x^{6}-\ldots \)

זה כמובן מזכיר את סדרת מספרי קטלן, \( 1,1,2,5,14,42,\ldots \), ולא במקרה: הנוסחה שקיבלנו הייתה \( C\left(x\right)=\frac{1-\sqrt{1-4x}}{2x} \), כך שמספרי קטלן מתקבלים מ-\( \sqrt{1-4x} \) באופן הבא:

1. החליפו את ה-1 שבהתחלה ב-0, והסירו את סימני המינוס (זה החלק של \( 1- \) השורש)
2. הזיזו את הסדרה צעד אחד שמאלה כך שה-0 בהתחלה נעלם (זה החלק של החלוקה ב-\( x \))
3. חלקו את אברי כל הסדרה ב-2 (זו החלוקה ב-2).

במילים אחרות - כן! הבינום המוכלל של ניוטון עובד ונותן לנו את מספרי קטלן! ככה בדיוק אוילר גילה את הנוסחה הסגורה למספרי קטלן. לא על ידי תעלול קומבינטורי מרהיב כמו שהראיתי בפוסט הקודם, אלא על ידי “הא, מצאתי את הפונקציה היוצרת, עכשיו בוא ניקח את המתמטיקה הסטנדרטית שלנו ונפעיל אותה על הפונקציה כדי לקבל את סדרת המקדמים”.

זה השלב שבו כולם מרוצים… חוץ ממני. כל הקטע הזה של הבינום המוכלל של ניוטון? זו התעסקות בטורי חזקות של חדו”א, לא בטורי חזקות פורמליים. זה לא אומר שזה לא תקין - אפשר בהחלט לומר שזו תוצאה שתקפה רק בתחום ההתכנסות של הטור, אבל זה מספיק כדי לקבל את סדרת המקדמים - אבל אני רוצה לראות כמה רחוק אפשר ללכת כשדבקים רק בפורמליות, בלי חדו”א בכלל. עכשיו יש לנו מטרה הרבה יותר ברורה: אנחנו לא רוצים להבין “סתם” איך להתעסק במספרי קטלן פורמלית, אלא איך אפשר להוכיח את הבינום המוכלל של ניוטון פורמלית.

הבינום הפורמלי המוכלל של ניוטון

נשמור על העניין פשוט ונסתכל על הבינום של ניוטון כשאחד המחוברים הוא 1. כלומר, על הנוסחה

\( \left(1+x\right)^{r}=\sum_{n=0}^{\infty}{r \choose n}x^{n} \)

מה שיש לנו באגף ימין כאן הוא פונקציה יוצרת - הפונקציה היוצרת של הסדרה \( a_{n}={r \choose n} \). באגף שמאל יש לנו ביטוי שאין לו משמעות פורמלית - לא הגדרנו בשום שלב העלאה בחזקה כללית של פולינומים, או של טורי חזקות. אז אני יכול להגדיר את המשמעות של אגף שמאל להיות מה שכתוב באגף ימין; השאלה המעניינת היא האם ההגדרה הזו תסכים עם מה שאנחנו מצפים שיהיה, כלומר אם עבור \( r \) שהוא מספר טבעי ההגדרה תתלכד עם ההגדרה הרגילה, ואם יישמרו חוקי החשבון הרגילים של חזקות, שהם מה שעומד מאחורי הרחבת הגדרת החזקה מטבעיים למספרים ממשיים באופן כללי. כלומר, האם יתקיים

\( \left(1+x\right)^{r}\cdot\left(1+x\right)^{s}=\left(1+x\right)^{r+s} \)

ו-\( \left(\left(1+x\right)^{r}\right)^{s}=\left(1+x\right)^{rs} \)

אבל כבר כאן צצה בעיה: הביטוי \( \left(\left(1+x\right)^{r}\right)^{s} \) הוא לא מוגדר היטב, כי הרי \( \left(1+x\right)^{r} \) הוא כבר פונקציה יוצרת עם אינסוף מחוברים, ולא הגדרתי העלאה בחזקה שלה, רק של הביטוי הפשוט \( 1+x \). אז אני צריך מראש ללכת על הגדרה כללית יותר. מה בדבר…

\( \left(1+F\left(x\right)\right)^{r}=\sum_{n=0}^{\infty}{r \choose n}F\left(x\right)^{n} \)

כאשר \( F\left(x\right) \) היא פונקציה יוצרת כלשהי? ובכן, זה כמעט עובד, אבל בואו ננצל את ההזדמנות כדי להציג גם את הדבר הזה בהקשר טיפה יותר כללי: הרכבה של פונקציות יוצרות.

אז נניח שיש לנו שתי פונקציות יוצרות

\( a\left(x\right)=\sum_{n=0}^{\infty}a_{n}x^{n} \)

\( b\left(x\right)=\sum_{n=0}^{\infty}b_{n}x^{n} \)

ואנחנו רוצים להגדיר את ההרכבה, \( a\left(b\left(x\right)\right) \). אם הפונקציות היוצרות היו פונקציות אמיתיות ולא סתם חבלי כביסה, מה שהיה מתקיים (כשרדיוס ההתכנסות היה מתיר את זה) הוא

\( a\left(b\left(x\right)\right)=\sum_{n=0}^{\infty}a_{n}b\left(x\right)^{n}x^{n} \)

הדבר הזה הוא לא ביטוי מפורש. כלומר, זה לא שבהרכבה, המקדם של \( x^{n} \) יהיה \( a_{n}b\left(x\right)^{n} \). מה שקורה הוא שצריך לקחת את הטור האינסופי \( b\left(x\right) \), לכפול אותו בעצמו \( n \) פעמים (את זה אנחנו יודעים לעשות), לכפול את התוצאה במקדם המספרי \( a_{n} \) ואז להוסיף את זה לטור הכולל שאנחנו בונים. בצורה הזו לאותו \( x^{n} \) יכולות לתרום חזקות רבות ושונות מהצורה \( b\left(x\right)^{k} \). למעשה, קיימת הסכנה שלאותו \( x^{n} \) יהיו אינסוף חזקות שתורמות מחוברים. זה קורה אם ורק אם \( b_{n}\ne0 \). כי למשל, בואו נסתכל על המקרה הפשוט שבו \( b\left(x\right)=1+x \), אז מהן החזקות?

\( \left(1+x\right)^{0}=1 \)

\( \left(1+x\right)^{1}=1+x \)

\( \left(1+x\right)^{2}=1+2x+x^{2} \)

\( \left(1+x\right)^{3}=1+3x+3x^{2}+x^{3} \)

וכן הלאה - אנחנו רואים שכל חזקה החל מ-2 תתרום ל-\( x^{1} \), למשל. למה? כי מה זה בעצם \( \left(1+x\right)^{3} \)? זו המכפלה \( \left(1+x\right)\left(1+x\right)\left(1+x\right) \). בכל פעם אנחנו בוחרים אחד משני האיברים שבתוך זוג סוגריים ספציפי ומוסיפים אותו למכפלה שלנו. אם בכל פעם היינו חייבים לבחור איבר שהוא לפחות \( x \), אז כל זוג סוגריים שמשתתף במכפלה היה מגדיל ב-1 לפחות את החזקה של \( x \) בתוצאה הסופית. אבל אם 1 נמצא בסוגריים, אז אפשר לבחור אותו ולא להגדיל את החזקה של \( x \) בתוצאה הסופית. זה היה מבטיח שעבור חזקות מסוימות של \( x \), אפשר יהיה תמיד לייצר אותן החל ממקום מסוים - לכן המקדם שלהם יהיה אינסופי, וזה לא מוגדר היטב.

אפשר לחזור עכשיו אל ההעלאה בחזקה. במקרה הזה, יש לנו את הפונקציה היוצרת

\( a\left(x\right)=\left(1+x\right)^{r}=\sum_{n=0}^{\infty}{r \choose n}x^{n} \)

כלומר, \( a_{n}={r \choose n} \), אז אני יכול להציב בה את \( F\left(x\right) \) לכל \( F\left(x\right) \) שמקיים \( F_{0}=0 \). למשל, עבור \( \sqrt{1-4x} \) הצבתי את \( F\left(x\right)=-4x \), שבהחלט מקיימת את זה. ומה עם תכונות החזקה שאנחנו רוצים להוכיח?

\( \left(1+F\left(x\right)\right)^{r}\cdot\left(1+F\left(x\right)\right)^{s}=\left(1+F\left(x\right)\right)^{r+s} \)

ו-\( \left(\left(1+F\left(x\right)\right)^{r}\right)^{s}=\left(1+F\left(x\right)\right)^{rs} \)

כדי שזה יהיה מוגדר היטב, \( \left(1+F\left(x\right)\right)^{r} \) צריך להיות מהצורה \( 1+G\left(x\right) \) כך ש-\( G_{0}=0 \). את זה אפשר לראות ממש מההגדרה:

\( \left(1+F\left(x\right)\right)^{r}=\sum_{n=0}^{\infty}{r \choose n}F\left(x\right)^{n}=1+\sum_{n=1}^{\infty}{r \choose n}F\left(x\right)^{n} \)

ועכשיו נגדיר \( G\left(x\right)=\sum_{n=1}^{\infty}{r \choose n}F\left(x\right)^{n} \) ונשתמש בכך ש-\( F_{0}=0 \) בעצמו ולכן כל העלאה בחזקה של \( F\left(x\right) \) כוללת רק חזקות של \( x \) החל מ-\( x^{1} \).

עכשיו אפשר לעבור לעבודה הטכנית עצמה של להוכיח ש-\( \left(1+x\right)^{r}\cdot\left(1+x\right)^{s}=\left(1+x\right)^{r+s}=\sum_{n=0}^{\infty}{r+s \choose n}x^{n} \). יש לנו כאן כפל של שני טורי חזקות, ואנחנו יודעים בדיוק איך זה עובד. נגדיר

\( a\left(x\right)=\sum_{n=0}^{\infty}{r \choose n}x^{n} \)

\( b\left(x\right)=\sum_{n=0}^{\infty}{s \choose n}x^{n} \)

כלומר

\( a_{n}={r \choose n} \)

\( b_{n}={s \choose n} \)

וכעת

\( a\left(x\right)b\left(x\right)=\sum_{n=0}^{\infty}c_{n}x^{n} \)

כאשר

\( c_{n}=\sum_{k=0}^{n}a_{k}b_{n-k}=\sum_{k=0}^{n}{r \choose k}{s \choose n-k} \)

מה שאנחנו מצפים לקבל הוא

\( \sum_{k=0}^{n}{r \choose k}{s \choose n-k}={r+s \choose n} \)

אם יש לנו את זה - סיימנו את ההוכחה. למרבה המזל, זה שוויון מפורסם מאוד, שאפילו יש לו שם משלו: שוויון צ’ו-ונדרמונדה. עוד יותר למרבה המזל, זה שוויון שקל מאוד להוכיח קומבינטורית, כלומר יש לנו אחלה אינטואיציה למה הוא נכון… אבל רק אם \( s,r \) הם מספרים טבעיים. במקרה הזה, אפשר לחשוב על כך שיש לנו קבוצה של \( r \) חתולים ו-\( s \) כלבים ואנחנו רוצים להרכיב צוות מרגלים שכולל בדיוק \( n \) חברים - זו בעיה של בחירה בלי חשיבות לסדר ובלי חזרות, ומכיוון שקבוצת המרגלים הפוטנציאליים הכוללת היא מגודל \( r+s \) יש לנו בסך הכל \( {r+s \choose n} \) אפשרויות. אבל היה אפשר גם לסרבל את זה טיפה: אם היינו מחליטים לקחת לקבוצה שלנו בדיוק \( k \) חתולים, אז היו לנו \( {r \choose k} \) אפשרויות לבחור את החתולים, ואחר כך היינו צריכים לבחור עוד \( n-k \) כלבים, ולזה יש \( {s \choose n-k} \) אפשרויות, ולכן מעקרון הכפל יש לנו \( {r \choose k}{s \choose n-k} \) אפשרויות להרכיב צוות שכולל בדיוק \( k \) חתולים. את הסיפור הזה יכלנו לעשות לכל \( k \) בין 0 ל-\( n \), ועקרון החיבור אומר שמספר האפשרויות הכולל, אם כך, הוא \( \sum_{k=0}^{n}{r \choose k}{s \choose n-k} \). זה מסיים את ההוכחה הקומבינטורית.

השאלה היא מה עושים עכשיו, כשרוצים להוכיח את השוויון ל-\( r,s \) שהם מספרים ממשיים כלליים. לא ברור איך הגיון קומבינטורי יעזור לנו כאן, אבל למרבה המזל גם לא צריך אותו - אפשר להסתמך על מה שכבר הוכחנו. בשביל זה בואו נדבר לרגע על פולינומים.

נניח ש-\( p\left(x\right),q\left(x\right) \) הם שני פולינומים. אנחנו יודעים שפולינום ממעלה \( d \) נקבע בצורה יחידה על ידי הערכים שלו ב-\( d+1 \) נקודות, ולכן פולינום ממעלה \( d \) שמתאפס ב-\( d+1 \) נקודות הוא זהותית פולינום האפס. עכשיו, אם אנחנו יודעים ש-\( p\left(n\right)=q\left(n\right) \) לכל \( n\in\mathbb{N} \), אז אנחנו יודעים שהפולינום \( p-q \) מתאפס על אינסוף נקודות, ובפרט על מספר נקודות שגדול מהדרגה שלו, ולכן הוא זהותית אפס: \( p-q=0 \), כלומר \( p=q \) - פולינומים שמזדהים על אינסוף נקודות הם זהים.

עכשיו בואו נסבך את זה ונהפוך את הפולינומים לבעלי שני משתנים: \( p\left(x,y\right),q\left(x,y\right) \). כאן צריך להיזהר: אם למשל \( p\left(x,y\right)=x \) ו-\( q\left(x,y\right)=y \) אז נקבל ש-\( p\left(n,n\right)=q\left(n,n\right) \) עבור אינסוף ערכי \( n\in\mathbb{N} \) אבל זה כמובן לא אומר שהפולינומים הללו זהים. הטיעון צריך להיות קצת יותר עדין. באופן כללי, אם יש שתי קבוצות אינסופיות \( A,B \) כך ש-\( p\left(a,b\right)=0 \) לכל \( a\in A,b\in B \), אז \( p \) הוא פולינום האפס (כלומר, הפואנטה היא ש-\( p \) מתאפס על כל \( A\times B \), לא רק על איזו תת-קבוצה נחמדה של \( A\times B \)). בואו נוכיח את זה: באופן כללי, \( p\left(x,y\right)=\sum_{i,j}a_{ij}x^{i}y^{j} \). אפשר לסדר את הסכום הזה לפי חזקות של \( y \), כלומר לכתוב \( p\left(x,y\right)=\sum_{j}\left(\sum_{i}a_{ij}x^{i}\right)y^{j} \), ולסמן \( p_{j}\left(x\right)=\sum_{i}a_{ij}x^{i} \). עכשיו, אם כל ה-\( p_{j}\left(x\right) \) הללו הם פולינומי האפס, סיימנו; מקבלים ש-\( p\left(x,y\right)=\sum_{j}p_{j}\left(x\right)y^{j}=\sum_{j}0\cdot y=0 \). אז בואו נניח בשלילה שעבור \( j \) כלשהו, \( p_{j}\left(x\right) \) הוא לא פולינום האפס. בפרט, קיים ערך קונקרטי, \( a\in A \), כך ש-\( p_{j}\left(a\right)\ne0 \) - כי אם לכל \( a\in A \) היינו מקבלים \( p_{j}\left(x\right)=0 \) אז היינו מקבלים פולינום שמתאפס על אינסוף ערכים ולכן הוא זהותית 0. אם כן, \( p_{j}\left(a\right)\ne0 \) ולכן אם נסתכל על הפולינום \( q\left(y\right)=p\left(a,y\right) \) אנחנו רואים שמצד אחד, \( q\left(y\right)=\sum_{j}p_{j}\left(a\right)y^{j} \) הוא לא פולינום האפס כי לכל הפחות המקדם של \( y^{j} \) הוא לא אפס. מצד שני - אנחנו יודעים שלכל אינסוף הערכים \( b\in B \) מתקיים \( q\left(b\right)=p\left(a,b\right)=0 \) ולכן זה כן פולינום האפס - סתירה. לב העניין הוא בדיוק בשלב האחרון: שלכל \( b\in B \) מקבלים \( p\left(a,b\right)=0 \), באופן שלא תלוי בזהות של \( a \).

המסקנה מכל זה היא שאם יש לנו זוג פולינומים בשני משתנים \( p\left(x,y\right),q\left(x,y\right) \) כך שלכל זוג מספרים טבעיים \( r,s \) מתקיים \( p\left(r,s\right)=q\left(r,s\right) \) אז הפולינום הם זהים, לכל זוג ערכים, כולל ערכים ממשיים (או אפילו מרוכבים). עכשיו נסתכל על הביטוי

\( \sum_{k=0}^{n}{r \choose k}{s \choose n-k}={r+s \choose n} \)

לב העניין הוא שבאופן כללי, \( {x \choose n}=\frac{x\left(x-1\right)\left(x-2\right)\ldots\left(x-n+1\right)}{n!} \) הוא פולינום ב-\( x \): המונה הוא הרי מכפלה של \( n \) פולינומים ב-\( x \), אז גם הוא פולינום. לכן גם \( \sum_{k=0}^{n}{x \choose k}{y \choose n-k}={x+y \choose n} \) הוא שוויון של פולינומים - ושוויון שמתקיים לכל הצבה של \( r,s \) טבעיים ב-\( x,y \). זה מוכיח את השוויון לכל \( r,s \) ממשיים, ולכן מסיים את ההוכחה הפורמלית לכך ש-\( \left(1+x\right)^{r}\cdot\left(1+x\right)^{s}=\left(1+x\right)^{r+s} \), וכמסקנה אנחנו מקבלים ש-\( \left(1+F\left(x\right)\right)^{r}\cdot\left(1+F\left(x\right)\right)^{s}=\left(1+F\left(x\right)\right)^{r+s} \) לכל \( F\left(x\right) \) עם \( F_{0}=0 \).

זה מקדם אותנו בצורה משמעותית לתפיסה האינטואיטיבית של \( \left(1+x\right)^{r} \) בתור פעולת החזקה. כדי לראות את זה, בואו נוותר לרגע על שיטת הסימון שבה אנחנו משתמשים ובמקום זה נכתוב

\( \Phi\left(1+F\left(x\right),r\right)=\sum_{n=0}^{\infty}{r \choose n}F\left(x\right)^{n} \)

כלומר, בינתיים פשוט הגדרנו דרך לבנות פונקציה יוצרת חדשה מתוך \( F\left(x\right) \). מה לזה ולפעולת ההעלאה בחזקה? ובכן, ראשית נשים לב לכך שעל פי הגדרה

\( \Phi\left(1+F\left(x\right),1\right)=\sum_{n=0}^{\infty}{1 \choose n}F\left(x\right)^{n}=F\left(x\right)^{0}+F\left(x\right)^{1}=1+F\left(x\right)=\left(1+F\left(x\right)\right)^{1} \)

כלומר, \( \Phi\left(1+F\left(x\right),1\right) \) מתלכד עם מה שאנחנו מכירים בתור \( \left(1+F\left(x\right)\right)^{1} \). שימו לב שאת הביטוי \( \left(1+F\left(x\right)\right)^{1} \) אנחנו מכירים לא בתור “פונקציה יוצרת שהוגדרה מוזר” אלא זו חזקה במשמעות הרגילה שלה בחוגים - כפל של האיבר בעצמו שוב ושוב (פעם אחת, במקרה הזה).

טוב ויפה, אבל כזכור עבדנו קשה כדי להוכיח את התכונה

\( \Phi\left(1+F\left(x\right),r+s\right)=\Phi\left(1+F\left(x\right),r\right)\Phi\left(1+F\left(x\right),s\right) \)

ולכן עכשיו אפשר להראות באינדוקציה שלכל \( n \) טבעי,

\( \Phi\left(1+F\left(x\right),n+1\right)=\Phi\left(1+F\left(x\right),n\right)\Phi\left(1+F\left(x\right),1\right)= \)

\( =\left(1+F\left(x\right)\right)^{n}\left(1+F\left(x\right)\right)^{1}=\left(1+F\left(x\right)\right)^{n+1} \)

כאשר גם כאן - החזקה היא במשמעות המקורית והרגילה שלה בחוג, אז הפונקציה \( \Phi \) מתלכדת עם המשמעות הרגילה בחוג. כדי להשתכנע שהיא מרחיבה אותה בצורה נכונה, בואו נסתכל למשל על

\( \Phi\left(1+F\left(x\right),1\right)=\Phi\left(1+F\left(x\right),\frac{1}{2}+\frac{1}{2}\right)=\Phi\left(1+F\left(x\right),\frac{1}{2}\right)^{2} \)

במילים אחרות, \( G\left(x\right)=\Phi\left(1+F\left(x\right),\frac{1}{2}\right) \) הוא מצד אחד טור חזקות פורמלי מוגדר היטב, שלא נזקקנו לחשבון דיפרנציאלי כדי להגדיר; ומצד שני הוא מקיים \( G\left(x\right)^{2}=1+F\left(x\right) \) וכמו כן קל לראות ש-\( G_{0}=1 \) ולכן, בסימון שלנו בתחילת הפוסט, \( G\left(x\right)=\sqrt{1+F\left(x\right)} \), וזה תואם את המשמעות האינטואיטיבית שיש לנו למה העלאה בחזקת \( \frac{1}{2} \) אמורה להיות.

זה עובד גם עבור אפס ועבור מספרים שליליים. אפשר לבדוק ישירות על פי ההגדרה ש-

\( \Phi\left(1+F\left(x\right),0\right)=\sum_{n=0}^{\infty}{0 \choose n}F\left(x\right)^{n}=1 \)

מה שמתאים להעלאה “רגילה” בחזקת 0, ועכשיו עבור שליליים:

\( 1=\Phi\left(1+F\left(x\right),0\right)=\Phi\left(1+F\left(x\right),n-n\right)= \)

\( =\Phi\left(1+F\left(x\right),n\right)\Phi\left(1+F\left(x\right),-n\right) \)

כלומר קיבלנו ש-\( \Phi\left(1+F\left(x\right),-n\right)=\frac{1}{\Phi\left(1+F\left(x\right),n\right)} \). הצעד האחרון דורש כזכור שהאיבר החופשי של \( \Phi\left(1+F\left(x\right),n\right) \) לא יהיה 0, ואנחנו כבר יודעים שהוא 1, אז הכל בסדר.

זה נחמד כי זה מחזיר אותנו לתחילת הפוסט, שבו הוכחנו בדרך די ישירה ש-\( 1+x+x^{2}+\ldots=\frac{1}{1-x} \). עכשיו זה אמור לנבוע מההגדרה הכללית יותר שלנו. נסמן \( F\left(x\right)=x+x^{2}+\ldots \) ונקבל

\( \Phi\left(1+F\left(x\right),-1\right)=\sum_{n=0}^{\infty}{-1 \choose n}F\left(x\right)^{n}=\frac{1}{0!}F\left(x\right)^{0}+\frac{\left(-1\right)}{1!}F\left(x\right)^{1}+\frac{\left(-1\right)\left(-2\right)}{2!}F\left(x\right)^{2}+\ldots \)

באופן כללי, האיבר ה-\( n \)-י בסכום יהיה \( \frac{\left(-1\right)\left(-2\right)\cdots\left(-n\right)}{n!}=\frac{\left(-1\right)^{n}n!}{n!}=\left(-1\right)^{n} \), כלומר אנחנו מקבלים

\( 1-F\left(x\right)+F\left(x\right)^{2}-F\left(x\right)^{3}+\ldots \)

בכמה דרכים \( x^{n} \), עבור \( n\ge2 \), יכול להתקבל כאן? אם נסתכל על \( F\left(x\right)^{k} \), הוא כולל \( k \) זוגות סוגריים שמכל אחד מהם בוחרים חזקה של \( x \) כך שהחזקות מסתכמות אל \( n \) - זה כמו לספור כמה פתרונות יש למשוואה \( a_{1}+\ldots+a_{k}=n \). מה שכן, שימו לב שהסוגריים לא כוללים את \( x^{0} \) אז הפתרונות הם בטבעיים חיוביים. זו בעיה קלה, קומבינטורית: זה כמו לשאול כמה פתרונות בשלמים אי-שליליים יש ל-\( a_{1}+\ldots+a_{k}=n-k \) וזו בדיוק בחירה בלי חשיבות לסדר ועם חזרות של \( n-k \) פעמים מתוך \( k \) איברים - הפתרון הוא \( {\left(n-k\right)+k-1 \choose k-1}={n-1 \choose k-1} \). עכשיו, זה נתן לנו את המקדם של \( x^{n} \) באיבר \( F\left(x\right)^{k} \), אבל כדי לקבל את המקדם הכולל של \( x^{n} \) צריך לחבר את המקדמים שמקבלים לכל \( k \) וגם לקחת בחשבון את סימן המינוס שיש על איברים שבהם \( k \) אי זוגי. כלומר נקבל

\( \sum_{k=1}^{n}\left(-1\right)^{k}{n-1 \choose k-1} \)

במקרה הזה קל לטפל בעזרת הבינום של ניוטון. נשנה את משתנה הסכימה באותה דרך שבה עשינו את זה קודם עבור פיבונאצ’י:

\( \sum_{k=1}^{n}\left(-1\right)^{k}{n-1 \choose k-1}=-\sum_{k=0}^{n-1}\left(-1\right)^{k}{n-1 \choose k}=-\left(1-1\right)^{n-1}=0 \)

המקרים החריגים היחידים הם \( n=0,1 \). עבור \( n=0 \) בכלל אי אפשר להשתמש בנוסחה הזו, אבל אם חושבים רגע רואים שהיא אמורה לתת 0 כאן - וזה נכון, כי \( x^{0} \) בכלל לא מופיע ב-\( -F\left(x\right)+F\left(x\right)^{2}-F\left(x\right)^{3}+\ldots \), הוא מופיע רק ב-1 בהתחלה. כמו כן עבור \( n=1 \) יש לנו סיטואציה חריגה של \( 0^{0} \) וזו מהסיטואציות שבהן הדבר הנכון לעשות הוא להגדיר \( 0^{0}=1 \) (יש לי פוסט על זה), ובואו לא נשכח את המינוס הזה שהשתרבב החוצה, כלומר מקבלים \( -1 \) במקרה הזה, ולכן \( 1-F\left(x\right)+F\left(x\right)^{2}-F\left(x\right)^{3}+\ldots=1-x \) וזה - הפלא ופלא, זה בדיוק מה שציפינו לקבל, כי אנחנו כבר יודעים ש-\( 1+x+x^{2}+\ldots=\frac{1}{1-x} \) אז כמובן ש-\( \left(1+x+x^{2}+\ldots\right)^{-1}=1-x \).

אוקיי, אז אני מקווה שהשתכנענו שהצלחנו להגדיר את \( \left(1+F\left(x\right)\right)^{r} \) לכל \( r \) רציונלי. איך נגדיר אותו לכל ממשי? ובכן, כאן אנחנו בבעיה וחייבים לדבר על מושגים מחדו”א פשוט כי מספר ממשי הוא מושג מחדו”א. הייתה לי סדרת פוסטים על זה לא מזמן. בגדול, דרך נוחה לחשוב על מספרים ממשיים הם בתור אובייקטים שלכל אחד מהם, אנחנו יכולים לקחת סדרת רציונליים ששואפת אליו. זה מוביל להגדרה “הרגילה” של חזקה שהיא מספר ממשי כללי: בהינתן \( r \), לוקחים סדרה \( q_{n} \) של רציונליים כך ש-\( q_{n}\to r \), ואז מגדירים \( x^{r}=\lim_{n\to\infty}x^{q_{n}} \) וצריך לשבור את הראש כדי להוכיח שזה מוגדר היטב. אבל איך אפשר לעשות משהו דומה עם טורי חזקות פורמליים? אין לנו מושג של התכנסות על טורי חזקות, נכון? נכון…?

החפירה העמוקה ביותר (שנגיע אליה כאן)

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

בגדול, הרעיון הוא שאם יש לנו סדרה \( F^{1}\left(x\right),F^{2}\left(x\right),F^{3}\left(x\right),\ldots \) ואנחנו רוצים לדעת אם היא מתכנסת לאנשהו, נסתכל על המקדם של \( x^{n} \) עבור כל הסדרות הללו. אם החל ממקום מסוים המקדם הזה קבוע, ואם זה קורה לכל \( n \), אז לסדרה יש גבול שהוא הפונקציה היוצרת שבנויה מהמקדמים הללו. קצת יותר פורמלית: אם לכל \( n \) קיימים \( a_{n}\in\mathbb{R} \) ו-\( k_{n} \) כך שלכל \( i\ge k_{N} \) מתקיים ש-\( F_{n}^{i}=a_{n} \) (כאן \( F_{n}^{i} \) פירושו המקדם של \( x^{n} \) בטור החזקות \( F^{i}\left(x\right) \)) אז \( \lim_{i\to\infty}F^{i}\left(x\right)=F\left(x\right) \) כך ש-\( F\left(x\right)=\sum_{n=0}^{\infty}a_{n}x^{n} \).

אבל אפשר לעשות את זה עוד יותר מסודר. מי שמכירות את הבניה האנליטית של המספרים ה-\( p \)-אדיים (הצגתי אותה כאן) כנראה ירגישו בבית.

ראשית, לכל טור חזקות פורמלי \( F\left(x\right) \) ששונה מאפס, נגדיר \( \nu\left(F\left(x\right)\right)=\min_{F_{n}\ne0}n \), כלומר האינדקס של המקדם הראשון בטור ששונה מאפס. בנוסף נגדיר \( \nu\left(0\right)=\infty \) כדי שהכל יסתדר יפה. עכשיו אפשר להגדיר מטריקה על חוג טורי החזקות הפורמליים:

\( d\left(F,G\right)=2^{-\nu\left(F-G\right)} \)

במילים אחרות, ככל שהאינדקס הראשון שבו \( F,G \) נבדלים זה מזה הוא גבוה יותר, כך ה”מרחק” שלהם יהיה קטן יותר. אם הם נבדלים כבר באינדקס ה-0 המרחק שלהם יהיה 1, ואם הם נבדלים לראשונה באינדקס ה-3 אז המרחק שלהם יהיה \( \frac{1}{8} \) וכן הלאה.

מה שקורה כאן הוא שראשית כל, אם \( F=G \) אז \( F-G=0 \) ולכן \( d\left(F,G\right)=2^{-\nu\left(F-G\right)}=2^{-\nu\left(0\right)}=2^{-\infty}=0 \) (מי שמפריע לו השימוש הזה באינסוף - אוקיי, בסדר, פשוט נגדיר \( d\left(F,G\right)=0 \) כאשר \( F=G \) וחסל, מרוצים?).

שנית, \( d\left(F,G\right)=2^{-\nu\left(F-G\right)}=2^{-\nu\left(G-F\right)}=d\left(G,F\right) \); זה עובד כי המקדם הראשון ששונה מאפס ב-\( F-G \) הוא אותו מקדם כמו ב-\( G-F \), פשוט עם סימן הפוך.

לבסוף, אם \( F,G,H \) הם שלושה טורים, אז ראשית בואו נסמן ב-\( n \) את האינדקס הראשון שבו \( F,H \) נבדלים (אם הם זהים התוצאה שאגיע אליה עוד מעט נובעת עוד יותר בקלות), כלומר \( d\left(F,H\right)=2^{-n} \). בואו נסמן ב-\( m_{1} \) את האינדקס הראשון שבו \( F,G \) נבדלים וב-\( m_{2} \) את האינדקס הראשון שבו \( G,H \) נבדלים (ייתכן ש-\( m_{1},m_{2}=\infty \)). אני טוען ש-\( n\ge\min\left\{ m_{1},m_{2}\right\} \). למה? ובכן, אם \( G \) נבדל מ-\( F,H \) בשלב שבו הם עדיין זהים, זה אומר ש-\( m_{1}=m_{2} \) (כי הוא ייבדל משניהם בו זמנית שהרי הם זהים עדיין בשלב הזה) ומכיוון שזה לפני שהם נבדלים, האינדקס הזה בא לפני \( n \), כלומר במקרה הזה \( m_{1},m_{2}<n \).

עכשיו, באינדקס ה-\( n \) מתקיים \( F_{n}\ne H_{n} \) ולכן פשוט לא ייתכן ש-\( G_{n}=F_{n} \) וגם \( G_{n}=H_{n} \), כי שוויון כזה היה מכריח את \( F_{n}=H_{n} \). לכן זה השלב שבו בודאות \( G \) הולך להיבדל מ-\( F \) או מ-\( H \). אנחנו לא יודעים מי מהם, לכן אנחנו לוקחים את המינימום על \( \left\{ m_{1},m_{2}\right\} \).

מה המסקנה? \( n\ge\min\left\{ m_{1},m_{2}\right\} \) גורר ש-

\( d\left(F,H\right)=2^{-n}\le2^{-\min\left\{ m_{1},m_{2}\right\} }=\max\left\{ 2^{-m_{1}},2^{-m_{2}}\right\} =\max\left(d\left(F,G\right),d\left(G,H\right)\right) \)

זה נותן לנו את אי שוויון המשולש, בגרסה יותר חזקה מהרגיל אפילו: אם אני קטן מהמקסימום של שני מספרים אי שליליים, אני בוודאי קטן יותר מהסכום שלהם (שכולל את המקסימום ועוד איזה מספר)

אז קיבלנו פונקציה \( d \) כך ש-

• \( d\left(F,G\right)\ge0 \) ויש שוויון אם ורק אם \( F=G \)
• \( d\left(F,G\right)=d\left(G,F\right) \)
• \( d\left(F,H\right)\le d\left(F,G\right)+d\left(G,H\right) \)

שלוש התכונות הללו הופכות את \( d \) למה שנקרא מטריקה, שהיא פונקציה שמאפשרת לדבר באופן כללי על גבולות והתכנסות (למעשה, התכונה החזקה יותר של אי-שוויון המשולש נותנת משהו שנקרא אולטרמטריקה אבל נעזוב את זה). עכשיו אפשר לומר משהו כזה: \( \lim_{n\to\infty}F^{n}\left(x\right)=F\left(x\right) \) אם לכל \( \varepsilon>0 \) קיים \( N \) כך שאם \( n>N \) אז \( d\left(F^{n}\left(x\right),F\left(x\right)\right)<\varepsilon \). זו ההגדרה הסטנדרטית לגבול, ואם חושבים עליה קצת בהקשר של ה-\( d \) הספציפית שלנו רואים שהמשמעות של \( \lim_{n\to\infty}F^{n}\left(x\right)=F\left(x\right) \) היא בדיוק מה שהזכרתי קודם: כדי שהסדרה \( F^{n}\left(x\right) \) תתכנס לגבול, צריך שהמקדם של \( x^{k} \) יתקבע החל ממקום מסוים בסדרה, ואז הוא יהיה המקדם של אותו איבר ב-\( F\left(x\right) \).

עכשיו אפשר להסתכל על ביטוי כמו \( \sum_{n=0}^{\infty}F\left(x\right)^{n} \). כבר היינו בסיטואציה דומה קודם, וראינו שכדי שחזקה של \( F\left(x\right) \) תתנהג יפה, היה צריך שיתקיים \( F_{0}=0 \), אז נניח שזה קורה. עכשיו אפשר לחשוב על \( \sum_{n=0}^{\infty}F\left(x\right)^{n} \) פשוט כמו טור במובן הרגיל, כזה שמוגדר עם סכומים חלקיים \( \sum_{n=0}^{\infty}F\left(x\right)^{n}=\lim_{n\to\infty}S_{n} \) כאשר \( S_{n}=\sum_{k=0}^{n}F\left(x\right)^{k} \). בכל פעם שבה מוסיפים חזקה חדשה \( F\left(x\right)^{n} \) לסכום שיש לנו, היא משנה רק את המקדמים של \( x^{n} \) וחזקות גבוהות יותר - כלומר, החזקות הנמוכות יותר התקבעו ולכן הטור מתכנס.\textbackslash אפשר לעשות משהו אפילו עוד יותר משעשע כדי לחשב את הסכום שלו: הרי כדי לחשב את הסכום של \( \sum_{n=0}^{\infty}q^{n} \) במספרים ממשיים אנחנו מסתכלים על הסכום החלקי ה-\( n \)-י שיוצא \( \frac{q^{n+1}-1}{q-1} \), נוכל להסתכל על סכום דומה גם עבור \( F\left(x\right) \). הרי איך מוכיחים את הנוסחה לסכום החלקי? מסתכלים על המכפלה

\( \left(1+F\left(x\right)+\ldots+F\left(x\right)^{n}\right)\left(F\left(x\right)-1\right)=F\left(x\right)^{n+1}-1 \)

זו זהות שאפשר להוכיח בכל חוג קומוטטיבי. עכשיו, אם \( F_{0}=0 \) אז המקדם החופשי של \( F\left(x\right)-1 \) שונה מאפס ולכן הוא הפיך, ולכן אפשר לכפול בהופכי ולקבל

\( 1+F\left(x\right)+\ldots+F\left(x\right)^{n}=\frac{F\left(x\right)^{n+1}-1}{F\left(x\right)-1} \)

ועכשיו, מהו \( \lim_{n\to\infty}\frac{F\left(x\right)^{n+1}-1}{F\left(x\right)-1} \)? המכנה נשאר קבוע, ובמונה יש לנו חזקה הולכת וגדלה \( F\left(x\right)^{n+1} \). בחזקה הזו, המקדם של \( x^{n} \) וכל הקודמים לו הוא 0, ולכן… \( \lim_{n\to\infty}F\left(x\right)^{n+1}=0 \) ומכאן נקבל \( \lim_{n\to\infty}\frac{F\left(x\right)^{n+1}-1}{F\left(x\right)-1}=\frac{0-1}{F\left(x\right)-1}=\frac{1}{1-F\left(x\right)} \) והנה קיבלנו את התוצאה שממנה התחיל הפוסט - רק שעכשיו הוכחנו אותה באותה צורה בדיוק שבה מוכיחים את הסכום ה”קלאסי”. אותה טרמינולוגיה, אותו עולם מושגים של התכנסות, אותה טכניקה - ובלי לערב רדיוסי התכנסות בכלל. אין זכר למגבלה \( \left|q\right|<1 \), פשוט כי בחוג שלנו, עם המטריקה שלנו, העניינים הם למעשה פשוטים יותר.

עכשיו גם קצת יותר ברורה העניין הזה של להציב את \( F\left(x\right) \) בתוך \( G\left(x\right) \). אנחנו מקבלים בסוף טור מהצורה \( \sum_{n=0}^{\infty}a_{n}F^{n}\left(x\right) \), וזה מתכנס אם \( F_{0}=0 \). עכשיו אפשר לקחת את זה ולהשתמש בזה עבור טורים מוכרים. למשל, אם ניזכר איך נראה הפיתוח של פונקציית האקספוננט לטור חזקות: \( e^{x}=\sum_{n=0}^{\infty}\frac{1}{n!}x^{n} \), אז אפשר להגדיר \( e^{F\left(x\right)}=\sum_{n=0}^{\infty}\frac{1}{n!}F^{n}\left(x\right) \), ואפשר להגדיר \( \ln\left(1+F\left(x\right)\right)=\sum_{n=0}^{\infty}\frac{\left(-1\right)^{n+1}}{n}F^{n}\left(x\right) \) ועוד ועוד. אז ביטוי כמו \( \sqrt{1-4x} \) שמופיע בתוך פונקציה יוצרת? נראה לי שאנחנו כבר יודעים איך להסתדר איתו.