מספרי ברנולי

בואו נסכום סכומים

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

\( 1+2+3+\ldots+n=\frac{n\left(n+1\right)}{2} \)

סביב הסכום הזה יש את הצ’יזבט האהוב על המתמטיקאי קרל פרידריך גאוס, שלכאורה גילה אותו בתור ילד קטן שהמורה בבית הספר נתן לו וליתר התלמידים לסכום את המספרים מ-1 עד 100 כדי להעסיק אותם בזמן שהוא נח. גאוס הילד היה נאמן לסלוגן על כך שמתמטיקאים הם עצלנים: במקום לחבר את הכל במפורש, הוא שם לב לכך ש-1 ועוד 100 שווה 101, וגם 2 ועוד 99 שווה 101 וכן הלאה, כך שיש לו 50 זוגות מספרים שהסכום של כולם הוא 101 ורק צריך לחשב את הכפל הקל 50 כפול 101 ואת זה אפילו אני יודע לעשות בראש ולקבל 5050. הנוסחה שכתבתי למעלה היא אותו דבר: יש לנו \( \frac{n}{2} \) זוגות שהסכום של כולם הוא \( n+1 \), אז אנחנו פשוט כופלים (אם \( n \) אי זוגי יש איבר בודד באמצע שאי אפשר למצוא לו בן זוג, אבל הנוסחה עדיין עובדת כי היא סופרת אותו בתור “חצי זוג” - נסו בעצמכם לבדוק על מספרים קטנים!)

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

\( 1^{2}+2^{2}+3^{2}+4^{2}+\ldots+n^{2}=\frac{n\left(n+1\right)\left(2n+1\right)}{6} \)

הנוסחה הזו פחות פשוטה מהקודמת, אבל היא עדיין די פשוטה ומערבת רק מכפלה של שלושה מספרים. זה מעלה את השאלה אם גם כשאני מחבר חזקות גבוהות יותר של הטבעיים, אני עדיין אקבל נוסחה פשוטה יחסית. מה למשל קורה עם \( 1^{3}+2^{3}+3^{3}+\ldots \)? התשובה היא שאכן, יש נוסחה פשוטה יחסית למקרה הזה ובעצם לכל מקרה של \( 1^{m}+2^{m}+3^{m}+\ldots+n^{m} \), אם כי “פשוטה” זה כמובן עניין יחסי כי ככל ש-\( m \) גדול יותר הנוסחה תהיה מסובכת יותר. אבל מה שאפשר לומר שהופך את העניין לפשוט הוא שני דברים:

• הנוסחה היא תמיד פולינום ממעלה \( m+1 \).
• אפשר לכתוב את הנוסחה באופן כללי, לכל \( m \) שהוא, בעזרת משהו שנקרא מספרי ברנולי.

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

פולינומים הם באמת ובתמים פונקציות פשוטות מאוד. אם מציבים ערך בפולינום, החישוב רק דורש לחשב חזקות של הערך, לכפול אותן במקדמים, ולחבר. אם אני מצליח לתרגם את החיבור של המספרים \( 1^{10}+2^{10}+3^{10}+\ldots+1000^{10} \) לחישוב של הצבה של 1000 בפולינום ממעלה 11, המרתי את הבעיה של חישוב 1000 חזקות עשיריות של מספרים וחיבור של כולן, לבעיה של חישוב 11 חזקות שונות של אותו מספר (וכשהמספר הזה הוא 1,000 זה לא בדיוק החלק הקשה פה) ואז כפל של 11 החזקות הללו במקדמים וחיבור שלהן - משמעותית פחות עבודה. זה הוביל את יעקב ברנולי, שגילה את הנוסחה הכללית (ולא אכנס כאן לדיון ההיסטורי של מי בדיוק גילה מה ובאיזה נוסח למרות שיש דיון כזה) לכתוב בהתלהבות ביומן שלו שבעזרת הנוסחה לקחה לו פחות מרבע שעה כדי לחשב את סכום החזקות העשיריות של המספרים עד 1000 ולקבל שיצא \( 91,409,924,241,424,243,424,241,924,242,500 \). גם ברנולי היה נאמן לסלוגן “מתמטיקאים הם עצלנים”, בדרך המאוד מוזרה שבה העצלנות הזו מתבטאת בפועל.

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

ראשית, יש את הסימון המוסכם לסכימה. למשל, במקום לכתוב \( 1^{m}+2^{m}+3^{m}+\ldots+n^{m} \) אני כותב \( \sum_{k=1}^{n}k^{m} \). כאן הסימן \( \Sigma \) אומר שיש לי תיאור של סכום, ה-\( k^{m} \) שליד ה-\( \Sigma \) הוא “האיבר הכללי” של הסכום - כלומר, הצורה שיש לכל איבר בסכום. ה-\( k=1 \) למטה גם אומר שמשתנה הסכימה הוא \( k \), מה שאומר שבביטוי \( k^{m} \) אני מציב ערכים ב-\( k \) אבל משאיר את \( m \) כמות שהוא, וגם שהערך של \( k \) הזה מתחיל מ-1. ה-\( n \) למעלה אומר שהערך הגדול ביותר ש-\( k \) מגיע אליו הוא \( n \), והקונבנציה הלא כתובה היא שמגדילים בכל פעם את הערך של \( k \) ב-1. לכן \( \sum_{k=1}^{n}k^{m}=1^{m}+2^{m}+3^{m}+\ldots+n^{m} \). למרות שסימון הסכימה הזה נראה קצת מרתיע בהתחלה הוא הרבה יותר קומפקטי וברור אחרי שמתרגלים אליו.

שנית, אנחנו הולכים לראות מספרים מהצורה \( {a \choose b} \). הסימון הזה, שנקרא מקדם הבינום (אסביר בהמשך למה) מוגדר באופן הבא. ראשית, מגדירים עצרת של מספר טבעי, שמסומנת בתור המספר עם סימן קריאה אחריו: \( a!=1\cdot2\cdot3\cdots a \), כלומר מכפלת כל המספרים הטבעיים מ-1 עד \( a \) (למשל \( 4!=1\cdot2\cdot3\cdot4=24 \)) ובנוסף ההגדרה המפורשת \( 0!=1 \). שנית, \( {a \choose b}=\frac{a!}{b!\left(a-b!\right)} \) והביטוי הזה מוגדר כאשר \( 0\le b\le a \). יש הגיון מאחורי הביטוי הזה, לא סתם החלטנו להמציא אותו: \( {a \choose b} \) סופר את מספר הדרכים שבהן אפשר לבחור \( b \) איברים מתוך \( a \) איברים, במקרה שבו אין חשיבות לסדר שבו הבחירה הזו מתבצעת. (אני מתאר את זה כאן).

לבסוף, בנוסחה שאני הולך להציג יופיעו מספרי ברנולי שמסומנים ב-\( B_{0},B_{1},B_{2},\ldots \) והם יהיו המושג המרכזי בפוסט.

אני אגלה כבר עכשיו שמספרי ברנולי הראשונים הם \( B_{0}=1,B_{1}=-\frac{1}{2},B_{2}=\frac{1}{6},B_{3}=0 \) ואת ההגדרה הכללית שלהם אביא עוד מעט, אבל קודם אני רוצה להראות איך הם נותנים לנו את הנוסחה לסכום החזקות. אלא שכאן יש סיבוך קטן. אמרתי ש-\( B_{1}=-\frac{1}{2} \), אבל יש גם כאלו שמעדיפים להגדיר \( B_{1}=\frac{1}{2} \). שתי הקונבנציות סבירות, אבל אני בפוסט הזה הולך להשתמש בקונבנציה ש-\( B_{1}=-\frac{1}{2} \) וזה טיפה משפיע על הנוסחה: במקום להסתכל על \( \sum_{k=1}^{n}k^{m} \) אני מסתכל על \( \sum_{k=1}^{n-1}k^{m} \), כלומר על הסכום \( 1^{m}+2^{m}+\ldots+\left(n-1\right)^{m} \). את הסכום הזה אני אסמן ב-\( S_{m}\left(n\right) \). כמובן שזה לא שינוי גדול במיוחד; אם ניקח את הנוסחה \( \frac{n\left(n+1\right)}{2} \) שראינו קודם ונחליף את \( n \) ב-\( n-1 \) נקבל \( S_{1}\left(n\right)=\frac{n\left(n-1\right)}{2}=\frac{1}{2}n^{2}-\frac{1}{2}n \). באופן דומה אם ניקח את \( \frac{n\left(n+1\right)\left(2n+1\right)}{6} \) ונחליף את \( n \) ב-\( n-1 \) נקבל \( S_{2}\left(n\right)=\frac{n\left(n-1\right)\left(2n-1\right)}{6}=\frac{1}{3}n^{3}-\frac{1}{2}n^{2}+\frac{1}{6}n \).

עכשיו אפשר להציג את הנוסחה הכללית

• \( S_{m}\left(n\right)=\frac{1}{m+1}\sum_{k=0}^{m}{m+1 \choose k}B_{k}n^{m+1-k} \)

בואו נראה איך היא נותנת את הסכומים שכבר ראינו. ראשית, עבור \( 1+2+3+\ldots+n-1 \), זה הסכום \( \sum_{k=1}^{n-1}k^{1} \), כלומר \( m=1 \). לכן כשמשתמשים בנוסחה הכללית שראינו, מקבלים

\( S_{1}\left(n\right)=\frac{1}{2}\left[{2 \choose 0}B_{0}n^{2}+{2 \choose 1}B_{1}n^{1}\right]=\frac{1}{2}\left[n^{2}+2\cdot\left(-\frac{1}{2}\right)n\right]=\frac{1}{2}n^{2}-\frac{1}{2}n \)

ובאופן דומה:

\( S_{2}\left(n\right)=\frac{1}{3}\left[{3 \choose 0}B_{0}n^{3}+{3 \choose 1}B_{1}n^{2}+{3 \choose 2}B_{2}n\right]=\frac{1}{3}\left[n^{3}-\frac{3}{2}n^{2}+\frac{3}{6}n\right]=\frac{1}{3}n^{3}-\frac{1}{2}n^{2}+\frac{1}{6}n \)

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

ההגדרה היא רקורסיבית: אני מניח שכבר הגדרתי את כל המספרים \( B_{0},B_{1},B_{2},\ldots,B_{k-1} \) ומגדיר באמצעותם את \( B_{k} \), בצורה הבאה:

\( B_{k}=-\frac{1}{k+1}\sum_{i=0}^{k-1}{k+1 \choose i}B_{i} \)

עם מקרה הבסיס \( B_{0}=1 \). גם פה, הרבה יותר קל “להרגיש” את ההגדרה כשכותבים כמה מקרים ידנית:

\( B_{1}=-\frac{1}{2}{2 \choose 0}B_{0}=-\frac{1}{2} \)

\( B_{2}=-\frac{1}{3}\left[{3 \choose 0}B_{0}+{3 \choose 1}B_{1}\right]=-\frac{1}{3}\left[1-\frac{3}{2}\right]=-\frac{1}{3}\left(-\frac{1}{2}\right)=\frac{1}{6} \)

ואם ממשיכים בחישובים, מקבלים את הסדרה הבאה:

\( 1,-\frac{1}{2},\frac{1}{6},0,-\frac{1}{30},0,\frac{1}{42},0,-\frac{1}{30},0,\frac{5}{66},0,-\frac{691}{2730},\ldots \)

בדרך כלל ה-\( -\frac{691}{2730} \) הוא זה שבו מרימים ידיים בייאוש ושואלים “אתם צוחקים עלינו?!”. עד לשם, אפשר לראות ניצוצות של חוקיות סבירה - כל המספרים במקומות האי זוגיים למעט \( B_{1} \) הם 0; המספרים האחרים מחליפים סימן בין מינוס לפלוס; במכנה מופיעים מספרים סבירים יחסית כולל 42 יקיר המין האנושי; אבל אז מגיע \( -\frac{691}{2730} \) שכולל מונה ומכנה שאין לאף אחד שמץ של מושג מה הם רוצים מחיינו, והורס כל תקווה לאיזו נוסחה פשוטה יחסית, יותר מנוסחת הנסיגה שיש לנו (יש גם נוסחאות סגורות שכוללות סכימה ואני לא חושב שאפשר לומר שהן פשוטות יותר).

אוקיי, אז זה מה שעושים עם זה, בואו נוכיח שזה עובד.

בואו נביים בינומים

לפני שאני מגיע להוכחה האמיתית, שמשתמשת בכלי אלגנטי ויפה אבל לא טריוויאלי להבנה, הנה גישה קצת יותר בסיסית לנושא שכל אחד יכול להבין. בינתיים אני לא אנסה להוכיח את הנוסחה שראינו למעלה אלא משהו צנוע יותר - להוכיח ש-\( S_{m}\left(n\right) \) הוא פולינום ממעלה \( m+1 \) ולהראות איך למצוא אותו. בשביל זה אני קודם כל הולך להשתמש במשהו שנקרא הבינום של ניוטון (יש לי עליו פוסט) שאומר באופן כללי:

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

אם במקום \( b \) יש לי 1 זה נהיה משמעותית פשוט יותר:

\( \left(a+1\right)^{n}=\sum_{i=0}^{n}{n \choose i}a^{i}=1+{n \choose 1}a+{n \choose 2}a^{2}+\ldots+{n \choose n-1}a^{n-1}+a^{n} \)

עכשיו נשתמש בזה עבור \( a=k \) ו-\( n=m+1 \) ונקבל את הדבר הבא:

\( \left(k+1\right)^{m+1}-k^{m+1}=1+{m+1 \choose 1}k+{m+1 \choose 2}k^{2}+\ldots+{m+1 \choose m}k^{m} \)

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

\( \left[n^{m+1}-\left(n-1\right)^{m+1}\right]+\left[\left(n-1\right)^{m+1}-\left(n-2\right)^{m+1}\right]+\ldots+\left[2^{m+1}-1^{m+1}\right]+\left[1^{m+1}-0^{m+1}\right]=n^{m+1} \)

אז אם אנחנו מחברים את אגף שמאל של הביטוי

\( \left(k+1\right)^{m+1}-k^{m+1}=1+{m+1 \choose 1}k+{m+1 \choose 2}k^{2}+\ldots+{m+1 \choose m}k^{m} \)

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

\( n^{m+1}=n+{m+1 \choose 1}S_{1}\left(n\right)+{m+1 \choose 2}S_{2}\left(n\right)+\ldots+{m+1 \choose m}S_{m}\left(n\right) \)

וזו נוסחה די מרהיבה כי היא מקשרת את כל הנוסחאות לסכומים עד לחזקה ה-\( m \)-ית. אפשר לבודד את \( S_{m}\left(n\right) \) ולקבל

\( S_{m}\left(n\right)=\frac{1}{m+1}\left[n^{m+1}-{m+1 \choose m-1}S_{m-1}\left(n\right)-\ldots-{m+1 \choose 1}S_{1}\left(n\right)-n\right] \)

אם אנחנו כבר יודעים, אינדוקטיבית, שכל \( S_{k}\left(n\right) \) כזה הוא ממעלה לכל היותר \( k+1 \) המסקנה היא שהביטוי באגף ימין הוא פולינום ממעלה \( m+1 \) (בגלל ה-\( n^{m+1} \) שמופיע שם והעובדה שכל ה-\( S_{k}\left(n\right) \)-ים הם ממעלה קטנה יותר). הנוסחה הזו גם פותחת פתח לבניה רקורסיבית של ה-\( B_{m} \)-ים ויש ספרים שנוקטים בגישה הזו (למשל Concrete Mathematics של קנות’ ושות’) אבל זה טכני לא כיף. אני רוצה טכני כיף.

בואו טכני כיף

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

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

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

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

• \( \sum_{n=0}^{\infty}a_{n}x^{n}+\sum_{n=0}^{\infty}b_{n}x^{n}=\sum_{n=0}^{\infty}c_{n}x^{n} \) עם \( c_{n}=a_{n}+b_{n} \)
• \( \left(\sum_{n=0}^{\infty}a_{n}x^{n}\right)\left(\sum_{n=0}^{\infty}b_{n}x^{n}\right)=\sum_{n=0}^{\infty}c_{n}x^{n} \) עם \( c_{n}=\sum_{k=0}^{n}a_{n-k}b_{k} \)

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

דבר אחד שאין בפוסט וכן נשתמש בו כאן הוא פונקציות יוצרות אקספוננציאליות. הפונקציה היוצרת האקספוננציאלית של \( \left\{ a_{n}\right\} _{n=0}^{\infty} \) היא \( \sum_{n=0}^{\infty}a_{n}\frac{x^{n}}{n!} \). זה עדיין ביטוי פורמלי וההגדרות למעלה עדיין תקפות לגביו, אבל בואו נראה מה קורה לפעולות החיבור והכפל. עבור חיבור עדיין נקבל \( \sum_{n=0}^{\infty}a_{n}\frac{x^{n}}{n!}+\sum_{n=0}^{\infty}b_{n}\frac{x^{n}}{n!}=\sum_{n=0}^{\infty}c_{n}\frac{x^{n}}{n!} \) עם \( c_{n}=a_{n}+b_{n} \), כלומר פעולת החיבור של פונקציות יוצרות של שתי סדרות מניבה את הפונקציה היוצרת של סדרת הסכומים. כפל, לעומת זאת, הוא קצת יותר טריקי.

מה שאנחנו רוצים לעשות הוא, בהינתן הסדרות \( a_{n},b_{n} \), להבין מה הסדרה \( c_{n} \) שעבורה תתקיים המשוואה

\( \left(\sum_{n=0}^{\infty}a_{n}\frac{x^{n}}{n!}\right)\left(\sum_{n=0}^{\infty}b_{n}\frac{x^{n}}{n!}\right)=\sum_{n=0}^{\infty}c_{n}\frac{x^{n}}{n!} \)

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

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

אנחנו רוצים להוציא החוצה את ה-\( \frac{1}{2!} \) ולכן נקבל

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

מה קורה באופן כללי? המקדם של \( x^{n} \) יהיה \( \sum_{k=0}^{n}\frac{a_{k}}{k!}\frac{b_{n-k}}{\left(n-k\right)!} \). עכשיו, זכרו את הבינום של ניוטון: \( {n \choose k}=\frac{n!}{k!\left(n-k\right)!} \). לכן, אם נכפול ונחלק את הסכום ב-\( n! \), נקבל

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

כלומר, את נוסחת הכפל צריך לתקן באופן הבא:

• \( \left(\sum_{n=0}^{\infty}a_{n}\frac{x^{n}}{n!}\right)\left(\sum_{n=0}^{\infty}b_{n}\frac{x^{n}}{n!}\right)=\sum_{n=0}^{\infty}c_{n}\frac{x^{n}}{n!} \) עם \( c_{n}=\sum_{k=0}^{n}{n \choose k}a_{n-k}b_{k} \)

עכשיו אפשר לדבר על הפונקציה היוצרת האקספוננציאלית הבסיסית שלנו: זו שמתאימה לסדרה \( a_{n}=1 \), כלומר לטור \( \sum_{n=0}^{\infty}\frac{x^{n}}{n!} \). את הפונקציה הזו אני אסמן בסימון המקוצר המסתורי \( e^{x} \). כמובן, ייתכן שחלקכם מכירים את הסימון הזה והוא לא נראה להם מסתורי, אבל זה מסוכן מאוד לחשוב ככה כי למשל אם אני אכתוב עכשיו \( e^{2x} \) אתם תגידו “כמובן, זה הטור \( \sum_{n=0}^{\infty}2^{n}\frac{x^{n}}{n!} \)” וזה יהיה נכון בכל מה שנוגע לפונקציה שנקראת “אקספוננט” שאנחנו פוגשים בחדו”א, אבל כאן אנחנו בעולם קצת שונה, של טורי חזקות פורמליים, והביטוי \( e^{2x} \) הוא פשוט לא מוגדר. מה שמתבקש הוא להגדיר אותו בתור \( e^{x}\cdot e^{x} \), כי כפל כן הגדרנו, אבל צריך לוודא שזה עובד.

מכיוון ש-\( e^{x} \) התאים לסדרה \( a_{n}=1 \), אז \( e^{x}\cdot e^{x} \) מתאים לסדרה \( c_{n}=\sum_{k=0}^{n}{n \choose k} \). למרבה השמחה, אנחנו יודעים ש-\( \sum_{k=0}^{n}{n \choose k}=2^{n} \) (הוכחה קומבינטורית: \( {n \choose k} \) הוא מספר הדרכים לבחור \( k \) איברים מתוך \( n \), ואילו \( 2^{n} \) הוא מספר הדרכים לבחור תת-קבוצה כלשהי מתוך \( n \)) ולכן באמת מקבלים ש-\( e^{x}\cdot e^{x} \) מיוצג על ידי הטור \( \sum_{n=0}^{\infty}2^{n}\frac{x^{n}}{n!} \) מה ש”מצדיק” את הסימון \( e^{2x}=e^{x}\cdot e^{x} \). בגישה קצת פחות פורמלית הייתי אומר “מכיוון ש-\( e^{x} \) שלי הוגדרה עם אותו טור כמו אקספוננט אז כל תוצאה שיש לנו על אקספוננט עובדת כאן עם הבונוס שלא צריך להתחשב בשיקולי התכנסות” אבל אני לא אעשה את זה.

עכשיו, אם יש לנו את \( e^{2x} \), מה עם \( e^{kx} \) עבור \( k \) טבעי כללי? ההגדרה המתבקשת היא \( e^{kx}=\sum_{n=0}^{\infty}k^{n}\frac{x^{n}}{n!} \). הייתי רוצה להראות שזו באמת החזקה ה-\( k \)-ית של \( e^{x} \), ואת זה אני יכול להוכיח באינדוקציה. נניח שבאמת מתקיים \( e^{kx}=\sum_{n=0}^{\infty}k^{n}\frac{x^{n}}{n!} \) ונוכיח ש-\( e^{x}\cdot e^{kx}=\sum_{n=0}^{\infty}\left(k+1\right)^{n}\frac{x^{n}}{n!} \).

לצורך ההוכחה שוב נתבסס על הגדרת הכפל עבור האיבר הכללי - הפעם הוא יוצא \( c_{n}=\sum_{i=0}^{n}{n \choose i}k^{i} \). על \( {n \choose i}k^{i} \) אפשר לחשוב קומבינטורית בתור בחירה של \( i \) מתוך \( n \) איברים, ואז צביעה של כל איבר בצבע מתוך קבוצה בת \( k \) צבעים, כך שאפשר לבחור את אותו צבע יותר מפעם אחת. עכשיו, אם אני סופר את מספר הדרכים לבחור תת-קבוצה של \( n \) האיברים ולצבוע את אבריה ב-\( k \) צבעים, אפשר להתחכם טיפה - ל-\( k \) הצבעים נוסיף “צבע שקוף”, ואז פשוט נצבע את כל \( n \) האיברים ב-\( k+1 \) הצבעים, ומי שצבוע בצבע שקוף ייחשב כאילו לא לקחנו אותו לתת הקבוצה. כך קיבלנו שמספר הדרכים הכולל הוא \( \left(k+1\right)^{n} \), כלומר \( c_{n}=\left(k+1\right)^{n} \), כמו שרצינו להראות.

למה אני בכלל טורח כל כך להתעסק בחזקות של \( e^{x} \)? מן הסתם אני חותר למשהו. בואו נחזור אל המטרה שלנו - אנחנו רוצים למצוא נוסחה עבור \( S_{m}\left(n\right) \), לכל \( m \). קודם ראינו שאולי קשה להבין את \( S_{m}\left(n\right) \) עבור \( m \) בודד אבל אם מסתכלים על ה-\( S_{m} \)-ים הללו כמכלול, כולם ביחד, יש ביניהם קשרים. פונקציות יוצרות הן בדיוק דרך לנצל את הקשרים הללו, אז די מתבקש לקחת את \( S_{m} \) ולשתול אותם בתוך פונקציה יוצרת. עכשיו, בפונקציה יוצרת מה ששותלים הוא סדרות מספרים, אבל \( S_{m} \) היא לא סדרה של מספרים, היא סדרה של פונקציות - אז נבחר \( n \) קונקרטי, נקבל עבורו סדרה קונקרטית של מספרים, \( \left\{ S_{m}\left(n\right)\right\} _{m=0}^{\infty} \). נשתול אותה בתוך פונקציה יוצרת אקספוננציאלית ונראה מה נקבל:

\( \sum_{m=0}^{\infty}S_{m}\left(n\right)\frac{x^{m}}{m!}=\sum_{m=0}^{\infty}\left(\sum_{k=0}^{n-1}k^{m}\right)\frac{x^{m}}{m!} \)

עכשיו שימו לב מה קורה כאן: יש לנו פונקציה יוצרת אקספוננציאלית שהאיבר הכללי שלה הוא סכום סופי של איברים. זה מתאים לסיטואציה \( c_{n}=a_{n}+b_{n} \) שראינו קודם, רק לא עם שני איברים אלא עם \( n \) איברים, אבל באינדוקציה אפשר להראות שכל איבר כללי שהוא סכום של מספר סופי כלשהו של איברים מתפרק לסכום של פונקציות יוצרות, ולכן נקבל

\( \sum_{m=0}^{\infty}S_{m}\left(n\right)\frac{x^{m}}{m!}=\sum_{m=0}^{\infty}\left(\sum_{k=0}^{n-1}k^{m}\right)\frac{x^{m}}{m!}=\sum_{k=0}^{n-1}\left[\sum_{m=0}^{\infty}k^{m}\frac{x^{m}}{m!}\right] \)

הפלא ופלא, כל הפונקציות היוצרות שבסכום מתאימות בדיוק לחזקות של \( e \) שראינו קודם, אז קיבלנו את התוצאה

\( \sum_{m=0}^{\infty}S_{m}\left(n\right)\frac{x^{m}}{m!}=e^{0x}+e^{x}+e^{2x}+e^{3x}+\ldots+e^{\left(n-1\right)x} \)

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

עכשיו, בואו נכפול ונחלק את הביטוי הזה ב-\( x \) ונקבל \( \frac{e^{nx}-1}{e^{x}-1}=\frac{e^{nx}-1}{x}\frac{x}{e^{x}-1} \). אני עוד מעט אקדיש חלק שלם כדי להסביר למה \( \frac{x}{e^{x}-1}=\sum_{k=0}^{\infty}B_{k}\frac{x^{k}}{k!} \), כלומר \( \frac{x}{e^{x}-1} \) הוא הפונקציה היוצרת האקספוננציאלית של מספרי ברנולי. לגבי \( \frac{e^{nx}-1}{x} \), קל יותר לטפל בו: \( e^{nx}=1+nx+\frac{n^{2}x^{2}}{2}+\ldots \) ולכן \( \frac{e^{nx}-1}{x}=n+\frac{n^{2}x}{2}+\ldots=\sum_{k=0}^{\infty}\frac{n^{k+1}}{k+1}\cdot\frac{x^{k}}{k!} \)

נסכם לרגע בזהירות את מה שראינו:

\( \sum_{m=0}^{\infty}S_{m}\left(n\right)\frac{x^{m}}{m!}=\left(\sum_{k=0}^{\infty}\frac{n^{k+1}}{k+1}\frac{x^{k}}{k!}\right)\left(\sum_{k=0}^{\infty}B_{k}\frac{x^{k}}{k!}\right) \)

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

\( S_{m}\left(n\right)=\sum_{k=0}^{m}{m \choose k}B_{k}\frac{n^{\left(m-k\right)+1}}{\left(m-k\right)+1} \)

את הגורם שבפנים אפשר לפשט עם עוד תעלול אלגברי/קומבינטורי קטן:

\( {m \choose k}\frac{1}{m-k+1}=\frac{m!}{k!\left(m-k\right)!}\cdot\frac{1}{m-k+1}=\frac{m!}{k!\left(m-k+1\right)!}=\frac{1}{m+1}\frac{\left(m+1\right)!}{k!\left(m-k+1\right)!}=\frac{1}{m+1}{m+1 \choose k} \)

וקיבלנו את הנוסחה שמציגים בכל מקום:

\( S_{m}\left(n\right)=\frac{1}{m+1}\sum_{k=0}^{m}{m+1 \choose k}n^{m+1-k}B_{k} \)

וזה היה… ממש טכני? ובכן, כן ולא. אני יודע שזה די מרתיע אבל בסופו של דבר כשמבינים את הרעיון של פונקציות יוצרות כל מה שעשינו פה הוא מאוד סטנדרטי. זה לא אומר שהיה כיף גדול לעשות את זה, אבל בהתחשב בתוצאה הדי כללית שמקבלים פה זה ממש נחמד - בפרט שזו תוצאה שמטפלת בכל אינסוף ה-\( S_{m}\left(n\right) \)-ים בו זמנית.

אבל עדיין לא סיימתי כי נשאר לי להסביר מאיפה מספרי ברנולי הגיעו.

בואו למסע אל מקורות הברנולי

אני טענתי, ללא הוכחה, ש-\( \frac{x}{e^{x}-1}=\sum_{k=0}^{\infty}B_{k}\frac{x^{k}}{k!} \). כלומר אני מגדיר את מספרי ברנולי בתור הסדרה ש-\( \frac{x}{e^{x}-1} \) היא הפונקציה היוצרת האקספוננציאלית שלה. יש כאן שתי שאלות

• למה אני יודע בכלל ש-\( \frac{x}{e^{x}-1} \) ניתן לתיאור על ידי טור חזקות כזה?
• איך אני יודע שאלו מספרי ברנולי? כלומר, איך אני מראה שמתקיימת הנוסחה הרקורסיבית \( B_{n}=-\frac{1}{n+1}\sum_{k=0}^{n-1}{n+1 \choose k}B_{k} \) שהצגתי קודם?

נתחיל מהשאלה הראשונה, למה \( \frac{x}{e^{x}-1} \) ניתן לתיאור על ידי טור חזקות פורמלי. אם לא היינו עובדים במסגרת פורמלית אלא בחדו”א, הסיפור היה הולך ככה: היינו שמים לב שכשמציבים \( x=0 \) אז \( e^{x}=1 \) ולכן \( e^{x}-1=0 \) ולכן המכנה של \( \frac{x}{e^{x}-1} \) יכול להתאפס ומדובר בקטסטרופה. אבל מצד שני, גם המונה מתאפס כש-\( x=0 \) ולכן אפשר להשתמש בלהטוט החדו”אי שנקרא כלל לופיטל ולקבל \( \lim_{x\to0}\frac{x}{e^{x}-1}=\lim_{x\to0}\frac{1}{e^{x}}=1 \). כלומר, אפשר “לתקן” את הפונקציה \( \frac{x}{e^{x}-1} \) כך שב-\( x=0 \) היא תוגדר להיות 1 ולקבל פונקציה נחמדה שאפשר לפתח לטור והכל טוב ויפה.

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

אבל לא הכל אבוד, אני לא באמת צריך הופכיים פה. מה שאני רוצה להגיד בביטוי \( \frac{x}{e^{x}-1}=f\left(x\right) \) הוא שמתקיים השוויון \( x=f\left(x\right)\left(e^{x}-1\right) \). אז אני אבדוק אם אני מסוגל להגדיר את \( f\left(x\right) \) כדי שהשוויון הזה יתקיים; אם אני מסוגל, אז אפשר יהיה להשתמש בסימון המקוצר \( \frac{x}{e^{x}-1} \) כמו קודם.

בואו נתחיל מלכתוב את \( f\left(x\right) \) בתור טור חזקות אקספוננציאלי כללי: \( f\left(x\right)=\sum_{k=0}^{\infty}b_{k}\frac{x^{k}}{k!} \). כרגע אני לא יודע שה-\( b_{k} \)-ים הללו הם מספרי ברנולי, או אפילו שאני יכול לבחור להם ערכים בצורה כזו שתצדיק את השוויון \( \frac{x}{e^{x}-1}=f\left(x\right) \), אבל אני כן יכול לקחת טור חזקות אקספוננציאלי כללי כלשהו, לתת למקדמים שלו את הסימון \( b_{k} \), לכפול אותו ב-\( e^{x}-1 \) ולראות מה קורה. נוסחת הכפל הרגילה של טורי חזקות אקספוננציאליים תקפה גם כאן:

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

אצלנו \( a_{0}=0 \) ואילו \( a_{k}=1 \) לכל \( k>0 \) (כי החסרת 1 מ-\( e^{x} \) הורידה 1 מהאיבר במקום 0; אם למשל היינו רוצים להוריד 3 מהאיבר במקום 2 היינו צריכים לחסר \( 3x^{2} \)). בנוסחה \( c_{n}=\sum_{k=0}^{n}{n \choose k}a_{n-k}b_{k} \) אני מקבל את \( a_{0} \) כאשר \( k=n \) ולכן המקרה הזה אף פעם לא יופיע, ואני מקבל:

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

כלומר, עבור \( c_{0} \) אני מקבל סכום “ריק” ולכן \( c_{0}=0 \) תמיד, אין לי שליטה על זה (זו בדיוק הסיבה שבגללה \( e^{x}-1 \) לא הפיך). זו לא באמת בעיה, כי אנחנו רוצים לקבל את התוצאה \( x \), כלומר התוצאה שמתאימה למקרה שבו \( c_{1}=1 \) ואילו \( c_{n}=0 \) לכל \( n\ne1 \). אז מה באמת קורה עבור \( c_{1} \)?

\( c_{1}={1 \choose 0}b_{0}=b_{0} \)

זה מאלץ אותנו להגדיר \( b_{0}=1 \), אבל יופי - אם אנחנו מגדירים את \( b_{0}=1 \) אנחנו באמת מקבלים את הערך המבוקש של \( c_{1} \). מה עם היתר?

עבור \( c_{2} \) צריך להתקיים \( c_{2}=0 \), ואנחנו יודעים ש-

\( c_{2}={2 \choose 0}b_{0}+{2 \choose 1}b_{1} \)

כלומר:

\( 0=b_{0}+2b_{1} \)

כלומר:

\( b_{1}=-\frac{1}{2}b_{0}=-\frac{1}{2} \)

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

\( c_{n+1}=\sum_{k=0}^{n}{n+1 \choose k}b_{k} \)

נציב \( c_{n+1}=0 \) וכמו כן נפריד את \( b_{n} \) מכל היתר:

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

עכשיו, \( {n+1 \choose n}=n+1 \) ולכן אחרי העברת אגפים וחלוקה:

\( b_{n}=-\frac{1}{n+1}\sum_{k=0}^{n-1}{n+1 \choose k}b_{k} \)

וזו בדיוק, אבל בדיוק, הנוסחה עבור מספרי ברנולי:

\( B_{n}=-\frac{1}{n+1}\sum_{k=0}^{n-1}{n+1 \choose k}B_{k} \)

מה שמשיג את שתי המטרות שלנו: הראנו שבאמת קיימת פונקציה \( f\left(x\right) \) כך ש-\( f\left(x\right)\left(e^{x}-1\right)=x \) למרות ש-\( e^{x}-1 \) לא הפיכה, והראינו שהמקדמים של הפונקציה היוצרת האקספוננציאלית שלה הם מספרי ברנולי \( B_{k} \), ולכן אפשר לכתוב

\( \frac{x}{e^{x}-1}=\sum_{k=0}^{\infty}B_{k}\frac{x^{k}}{k!} \)

כפי שרצינו.

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

• הגעתי איכשהו אל הפונקציה היוצרת \( e^{0x}+\ldots+e^{\left(n-1\right)x} \)
• טענתי ש-\( e^{0x}+\ldots+e^{\left(n-1\right)x}=\frac{e^{nx}-1}{e^{x}-1} \)
• טענתי ש-\( \frac{e^{nx}-1}{e^{x}-1}=\frac{e^{nx}-1}{x}\frac{x}{e^{x}-1} \)

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

כבר ראיתי שיש פונקציה \( f\left(x\right)=\frac{x}{e^{x}-1} \), כלומר פורמלית זה טור חזקות שמקיים \( \left(e^{x}-1\right)f\left(x\right)=x \).

בנוסף, ראיתי שיש \( g\left(x\right)=\frac{e^{nx}-1}{x} \), כלומר פורמלית זה טור חזקות שמקיים \( xg\left(x\right)=e^{nx}-1 \).

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

עכשיו אני יכול לעשות שרשרת של הצבות:

\( \left(e^{x}-1\right)\left(e^{0x}+\ldots+e^{\left(n-1\right)x}\right)=e^{nx}-1=xg\left(x\right)=\left(e^{x}-1\right)f\left(x\right)g\left(x\right) \)

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

\( e^{0x}+\ldots+e^{\left(n-1\right)x}=f\left(x\right)g\left(x\right) \)

מה שמסיים את ההוכחה.

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