אלגוריתמים להוכחת זהויות קומבינטוריות

zeil_shirt

חולצה אגדית שמסכמת את הפוסט. דוגמן: דורון ציילברגר

הפוסט הזה מבוסס על הספר הנהדר "A=B" של Petkovšek, Wilf & Zeilberger משנת 1996 (ניתן להורידו בחינם ובאופן חוקי). הספר מתאר את ה-State of the Art של נושא אלגנטי ויחסית חדש במתמטיקה: אלגוריתמים שמוכיחים זהויות קומבינטוריות.
הספר סוקר את הנושא בצורה מעולה, אבל אורכו 208 עמודים והוא באנגלית. פוסט זה בא לתקצר את הספר בשפת הקודש תוך העברת הרעיונות המרכזיים. אני חורג מהספר בכמה נקודות: סדר הצגת האלגוריתמים שונה, דוגמאות שאינן הופיעו בספר הוספו, וחלק מההוכחות הפכו לתרגילים (כי אתם מסוגלים לזה!). בנוסף, אני מבהיר נקודות שלא בוהרו בספר המקורי.
השמטתי כמה נושאים מתקדמים (כמו q-זהויות ואלגוריתם Hyper) וגם את נושא השימוש במחשב – כל האלגוריתמים ממומשים בתוכנה Maple ובתוכנות נוספות והשימוש בהם קל מאוד.

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

  • קודם כל זה משמש מתמטיקאים שמתעסקים בקומבינטוריקה (ישירות או בעקיפין) כי הם נתקלים בזהויות כאלו כל הזמן (זה לאו דווקא עיקר המחקר שלהם, אבל זה צץ באופן טבעי). לרוב הן ממש לא פשוטות כמו אלו שרואים בקורסים שציינתי, ולא תמיד קל לבנות להם הוכחה קומבינטורית קלאסית. האלגוריתם הזה עושה את החיים קלים ואפשריים.
  • מעבר לזה, יש מתמטיקאים שחוקרים q-זהויות: זהויות שמשלבות קומבינטוריקה ושדות סופיים, לרוב אלו הכללות של זהויות קלאסיות ומוסיפים להן פרמטר q שמייצג גודל של שדה סופי, כאן יש דוגמא מפורסמת. בספר "A=B" מתוארים אלגוריתמים שיכולים להוכיח גם (חלק) מהזהויות הללו. התחום הזה פורה ויש עוד הרבה מה לחקור בו והוא משלב אלגברה וקומבינטוריקה בצורה יפה. לא ניכנס אליו כאן.
  • ובטוח יש עוד שימושים…

זה פוסט ארוך – יש בו 9 פרקים שממוספרים 0 עד 8.
עם זאת, כדי להבין את האלגוריתם הבסיסי והאינטואיטיבי ביותר, מספיק לקרוא את פרקים 3-4 ואולי בקריאה ראשונה זה הדבר הנכון.
פרקים 0 עד 2 מדברים על יכולות ומגבלות המחשב, ופרקים 5 עד 8 מדברים על אלגוריתמים ושימושים מתקדמים יותר.
לרוב, אני מעבירים את פרקים 0 עד 6 בהרצאה של שעתיים לבוגרי סמסטר ראשון במתמטיקה (הידע הנדרש הוא אלגברה לינארית וראש פתוח). פרקים 7 ו-8 דורשים עוד שעה.

קריאה מהנה. אשמח לקבל כל הערה/הארה/תיקון/שיפור בנושא למייל bambaman1 כרוכית gmail.com .

0. הקדמה

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

זהויות הן אובייקט נפוץ בכל ענף מתמטי כמעט. הנה כמה דוגמאות קלאסיות:

גיאומטריה: V-E+F=2 (נוסחת אוילר), A^{2}+B^{2}=C^{2} (משפט פיתגורס, שקול ל-\sin^2 (x) + \cos^2 (x) = 1 )

אלגברה: \prod_{p\text{ is a prime}}(1-p^{-s})^{-1}=\sum_{n\ge1}n^{-s} (מכפלת אוילר), \det(AB)=\det(A)\det(B) (כפליות הדטרמיננטה)

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

לפני שנפנה לכך, נדבר קצת על מה אי-אפשר לעשות עם מחשב (אם אתם רוצים להגיע לפואנטה – תדלגו על 2 הפרקים הבאים).

1. המחשב אינו כל יכול

אתם יושבים? אז… לא על כל שאלה במתמטיקה אפשר לענות.
למה אני מתכוון? בשנת 1900 פירסם הילברט 23 שאלות פתוחות ומהותיות בעיניו, וביניהן השאלה הבאה (שאלה מספר 10): מציאת אלגוריתם שמכריע האם למשוואה דיופנטית יש פיתרון? בויקיפדיה האנגלית מוצגת ההגדרה הבאה לאלגוריתם שהילברט ביקש:

A process according to which it can be determined by a finite number of operations whether the equation is solvable in rational integers

למי שלא מכיר – משוואה דיופטנטית היא משוואה מהצורה P(x_{1},\cdots,x_{n})=0 כאשר P פולינום עם מקדמים שלמים והמשתנים \{ x_i \}_{i=1}^{n} יכולים לקבל רק ערכים שלמים (לדוגמא: x^3+y^3-z^3). מטייסביץ' הראה ב-1970 שאין כזה אלגוריתם.

תרגיל 1: הראו שאם היה אלגוריתם שמכריע האם קיים פיתרון בשלמים, אפשר היה לבנות ממנו אלגוריתם שמכריע האם יש פיתרון במספרים טבעיים, ולהיפך.

עוד דוגמא שלילית, הפעם כזו שקשורה לזהויות: נסתכל על אוסף הפונקציות במשתנה x הנוצרות מארבע פעולות חשבון והרכבה מהפונקציות e^{x},\sin x,|x| והפונקציות הקבועות \{\ln2,\pi\}\cup\mathbb{Q} ריצ'רדסון הוכיח ב-1968 שאין אלגוריתם שמכריע האם 2 פונקציות כאלו מסכימות לכל x ממשי, מה ששקול לאלגוריתם שבודק האם פונקציה כזו מתאפסת תמיד. ויקיפדיה האנגלית מלאה בעוד הרבה דוגמאות של בעיות לא כריעות.

2. המחשב יכול לעשות דברים מסויימים

המחשב אומנם לא יכול לפתור משוואה דיופנטית כללית, אבל יש משפחות שלמות של משוואות שהוא כן יודע לפתור, לדוגמא משוואות Pell: משוואות בשני משתנים מהצורה x^2-Dy^2 = 1, כאשר D הוא פרמטר שלם.
בדומה, המחשב אינו יכול להוכיח כל זהות, אבל יש משפחות רחבות ומעניינות של זהויות שהוא כן יודע להוכיח. במקרים רבים הדבר נעשה באמצעות הצגת 2 האגפים ב"צורה קנונית": לרוב, כל איבר במשפחה הנידונה אפשר לרוב להציג בהרבה דרכים (אם עוסקים במספרים רציונליים אז \frac{1}{2}, \frac{2}{4} הן הצגות שונות של אותו מספר). אבל אם נדע להעביר כל איבר בהצגה כלשהי לאיבר בהצגה "נוחה" (באופן כזה שאותו איבר בהצגות שונות יעבור לאותה ההצגה ה"נוחה") שנקרא לו לשם העניין "נציג קנוני", ואם בנוסף יהיו לנו אלגוריתם שיודע לחשב את הנציג הזה ולהשוות נציגים, נוכל לוודא את הזהות A=B באופן הבא: 1) נבחר ל-A ול-B נציגים קנוניים, 2) נשווה ביניהם.

העיקרון מובן בצורה הכי ברורה דרך דוגמאות.

א. זהויות בין מספרים רציונליים: נניח שיש לנו 2 ביטויים שמורכבים מכפל, חלוקה וחיבור של מספרים שלמים. כדי לוודא שיוויון ביניהם, נעביר כל ביטוי כזה לצורה הקנונית הבאה: \frac{a}{b} כאשר a,b שלמים זרים ו-b חיובי.

האלגוריתם שמעביר מספר לצורה קנונית (ובפרט מוכיח את קיומה) מורכב משני שלבים – ראשית, משתמשים באלגוריתם 'המכנה המשותף' מימי התיכון, ולאחר מכן צריך לצמצם בגורם המשותף המקסימלי של המונה והמכנה (אותו מוצאים בעזרת אלגוריתם אוקלידס). 2 נציגים קנוניים שווים אמ"מ המונה והמכנה שווים. דוגמא: \frac{1}{101\cdot 33}+\frac{1}{101\cdot 11}=\frac{3}{50\cdot 50}+\frac{1}{33 \cdot 25 \cdot 100\cdot 101}. הנציג הקנוני של שני האגפים הוא \frac{4}{3333}.

ב. זהויות בין פולינומים: נניח שאנחנו רוצים להשוות פולינומים בשני משתנים, x,y. פולינומים אלו מהווים מרחב וקטורי, וצורה קנונית אפשרית היא הצגה בבסיס מסוים, לדוגמא: \{x^{i}y^{j}\}_{i,j}. עוד בסיס אפשרי – \{\binom{x}{i}\binom{y}{j}\}_{i,j}.

בשביל לעבור לצורה הקנונית הראשונה, צריך רק לפתוח סוגריים ולקבץ איברים. כך אפשר להוכיח זהויות נפלאות, ביניהן (2ab)^{2}+(a^{2}-b^{2})^{2}=(a^{2}+b^{2})^{2},(a+b)^{2}=a^{2}+2ab+b^{2}. הנה כמה זהויות יותר מעניינות ומתוחכמות, ב-4 משתנים:

  • (a^{2}+b^{2})(c^{2}+d^{2})=(ac-bd)^{2}+(ad+bc)^{2} – תוצאה של זהות זו היא שמכפלת סכום שני ריבועים היא גם כן סכום שני ריבועים (ישנה הכללה של אוילר לארבעה ריבועים ושל דגן לשמונה). אם כותבים אותה קצת אחרת, אפשר לקבל הוכחה לאי-שיוויון קושי-שוורץ במקרה של שני משתנים ממשיים: (a^{2}+b^{2})(c^{2}+d^{2})-(ac+bd)^{2}=(ac-bd)^{2} (נסו להוכיח את קושי-שוורץ הכללי כך!).
  • a^{4}+b^{4}+c^{4}+d^{4}-4abcd=(a^{2}-b^{2})^{2}+(c^{2}-d^{2})^{2}+2(ab-cd)^{2} – זהות שגוררת ישירות את אי-שיוויון הממוצעים עבור 4 משתנים (אפשרי להכליל סוג זה של הוכחה לכל כמות משתנים, ראו בפוסט הזה).

נציג עוד צורה קנונית, שונה מהותית במבט ראשון:

במקרה של פולינומים במשתנה יחיד x עם מעלה חסומה n, יש עוד צורה קנונית מעניינת (שנובעת מכך שדרך d נקודות עובר פולינום יחיד ממעלה קטנה מ-d): הצבת n+1 ערכים קבועים. לדוגמא: ההעתקה ששולחת את הפולינום p לוקטור ( p(0), p(1), \cdots, p(n) ) היא חח"ע וקלה לחישוב.
לפני שתתרעמו ותגידו שאמרנו שצורה קנונית של פולינום חייבת להיות פולינום ופתאום הבאתי וקטור, שימו לב לכך שאיברי הוקטור הם פשוט המקדמים שמתקבלים כשמציגים את הפולינום בבסיס "אינטרפולציית לגראנז'" המתאים: \{ \prod_{0\le j \le n,j \neq i} (\frac{x-j}{i-j}) \}_{i=0}^{n}. אז בעצם אנחנו מציגים את הפולינומים שלנו בבסיס מיוחד.

עובדה פשוטה שלא נוכיח כאן, היא שעבור פולינומים ב-m משתנים עם מעלה חסומה d, הצורה \left( p(a_1, \cdots, a_m) \right)_{ 0 \le a_i \le d} (וקטור באורך (d+1)^m) היא מזהה חח"ע של הפולינום ומהווה צורה קנונית. זה מוכח באמצעות גזירה דיסקרטית.
באופן כללי יותר, אם A_1, \cdots, A_m הן קבוצות ערכים מעוצמה גדולה מ-d, אז הצבת ערכי ה"תיבה" A_1 \cdot \times \cdots \times A_n בפולינום נותן צורה קנונית (נובע ישירות מ-משפט האפסים הקומבינטורי).

ג. זהויות טריגונומטריות: לדוגמא, \sin2x=2\cos x\sin x.
אם נשתמש בשיוויונות \sin x=\frac{e^{ix}-e^{-ix}}{2i},\cos x=\frac{e^{ix}+e^{-ix}}{2} (שקולים לנוסחת אוילר e^{ix} = \cos x + i \sin x, שניתנת להוכחה בין היתר ע"י השוואת טורי טיילור) אפשר להציג כל זהות טריגונומטרית כזהות של פונקציות רציונליות ב-t=e^{ix} (שימו לב ש-e^{-ix} = \frac{1}{t}). בין השאר, \cos(nx), \sin(nx) הם בעצם \frac{t^{n}+t^{-n}}{2},\frac{t^{n}-t^{-n}}{2i} בהתאמה.
את הבעיה שכעת יש לנו ביד – וידוא זהות בפונקציות רציונליות – אנחנו יודעים לפתור: באמצעות הכפלה במכנה המשותף, נקבל זהות של פולינומים, בעיה שכבר דנו בה.

שימו לב – אנחנו משתמשים כאן באופן לא מפורש בכך שפולינום שמתאפס על מעגל היחידה המרוכב (תמונת t) הוא בהכרח פולינום האפס – תרגיל לקורא.

טענה זו נותנת השראה לעוד דרך להוכיח זהויות טריגונומטריות – הצבת ערכים! נעביר זהות טריגונומטרית מהצורה f(\sin x,\cos x)=0 כאשר f פונקציה רציונלית ב-\sin x,\cos x לזהות פולינומיאלית g(t) = 0 עבור |t| = 1. בגלל שזה שקול לכך שהפולינום g הינו זהותית אפס, מספיק לוודא אותה עבור \deg g + 1 ערכים (g אמורה להיות זהותית אפס, לכן אנחנו מצפים שבפועל \deg g = 0. לכן כשנכתוב \deg g נתכוון בעצם לחסם עליון על \deg g ). כלומר מספיק לוודא את הזהות המקורית עבור \deg g + 1 זוויות (כמובן שהן צריכות להיות שונות מודולו 2\pi).
לדוגמא, כדי לוודא את \sin 2x=2\cos x\sin x מספיק להציב 7 ערכים, נגיד: 7 כפולות של \frac{\pi}{4}.

באופן כללי, עבור ביטוי טריגונומטרי ממעלה d לכל היותר, הצורה הבאה היא צורה קנונית:

(f(0),f(\frac{2\pi}{d+1}),f(2\cdot\frac{2\pi}{d+1}),\cdots,f(d\cdot\frac{2\pi}{d+1}))

ד. זהויות פיבונאצ'י: תהי \{F_{n}\}_{n\ge0} סדרת מספרי פיבונאצ'י,

F_{0}=0,F_{1}=1,F_{n+2}=F_{n+1}+F_{n}

מספרים אלו מקיימים זהויות מגוונות, כמו למשל F_{2n+1}=F_{n}^{2}+F_{n+1}^{2}. אם נגדיר \phi=\frac{1+\sqrt{5}}{2},\overline{\phi}=\frac{1-\sqrt{5}}{2} להיות שורשי המשוואה x^2 = x+1 אז נקבל מהתורה של סדרות נסיגה את הנוסחה המפורשת למספרי פיבונאצ'י: F_{n}=\frac{\phi^{n}-\overline{\phi}^{n}}{\phi-\overline{\phi}}.
אם מציבים s=\phi^{n},t=\overline{\phi}^{n} ומשתמשים בכך ש-F_{an+b}=\frac{\phi^{an+b}-\overline{\phi}^{an+b}}{\phi-\overline{\phi}}=\frac{\phi^{b}s^{a}-\overline{\phi}^{b}t^{b}}{\phi-\overline{\phi}} פולינום ב-s,t, מקבלים שכל זהות סבירה (כזו שמערכבת 4 פעולות חשבונות על ביטויים מהצורה F_{an+b}) נהיית שקולה ל-F(x,y)=0 כאשר F פולינום ו-(x,y) מקבלים את הערכים (\phi^{n},\overline{\phi}^{n}). בגלל ש-\phi\overline{\phi}=-1, זה גורר ש-F(x,x^{-1}) פולינום שמתאפס על \{\phi^{2n}\}_{n\ge1}, ולכן F(x,x^{-1}) זהותית אפס. בדומה, F(x,-x^{-1}) גם זהותית אפס.
לכן הוכחת זהויות פיבונאצ'י הופכת להיות שוב שקולה להוכחת (שתי) זהויות של פולינומים במשתנה אחד. בדומה למקרה הטריגונומטרי, בעצם מספיק לוודא את הזהות ל-\deg p_{1}+1 ערכים זוגיים ו-\deg p_{2}+1 ערכים אי-זוגיים, כאשר p_{1},p_{2} הפולינומים המתאימים. לדוגמא, כדי לוודא את F_{2n+1}=F_{n}^{2}+F_{n+1}^{2} מספיק להציב שבעה ערכים זוגיים ועוד שבעה אי-זוגיים.

תרגיל 2: חיקרו את האנלוגיה הבאה בין זהויות טריגונומטריות לזהויות פיבונאצ'י: נגדיר את סדרת לוקאס – L_{0}=2,L_{1}=1,L_{n+2}=L_{n+1}+L_{n}. הנוסחה המפורשת לה היא L_{n}=\phi^{n}+\overline{\phi}^{n}.
הזוג (L_{n},F_{n}) אנלוגי ל-(\cos x,\sin x). לדוגמא, הזהות L_{n}^{2}-5F_{n}^{2}=4(-1)^{n} דומה ל-\cos^{2}x+\sin^{2}x=1, ו-F_{2n}=L_{n}F_{n} דומה ל-\sin 2x=2\cos x\sin x.

3. זהויות בינומיות

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

\sum_{k=0}^{n}\binom{n}{k}=2^{n}
\sum_{k=0}^{n}k\binom{n}{k}=n2^{n-1}
\sum_{k=0}^{n}\binom{n}{k}^{2}=\binom{2n}{n}

דוגמאות פחות מוכרות:

\sum_{s=0}^{2m}(-1)^{s}\binom{2m}{s}^{2}=(-1)^{m}\binom{2m}{m,m}
\text{ Dixon's Identity: }\sum_{s=0}^{2m}(-1)^{s}\binom{2m}{s}^{3}=(-1)^{m}\binom{3m}{m,m,m}

(על שתי זהויות אלו דובר בהרחבה כאן.)

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

  • פונקציה F(n) תיקרא "היפר-גיאומטרית" אם המנה \frac{F(n+1)}{F(n)} היא פונקציה רציונלית ב-n. (אותה הגדרה תקפה לגבי סדרה  \{ f_n \}_{n}, ולפעמים נדבר על סדרות היפר-גיאומטריות כי זה יהיה נוח יותר.)
  • בדומה, פונקציה f(n,k) בשני משתנים תיקרא "היפר-גיאומטרית" אם שתי המנות \frac{f(n+1,k}{f(n,k)}, \frac{f(n,k+1)}{f(n,k)} הן פונקציות רציונליות ב-n,k. דוגמאות חשובות: כל ביטוי מהצורה (an+bk+c)! כאשר a,b,c טבעיים, וכמובן – מקדמים בינומיים: f(n,k) = \binom{n}{k}. נשים לב שפונקציות היפר-גיאומטריות סגורות לכפל וחילוק, אבל לא בהכרח לחיבור וחיסור.
  • "זהות היפר-גיאומטרית" היא זהות שבאגף אחד שלה יש סכום \sum_{k} f(n,k) כאשר f היפר-גיאומטרית ובאגף השני יש פונקציה F (בתקווה היפר-גיאומטרית אבל לאו דווקא). הסכימה היא בעיקרון על כל המספרים השלמים, אבל בכל המקרים שמעניינים אותנו ל-f יהיה תומך קומפקטי, ובשפת בני האדם: לכל n יהיה רק מספר סופי של k-ים עבורה היא לא מתאפסת.
    זו לא ההגדרה היחידה שאפשר לתת, אבל היא תספק אותנו בשימושינו הצנועים.

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

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

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

(1+x)^{n}=\sum_{k=0}^{n}x^{k}\binom{n}{k} \implies
n(1+x)^{n-1}=\sum_{k=1}^{n}kx^{k-1}\binom{n}{k}

כעת נציב x=1 ונקבל את הזהות השנייה שהצגנו, \sum_{k=0}^{n}k\binom{n}{k}=n2^{n-1}. \blacksquare

ב. הוכחה קומבינטורית ("סיפור"): הגורם הk-י בסכום \sum_{k=0}^{n}k\binom{n}{k} שווה למספר הדרכים לבחור תת-קבוצה בגודל k מתוך קבוצה בגודל n, ומתוך תת-קבוצה זו לבחור נציג.
אפשר לספור את הסכום הזה בצורה אחרת: לבחור בהתחלה את הנציג – יש לכך n אפשרויות – ואז לבחור את שאר איברי הקבוצה שלו – לכך יש 2^{n-1} אפשרויות, ומקבלים \sum_{k=0}^{n}k\binom{n}{k}=n2^{n-1}. \blacksquare

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

אנחנו נציג אלגוריתמים שיודעים:

  • למצוא רקורסיות לסכום היפר-גיאומטרי S(n)=\sum_{k} f(n,k). ברוב המקרים הרקורסיות הללו ניתנות לפיתרון בידיים, אבל יש אלגוריתם (שלא נציג) שמסוגל לפתור רקורסיות כאלו (מדובר ברקורסיות עם מקדמים שהם פונקציות רציונליות).
  • באמצעות אלגוריתם מציאת הרקורסיה הנ"ל, אפשר לבנות אלגוריתם שמוכיח זהויות היפר-גיאומטריות מהצורה F(n)=\sum_{k}f(n,k), כאשר F נתונה.
  • ליצור זהויות היפר-גיאומטריות חדשות מתוך זהויות קיימות.

הערה היסטורית

אנחנו נתעסק רק בסכומים סופיים, אבל יש תחום שלם (שלא ניגע בו), והוא טורים היפר-גיאומטריים. מדובר במשפחה של טורי חזקות שמופיעים באופן טבעי בחקר משוואות דיפרנציאליות ובאנליזה מרוכבת, ובמקרים מנוונים הם נותנים סכומים.
טורים אלו נחקרו מאות שנים ע"י מתמטיקאים כמו אוילר, גאוס ורימן, בלי קשר להקשרים הקומבינטוריים שבהם אנחנו לרוב פוגשים זהויות בינומיות. אנחנו לא ניגע בזווית הזו כמעט בכלל כי היא אנחנו מגיעים לנושא מכיוון שונה. ניתן דוגמא, כדי לסבר את האוזן.
טור היפר-גיאומטרי הוא טור \sum_{k \ge 0} t_k כאשר \{ t_k \}_{k \ge 0} סדרה היפר-גיאומטרית, כלומר \frac{t_{k+1}}{t_k} פונקציה רציונלית ב-k. זו הגדרה כללית, אז ננסה להבין איך נראים טורים אלו ולמעשה נביאם לצורה קנונית.
אם המונה ממעלה p והמכנה ממעלה q, אפשר לכתוב את המנה בתור \frac{\prod_{i=1}^{p} (k+a_i)}{\prod_{j=1}^{q} (k+b_j)} x (כאשר x מייצג את מנת המקדמים המובילים ו-a_i, b_j יכולים להיות מרוכבים). הקונבנציה היא להוסיף את k+1 למכנה (תמיד אפשר לעשות זאת ע"י הכפלת מונה ומכנה ב-k+1), וכך מקבלים את הייצוג הבא למנה:

\frac{t_{k+1}}{t_{k}} = \frac{ \prod_{i=1}^{p} (k+a_i) }{\prod_{j=1}^{q} (k+b_j)(k+1)} x

בנוסף, תמיד t_0 = 1. את הטור שמתאים ל-t_k הנ"ל מסמנים _{p}F_{q}[\begin{array}{ccc} a_{1} & \cdots & a_{p}\\ b_{1} & \cdots & b_{q} \end{array};x], ואם משתמשים בפונקציית העזר (a)_k = a(a+1)(a+2)\cdots (a+k-1) מקבלים את ההצגה הבאה לטור:

_{p}F_{q}[\begin{array}{ccc} a_{1} & \cdots & a_{p}\\ b_{1} & \cdots & b_{q} \end{array};x] = \sum_{k\ge0}\frac{(a_{1})_{k}\cdots(a_{p})_{k}}{(b_{1})_{k}\cdots(b_{q})_{k}}\frac{x^{k}}{k!}

וחושבים על טור זה כטור חזקות במשתנה מרוכב x (הגורם k! הופיע בזכות זה שדחפנו את k+1 למכנה). המקרים הנפוצים הם p=2,q=1.
כדי שהטור יתן סכום סופי, צריך שאחד מבין ה-a_i יהיה שלם שלילי. לדוגמא, אם a_1 = a_2 = -n, b_1 = n נקבל:

_{2}F_{1}[\begin{array}{cc} -n & ,-n\\ 1 \end{array};1]=\sum_{k\ge0}\frac{(-n)_{k}^{2}}{(1)_{k}}\frac{1^k}{k!}=\sum_{k=0}^{n}\frac{(n!/(n-k)!)^{2}}{k!^{2}}=\sum_{k=0}^{n}\binom{n}{k}^{2}

וזה סכום היפר-גיאומטרי נפוץ, שאנחנו יודעים שהוא שווה ל-\binom{2n}{n}. מסתבר שגאוס הוכיח זאת ועוד הרבה יותר:

_{2}F_{1}[\begin{array}{cc} a & ,b \\ c \end{array};1] = \frac{\Gamma(c) \Gamma(c-a-b)} {\Gamma(c-a) \Gamma(c-b)}

כאשר \Gamma היא פונקציית גמא, ובשביל התכנסות נדרש ש-\Re(c)>\Re(a+b). זה כולל את המקרה שלנו אבל גם עוד הרבה מקרים שברובם הטור לא מתנוון לכדי סכום.

4. האלגוריתם הראשון – הנזירה מארי סלין

כאמור, מעסיקים אותנו סכומים מהצורה S(n) = \sum_{k}f(n,k) כאשר f היפר-גיאומטרית.

האלגוריתם שנתאר מוצא רקורסיה ל-S(n). בהמשך נסביר איך באמצעות הרקורסיה אפשר להוכיח זהויות (כדאי להדגיש – זה לא החלק הקשה). אח"כ נתאר אלגוריתם מוצלח יותר (מבחינת סיבוכיות) למציאת הרקורסיה, אבל האלגוריתם שנתאר כעת הוא אינטואיטיבי וקל לזכירה.

האלגוריתם מופעל על דוגמא

האלגוריתם המדובר הומצא ע"י הנזירה סלין (Sister Mary Celine) ופורסם בשנת 1945 בעבודת הדוקטורט שלה. נפעיל אותו על הדוגמא הבאה:

S(n)=\sum_{k=0}^{n}k\binom{n}{k}

השלב הראשון והמרכזי באלגוריתם הוא מציאת רקורסיה למחובר f(n,k), רקורסיה שתלויה רק ב-n. במקרה שלנו f(n,k)=k\binom{n}{k}, ונניח שקיימת רקורסיה מהצורה הבאה:

a(n)f(n,k)+b(n)f(n+1,k)+c(n)f(n,k+1)+d(n)f(n+1,k+1)=0

כאשר a,b,c,d פונקציות רציונליות ב-n. נסביר איך מוצאים אותה (ובהמשך נגיד כמה מילים על למה היא קיימת).
ראשית, מחלקים ב-f(n,k). בגלל ש-f היפר-גיאומטרית, המקדמים של המשתנים יהיו פונקציות רציונליות, כי הם יהיו מנות מהצורה \frac{f(n+i, k+j)}{f(n,k)} (פה, ורק פה, משתמשים בכך ש-f היפר-גיאומטרית):

\frac{f(n+1,k)}{f(n,k)}=\frac{n+1}{n+1-k},\frac{f(n,k+1)}{f(n,k)}=\frac{n-k}{k},\frac{f(n+1,k+1)}{f(n,k)}=\frac{f(n+1,k+1)}{f(n+1,k)}\frac{f(n+1,k)}{f(n,k)}=\frac{n+1-k}{k}\frac{n+1}{n+1-k}=\frac{n+1}{k}

נכתוב את הרקורסיה שוב, אחרי שנכפיל במכנה המשותף k(n+1-k):

a(n)k(n+1-k)+b(n)(n+1)k+c(n)(n-k)(n+1-k)+d(n)(n+1)(n+1-k)=0

בגלל ש-a,b,c,d לא תלויים ב-k , אפשר לקבץ חזקות של k ולהשוות את המקדמים לאפס (פה אנחנו משתמשים בצורה קנונית לפולינום ב-k):

\begin{array}{lcl} (c(n)(n^2 +n) + d(n)(n+1)^2) k^0 +\\ (a(n)(n+1)+b(n)(n+1)+c(n)(-2n-1)+d(n)(-n-1))k^1+ \\ (c(n)-a(n))k^2 & = 0 \end{array}

מקבלים 3 משוואות, המיוצגות ע"י המטריצה הבאה:

\begin{pmatrix}  0 & 0 & n(n+1) & (n+1)^2 \\ n+1 & n+1 & -2n-1 & -n-1 \\ -1 & 0 & 1 & 0 \end{pmatrix} \begin{pmatrix} a \\ b \\ c \\ d \end{pmatrix} = \vec{0}

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

(a,b,c,d) = d(-1-\frac{1}{n},0,-1-\frac{1}{n},1)

נבחר את הפיתרון a(n)=-1-\frac{1}{n},b(n)=0,c(n)=-1-\frac{1}{n},d(n)=1, כלומר מתקיימת הרקורסיה הבאה:

-(1+\frac{1}{n})f(n,k)-(1+\frac{1}{n})f(n,k+1)+f(n+1,k+1)=0

בגלל שהמקדמים לא תלויים ב-k, אפשר לסכום את שני האגפים על פני כל ערכי k. כשנסכום, נעשה זאת על כל המספרים השלמים עם הקונבנציה ש-f(n,k) מתאפס כאשר כאשר k שלילי או k>n (זו יותר מקונבנציה – היא נובעת מהשיוויונות הבסיסיים kf(n,k+1) = (n-k)f(n,k), (n+1-k)f(n+1,k)=(n+1)f(n,k)). נקבל:

-(1+\frac{1}{n})S(n)-(1+\frac{1}{n})S(n)+S(n+1)=0

כלומר קיבלנו רקורסיה מעומק 1: S(n+1)=2\frac{n+1}{n}S(n). חישוב שלוקח זמן סופי (קרי, O(1)) מראה ש-S(1) = 1, ושימוש ברקורסיה נותן S(n)=2^{n-1}\frac{n!}{(n-1)!}S(1)=n2^{n-1}. וזה הכל. \blacksquare

המקרה הכללי

אז מה עושים באופן כללי? מנחשים שיש רקורסיה מעומק (d,d), כלומר:

\sum_{i,j=0}^{d} a_{i,j}(n) f(n+i,k+j) = 0

מחלקים את 2 האגפים ב-f(n,k) ומקבלים משוואות לינאריות במשתנים a_{i,j} ומקדמים שהם פונקציות רציונליות בשני משתנים. כופלים במכנה משותף ומקבצים לפי חזקות k, ומקבלים משוואות שהמקדמים שלהן הם פולינומים ב-n. אם יש יותר משתנים ממשוואות – מוצאים פיתרון, סוכמים את הרקורסיה על פני k ומוצאים רקורסיה ל-S. אם אין פיתרון- מגדילים את d (נגיד, פי 2) וחוזרים על התהליך. בהמשך נציג ללא הוכחה חסם מוכח על d.

מה שקרה לנו בדוגמא זו סיטואציה שכיחה – הרבה פעמים הרקורסיה תהיה מהצורה a_{0}(n)S(n+1)+a_{1}(n)S(n)=0 ולכן S(n)=S(0)\prod_{j=0}^{n-1}(-a_{0}(j)/a_{1}(j)). במקרה זה מקבלים יצוג מפורש ל-S כפונקציה היפר-גיאומטרית.
סיטואציה נוספת היא שמקבלים רקורסיה עם מקדמים קבועים שאפשר לפתור בדרכים סטנדרטיות לאחר מציאת שורשי הפולינום האופייני המתאים.

דוגמאות נוספות

  • L_{n}(x)=\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}\frac{x^{k}}{k!} – סדרת פולינומי Laguerre מקיימת את הרקורסיה nL_{n}(x)+(x+1-2n)L_{n-1}(x)+(n-1)L_{n-2}(x)=0, אותה אפשר למצוא עם אלגוריתם סלין – הפרמטר x לא מפריע בשום שלב.
  • זהות Reed-Dawson: נגדיר את הסכום S(n)=\sum_{k}\binom{n}{k}\binom{2k}{k}(-2)^{n-k}. מנחשים שיש רקורסיה מעומק 2 ופותרים אותה. מקבלים 7 מחוברים (לא 8 כי המקדם של f(n,k) מתאפס), סוכמים על k  ומקבלים (n+2)F(n+2)-4(n+1)F(n)=0, וחישוב קצר מראה ש:

F(n)=\begin{cases}  0 & 2\nmid n\\  \binom{n}{n/2} & 2|n  \end{cases}

המשפט הפורמלי

המשפט הכללי, שלא נוכיח, הולך כך: נניח ש-f(n,k) היא מהצורה הבאה:

f(n,k) = p(n,k)\frac{\prod_{i=1}^{u}(a_{i}n+b_{i}k+c_{i})!}{\prod_{i=1}^{v}(u_{i}n+v_{i}k+w_{i})!}x^{k}

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

אם הפונקציה כן מהצורה הרצויה, אז אם נבחר רקורסיה בעומק J=\sum|b_{j}|+|v_{j}|,I=1+\deg p+J(\sum|a_{j}|+|u_{j}|-1), כלומר ננסה לפתור את:

\sum_{0\le i\le I,0\le j\le J}f(n+i,k+j)a_{i,j}(n)=0

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

איך מוכיחים עם האלגוריתם זהויות?

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

  • למצוא רקורסיה לסכום היפר-גיאומטרי S(n) = \sum f(n,k)
  • להוכיח זהות מהצורה F(n) = \sum f(n,k) ב-3 שלבים: קודם, נמצא רקורסיה לאגף ימין בעזרת האלגוריתם שתיארנו – נסמן ב-d את העומק שלה. אח"כ נוודא שגם F מקיימת את הרקורסיה. לרוב, גם F היפר-גיאומטרית ואז זה מתנוון לשיוויון בפונקציות רציונליות, כי \sum_{i=0}^{d} a_{i}F(n+i)=0 שקול ל-\sum_{i=0}^{d} a_{i}\frac{F(n+i)}{F(n)}=0. שלב שלישי ואחרון הוא לוודא ששני האגפים מסכימים עבור i=1,2,\cdots, d. זה חישוב שלוקח זמן סופי.
  • יש אלגוריתם, שלא נתאר, שמאפשר לפתור רקורסיה כללית עם מקדמים פולינומיאלים בהנחה שהפיתרון הוא סכום של פונקציות היפר-גיאומטריות, והוא למעשה מאפשר למצוא ביטוי סגור לסכום היפר-גיאומטרי בלי שמישהו יגלה לכם אותו מראש! לא תמיד צריך אותו, לא חסרים מקרים שאפשר לפתור את הרקורסיה בידיים.

עם זאת, יש אלגוריתמים יעילים יותר ומגניבים יותר, עליהם נדבר בהמשך.

5. תופעת WZ

מבוא

תופעת WZ היא התופעה הנפלאה הבאה: אם מנרמלים את הזהות שלנו (המושג "נרמול יובהר בהמשך), לרוב (במובן אמפירי ולא מתמטי…) תהיה לה הוכחה מאוד קצרה בדמותה של פונקציה היפר-גיאומטרית דואלית.
ובצורה הרבה יותר ברורה, הסיפור הוא כזה: נניח שיש לנו זהות F(n)=\sum_{k}f(n,k) כאשר f ו-F היפר-גיאומטריות. אם F(n) לא מתאפסת בכלל (מצב שכיח), זהות זו שקולה לזהות \sum_{k}f(n,k)/F(n)=1. מכאן מקבלים שלאחר שינוי שמות, שהזהות שקולה לזהות מהצורה \sum_{k}f(n,k)=\text{const}, וזו הכוונה ב"נרמול" – להחליף את f ב-\frac{f}{F}. נשים לב שהמנה \frac{f}{F} נשארה היפר-גיאומטרית – זו נקודה מהותית, בגלל שהמונה היפר-גיאומטרי (בשני משתנים) והמכנה היפר-גיאומטרי (במשתנה יחיד).
הערה: אם מתקיים F \equiv 0 אז הזהות במצבה המקורי כבר מנורמלת וזה גם סבבה.

תופעת WZ היא העובדה היפה והמפתיעה שבהרבה (המון!) מקרים, קיימת g(n,k) היפר-גיאומטרית כך ש:

(*)f(n+1,k)-f(n,k) = g(n,k+1)-g(n,k)

למה זה שימושי בטירוף? כי סכימה על k \in \mathbb{Z}, תחת ההנחה \lim_{|k|\to\infty}g(n,k)=0 (הנחה סבירה מאוד ולרוב יתקיים יותר מכך – g(n,k) תתאפס, בהינתן n קבוע, עבור k גדול מספיק) נותנת את השיוויון S(n+1)-S(n) = 0. שיוויון זה מראה שהסכום S(n)=\sum_{k}f(n,k) לא תלוי ב-n! לכן מספיק לוודא את הזהות עבור n=1 או כל ערך אחר של n. קלי קלות.

מסתבר שהמנה \frac{g}{f}, אותה נסמן R, היא פונקציה רציונלית. למה? אם מחלקים את 2 האגפים של (*) ב-f(n,k) מקבלים את השיוויון הבא:

(\frac{f(n+1,k)}{f(n,k)} - 1) = R(n,k) (\frac{g(n,k+1)}{g(n,k)} - 1)

שגורר ש-R(n,k) היא בהכרח פונקציה רציונלית ב-n,k. מכאן נובע שכדי להוכיח זהות כל מה שאני צריך הוא את הפונקציה R, כי ממנה ניתן לשחזר את g ולוודא את השיוויון (*).

אם קורה התופעה, ואכן יש g כזו, אז שמה הוא "חברת-WZ של g", והזוג (f,g) נקרא זוג-WZ. לפונקציה הרציונלית R קוראים 'סרטיפיקט ההוכחה', כי ממנה אפשר לבנות בקלות הוכחה מלאה לזהות. (הערה: הקונבנציה היא דווקא לתת את R(n,k)=\frac{g(n,k)}{f(n,k-1)} בתור הסרטיפיקט, זה לא מאוד משנה.)

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

דוגמא פשוטה

ניקח את הזהות \sum_{k}\binom{n}{k}=2^{n}. ננרמל ונקבל \sum_{k}\binom{n}{k}2^{-n}=1. מתקיימת תופעת WZ, והפונקציה g(n,k)=-\binom{n}{k-1}2^{-n-1} היא חברת-WZ של f(n,k), ואכן מתקיים השיוויון היסודי הבא:

\binom{n+1}{k}2^{-n-1}-\binom{n}{k}2^{-n} = -\binom{n}{k}2^{-n-1}+\binom{n}{k-1}2^{-n-1}

לאחר הצמצומים הרלוונטים, מקבלים שזהות זו שקולה לזהות פסקל \binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}, שבעצמה שקולה לשיוויון \frac{n+1}{n+1-k} = 1 + \frac{k}{n+1-k} בפונקציות רציונליות. שימו לב שמנה R(n,k) = \frac{g(n,k)}{f(n,k)} = \frac{-2k}{n-k+1} היא פונקציה רציונלית, כמובטח.

דוגמא פחות פשוטה

\sum_{k}(-1)^{k}\binom{n}{k}\binom{2k}{k}4^{n-k}=\binom{2n}{n}. מנרמלים: \sum_{k}(-1)^{k}\binom{n}{k}\binom{2k}{k}4^{n-k}/\binom{2n}{n}=1. עבור n=1 מקבלים \frac{4-2}{2}=1. נניח ומישהו מסר לי את סרטיפיקט ההוכחה, שהוא R(n,k)=\frac{-2k^{2}}{(2n+1)(n-k+1)}. איך אוודא את הזהות בהינתן הסרטיפיקט? נציב g(n,k) = R(n,k)f(n,k) בשיוויון (*) ונחלק ב-f(n,k):

\begin{aligned} \frac{f(n+1,k)}{f(n,k)}-1 &= \frac{R(n,k+1)f(n,k+1)}{f(n,k)}-\frac{R(n,k)f(n,k)}{f(n,k)} \implies \\  \frac{n+1}{n+1-k}4\frac{n+1}{2(2n+1)}-1 &= -\frac{2(k+1)^{2}}{(2n+1)(n-k)}(-\frac{1}{4})\frac{n-k}{k+1}\frac{2(2k+1)}{k+1}+\frac{2k^{2}}{(2n+1)(n-k+1)} \implies \\ \frac{2(n+1)^{2}}{(n+1-k)(2n+1)}-1 &= \frac{2k+1}{2n+1}+\frac{2k^{2}}{(2n+1)(n-k+1)}  \end{aligned}

מכפילים במכנה המשותף (n+1-k)(2n+1) ומקבלים 2(n+1)^{2}-(n+1-k)(2n+1)=(2k+1)(n+1-k)+2k^{2}. פתיחת סוגריים משלימה את הוידוא.

מציאת g

נותר להסביר איך מוצאים את g מהשיוויון (*). נגדיר את פונקצית העזר h(k)=f(n+1,k)-f(n,k) (חושבים על n בתור פרמטר). אם אנחנו יודעים לפתור את השיוויון (*), אז באופן שקול אנחנו יודעים לפתור את המשוואה h(k)=G(k+1)-G(k), כי G(k)=g(n,k) הוא פיתרון כאשר g היא חברת-WZ של f.

נשים לב ש-h(k) היפר-גיאומטרית במשתנה אחד:

\frac{h(k+1)}{h(k)}=\frac{f(n+1,k+1)-f(n,k+1)}{f(n+1,k)-f(n,k)}=(\frac{f(n+1,k+1)}{f(n,k)}-\frac{f(n,k+1)}{f(n,k)})\cdot(\frac{f(n+1,k)}{f(n,k)}-1)^{-1}

בנוסף, בגלל שאנחנו מעוניינים ש-g תהיה היפר-גיאומטרית, אז גם G היא היפר-גיאומטרית במשתנה אחד.

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

זה הרגע שבו אתם צריכים לשאול: למה אי-אפשר להפעיל את האלגוריתם הנ"ל ישירות על f(n,k) במקום על f(n+1,k)-f(n,k), לקבל איזושהי פונקציה G(k) שמקיימת \sum_{k=0}^{K }f(n,k) = G(K+1), ואז להציב נגיד K=n ולקבל בדיוק את הסכום ההיפר-גיאומטרי שרצינו?
הסיבה פשוטה – אפשר לנסות להפעיל את האלגוריתם על f(n,k) במקום על ההפרש f(n+1,k)-f(n,k) אבל בסיכוי גבוה הוא יכשל. הוא לא עובד בכל מחיר אלא אם ורק אם יש פיתרון היפר-גיאומטרי. אם נחזור לדוגמא הבסיסית f(n,k) = \binom{n}{k}2^{-n}, אפשר לוודא שלסכום \sum_{k=0}^{K} f(n,k) אין ייצוג בתור פונקציה היפר-גיאומטרית ב-K, וזה לא סותר את העובדה שכשמציבים K=n פתאום מקבלים משהו אלגנטי (את הקבוע 1). אבל אם עובדים עם f(n+1,k)-f(n,k) אז הסכום \sum_{k=0}^{K} f(n+1,k)-f(n,k) כן היפר-גיאומטרי ב-k ויוצא -\binom{n}{K-1}2^{-n-1}. במילים אחרות, כשמפעילים את האלגוריתם על הביטוי ההיפר-גיאומטרי המקורי, אין סיבה שהוא יצליח, אבל אם מפעילים אותו על ההפרש אז יש צ'אנס לא רע להצלחה, כי הזהות (*) יפה מכדי לא להתקיים.

אגב, כל הקונספט של זוגות WZ פורסם לראשונה במאמר של Wilf ו-Zeilberger מ-1990, שמו "Rational Functions Certify Combinatorial Identities". מוזמנים לקרוא את המקור.

6. אלגוריתם גוספר

מבוא

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

האלגוריתם של גוספר פותר בעיה של אינטגרציה דיסקרטית: הקלט שלו הוא סדרה היפר-גיאומטרית \{ t_k \}_{k \ge 0} (לדוגמא: t_k = \binom{2k}{k}), והפלט שלו הוא סדרה היפר-גיאומטרית \{ s_k \}_{k \ge 0} כך ש-s_{n}=\sum_{k=0}^{n-1}t_{k} לכל n \ge 1, אם קיימת כזו. אחרת, הוא מודיע בעצב שאין ייצוג "יפה", כלומר היפר-גיאומטרי, לסכום \sum_{k=0}^{n-1}t_{k}.

נתחיל בלשים לב שבעיית הסכימה שקולה, עד כדי קבוע, למציאת ביטוי s_n המקיים s_{n+1}-s_{n}=t_{n} (זה ידוע בחדו"א בתור "המשפט היסודי"…). כאמור, האלגוריתם מוצא s_n אם הוא קיים והיפר-גיאומטרי.

נתאר את האלגוריתם בשני שלבים.

  • שלב א': רדוקציה למציאת פונקציה רציונלית שמקיימת רקורסיה מעומק 1.
  • שלב ב': רדוקציה למציאת פולינום שמקיים רקורסיה מעומק 1 ופתרון בעיה זו עם אלגברה לינארית.

ועכשיו נפרק כל שלב לשני צעדים:

פירוט

שלב א1: נסמן r(k)=\frac{t_{k+1}}{t_{k}}, שהיא פונקציה רציונלית ב-k. נניח שיש פיתרון היפר-גיאומטרי למשוואה s_{n+1}-s_{n}=t_{n}.

נשים לב שאם s_n היפר-גיאומטרי, מתקיים:

\frac{s_{n}}{t_{n}} = \frac{s_{n}}{s_{n+1}-s_{n}} = \frac{1}{\frac{s_{n+1}}{s_{n}}-1}

כלומר המנה \frac{s_n}{t_n} היא פונקציה רציונלית. נסמן אם כן s_{n}=y(n)t_{n}, כאשר y פונקציה רציונלית שאותה אנחנו מחפשים.

שלב א2: המשוואה הבסיסית s_{n+1}-s_{n}=t_{n} הפכה ל-y(n+1)t_{n+1}-y(n)t_{n}=t_{n}, כלומר:

y(n+1)r(n)-y(n) = 1

וקיבלנו נוסחת נסיגה מעומק 1 שמפתרונה y(n) אפשר לשחזר את s_n בקלות: s_{n}=y(n)t_{n}. כמו שהזכרנו בהתחלה, יש אלגוריתם שפותר נוסחאות נסיגה עם מקדמים שהם פונקציות רציונליות, אבל במקרה של עומק 1 נוכל להסתדר גם בלי!

שלב ב1: נתחיל ב"למת ההצגה": כל פונקציה רציונלית r(n) אפשר להציג בצורה \frac{a(n)}{b(n)}\frac{c(n+1)}{c(n)}, כך שמתקיים התנאי \forall h \in\mathbb{N}_{0}\implies\gcd(a(n),b(n+h))=1. ארחיב על למה זו בתרגילים, אבל בואו נראה מה היא נותנת לנו. נפעיל אותה על r שלנו:

r(n)=\frac{a(n)}{b(n)}\frac{c(n+1)}{c(n)}

ונציב במשוואה של השלב הקודם:

y(n+1)\frac{a(n)}{b(n)}\frac{c(n+1)}{c(n)}-y(n)=1\implies y(n+1)\frac{a(n)c(n+1)}{b(n)}-c(n)y(n)=c(n)

כדי לפשט את המקדמים, טבעי לעשות את שינוי המשתנים y(n)=\frac{b(n-1)}{c(n)}x(n), שנותן:

(**)a(n)x(n+1)-b(n-1)x(n) = c(n)

במובן מסויים, לא השתנה כלום – שוב קיבלנו משוואה מעומק 1. עכשיו המקדמים הם פולינומים במקום פונקציות רציונליות, אבל גם קודם יכולנו להגיע למצב זה (באמצעות הכפלה במכנה משותף).
מה שהשתנה הוא הקסם הבא, שאקרא לו "למת הפולינום", שאומרת שפיתרון בדמות פונקציה רציונלית למשוואה (**) הוא בהכרח פולינום ב-n. אני משאיר את הלמה הזו כתרגיל (בהמשך תובא הדרכה).

שלב ב2: מהלמה הזו ברור מה צריך לעשות: להציב x(n)=\sum_{i=0}^{d}a_{i}n^{i} כאשר d מעלת הפיתרון, להשוות מקדמים של חזקות זהות של n ולקבל משוואות לינאריות על a_i ולפתור עם אלגברה לינארית (זה מזכיר את אלגוריתם סלין כי מקדמי המשוואות הם פולינומים). זהו.

מה השמטנו? (או: תרגילים)

מבחינה אלגוריתמית, חסרים לנו 2 מרכיבים: הוכחה אלגוריתמית ללמת ההצגה, וחסם עליון על המעלה d. אל תמשיכו הלאה בלי שפתרתם את 3 התרגילים הבאים (בסוף הפרק יש רמזים):

תרגיל 3: הוכיחו את למת ההצגה באופן אלגוריתמי.
תרגיל 4: הוכיחו את למת הפולינום.
תרגיל 5: מצאו חסם למעלה d של הפיתרון x כפונקציה של a,b,c.

תקציר האלגוריתם

לסיכום: מחשבים את הפונקציה הרציונלית r(n)=t_{n+1}/t_{n} ומציגים אותה בצורה מסויימת באמצעות למת ההצגה. כך מקבלים את המשוואה x(n+1)a(n)-b(n-1)x(n)=c(n), שפותרים בעזרת אלגברה לינארית סטנדרטית (השוואת מקדמים ופתרון משוואות). מתוך x משחזרים את s באופן הבא:

s_{n}=y(n)t_{n}=x(n)\frac{b(n-1)}{c(n)}t_{n}

דוגמאות

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

דוגמא 1: S_{n}=\sum_{k=0}^{n-1}k!. במקרה זה, t_{n}=n!,r(n)=n+1. בגלל ש-\gcd(n+1,1)=1 אפשר לבחור a(n)=n+1,b(n)=c(n)=1 ולקבל את הרקורסיה (n+1)x(n+1)-x(n)=1. לרקורסיה זו לא יכול להיות פיתרון פולינומיאלי, כי המעלה של x(n)+1 קטנה ממש מהמעלה של (n+1)x(n+1), ולכן בוודאות אין הצגה היפר-גיאומטרית לסכום. לא מאוד מפתיע, אבל עכשיו יש לנו הוכחה. שזה עניין חשוב במתמטיקה.

דוגמא 2: S_{n}=\sum_{k=0}^{n}k\cdot k!. במקרה זה r(n)=\frac{(n+1)^{2}}{n} , t_{n}=n\cdot n!. הפעם h=1 מפר את התנאי של למת ההצגה כי \gcd((n+1)^{2},n+h)=n+1. לכן נכתוב \frac{(n+1)^{2}}{n}=\frac{n+1}{1}\frac{n+1}{n}, וזו הצגה חוקית, כלומר אפשר לבחור a(n)=n+1,b(n)=1,c(n)=n, מה שנותן את הרקורסיה x(n+1)(n+1)-x(n)=n.
מהשוואת מעלות ברור שפיתרון פולינומיאלי יהיה קבוע, ואכן x(n)=1 הוא פיתרון סבבה שנותן y(n)=\frac{b(n-1)}{c(n)}x(n)=\frac{1}{n}, כלומר s_{n}=y(n)t_{n}=n!. אכן, s_{n+1}-s_{n}=t_{n} ולכן:

\sum_{k=0}^{n}k!=\sum_{k=0}^{n}(s_{k+1}-s_{k})=s_{n+1}-s_{0}=(n+1)!-1

יש שגידו ששתי הדוגמאות האלה מזכירות את ההבדל בין \int_{0}^{t}e^{x^{2}} \,\mathrm{d}x (פונקציה לא אלמנטרית) ל- \int_{0}^{t}xe^{x^{2}} \,\mathrm{d}x=\frac{1}{2}\int_{0}^{t}(e^{x^{2}})' \,\mathrm{d}x=\frac{1}{2}(e^{t^{2}}-1) (פונקציה אלמנטרית).

דוגמא 3: כעת נקשר את האלגוריתם לפרק הקודם. נשתמש באלגוריתם גוספר כדי למצוא את חברת-WZ של f(n,k)=\binom{n}{k}2^{-n}. כזכור, מתחילים עם להגדיר פונקציית עזר, פונקציית הפרש:

h(k) = f(n+1,k)-f(n,k) = \binom{n+1}{k}2^{-n-1}-\binom{n}{k}2^{-n}

החלק הכי ארוך והכי חשוב הוא חישוב המנה r(k) = \frac{h(k+1)}{h(k)}:

\begin{aligned} r(k) &= \frac{\binom{n+1}{k+1}-2\binom{n}{k+1}}{\binom{n+1}{k}-2\binom{n}{k}}  \\ & = \frac{\frac{n+1}{k+1}-2\frac{n-k}{k+1}}{\frac{n+1}{n+1-k}-2}  \\ & = \frac{n+1-k}{k+1}\cdot\frac{2k-n+1}{2k-n-1}  \end{aligned}

וזו כבר הצגה בצורה של למת ההצגה, כלומר a(k)=n+1-k,b(k)=k+1,c(k)=2k-n-1. נרצה לפתור את המשוואה (n+1-k)x(k+1)-(k)x(k)=2k-n-1. משיקולי מעלות, x(k) צריך להיות קבוע, ואכן x(k) \equiv -1 הוא פיתרון מתאים. על כן,

g(n,k) = h(k)\frac{b(k-1)}{c(k)}x(k) = -(\frac{k}{2k-n-1})(\binom{n+1}{k}2^{-n-1}-\binom{n}{k}2^{-n})

עוד קצת עבודת פישוט מראה ש-g(n,k)=-\binom{n}{k-1}2^{-n-1} ושיש צדק בעולם.

רמזים והדרכה לתרגילי הפרק

נסיים ברמזים לשלושתם התרגילים החשובים:

רמז לתרגיל 3: נציג את r(n) כפונקציה רציונלית \frac{p(n)}{q(n)} עם מונה ומכנה זרים. אם התנאי h\in\mathbb{N}_{0}\implies\gcd(p(n),q(n+h))=1 מתקיים, סיימנו כי אפשר לבחור a=p, b=q, c=1. אחרת, צריך לתקן את זה. נאתחל את c להיות שווה 1.

אם h ספציפי מפר תנאי זה, כלומר מקבלים שה-\gcd הוא איזשהו g(n) \neq 1, נצטרך לבצע את התהליך הפשוט הבא: ראשית, נחלק את p ב-g(n) ואת q ב-g(n-h). החילוקים האלה מכריחים אותנו למצוא יצוג מהצורה \frac{d(n+1)}{d(n)} ל-\frac{g(n)}{g(n-h)} ומתבקש לבחור d(n)=\prod_{j=1}^{h}g(n-j), ונחליף את c ב-c \cdot d.
נחזור על התהליך לכל ה-h הרעים. יש מספר סופי שלהם, וכדי למצוא אותם נחשב רזולטנטה של p(n) ו-q(n+\alpha). נקבל פולינום ב-\alpha שהשורשים השלמים האי-שליליים שלו הם בדיוק הערכים עבורם \gcd(p(n),q(n+h))\neq 1.
חישוב רזולטנטה הוא חישוב של דטרמיננטה מסויימת (קרי: בעיה אלגוריתמית פתורה), ומציאת שורשים שלמים של פולינום זה גם עניין פתור, לפחות במקרה של פולינום עם מקדמים רציונליים.
טוב, פתרתי לכם כמעט את כל התרגיל. תרגיל חדש – הראו שהצורה של למה ההצגה היא יחידה, כלומר היא צורה קנונית!

רמז לתרגיל 4: נניח שיש פיתרון רציונלי x(n)=\frac{f(n)}{g(n)} עם f,g זרים, ונניח בשלילה ש-g אינה קבועה.
נבחר N שלם מקסימלי כך ש-\gcd(g(n),g(n+N))\neq1. הוא אי-שלילי כי N=0 מועמד והוא סופי כי הוא חסום ע"י המרחק בין שני השורשים הכי גדולים של g.
נסמן u(n)=\gcd(g(n),g(n+N)). השתמשו בשיוויון הבסיסי x(n+1)a(n)-b(n-1)x(n)=c(n) כדי להראות ש-u(n-N)|b(n-1)g(n+1). מקסימליות N מראה ש-u(n-N)|b(n-1), כלומר u(n)|b(n+N-1).
בדומה, u(n+1)|a(n), כלומר u(n)|a(n-1), אבל אז a(n-1),b(n+N-1) לא זרים, סתירה לבנייה של למת ההצגה.

רמז לתרגיל 5:  תתחילו עם המקרה \deg a \neq \deg b, שהוא פשוט יותר. המקרה המשלים נהיה מגעיל כאשר ל-a,b אותו מקדם מוביל כי צריך להסתכל על המקדם-אחרי-המוביל, אבל לא להיבהל ("Don't Panic").

7. הסימטריה של WZ

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

(*)f(n+1,k)-f(n,k) = g(n,k+1)-g(n,k)

 

שימוש א': חישוב ערכים עוקבים של סכום היפר-גיאומטרי ביעילות

תהי f פונקציה היפר-גיאומטרית 'מנורמלת', כלומר כזו שמקיימת \sum_{k}f(n,k)=\text{const}, ותהי g חברת-WZ של f. נניח ואנחנו רוצים לסכום את h(n)=\sum_{k=0}^{n}f(n,k), לדוגמא:

f(n,k)=\binom{3n}{k}/8^{n}

שימו לב לגבולות הסכימה – הם סופיים (בין 0 ל-n), ולכן אף אחד לא מבטיח שיש לסכום h ייצוג יפה. (אנחנו כן יודעים שסכימה על כל השלמים – ששקולה לסכימה בין 0 ל-3n – כן תיתן ביטוי יפה, ספציפית: 1.)
כדי לחשב את h(n) = 8^{-n} \sum_{k=0}^{n} \binom{3n}{k} עבור n=0,1,2,\cdots, N, צריך נאיבית O(N^2) הערכות של הפונקציה \binom{3n}{k}. נסביר איך אפשר לעשות זאת ב-O(N) הערכות (של פונקציה היפר-גיאומטרית אחרת).

נסכום את הזהות (*) על פני k=0,1,2,\cdots, n:

\begin{aligned} \sum_{k=0}^{n}f(n+1,k)-\sum_{k=0}^{n}f(n,k) &= g(n,n+1)-g(n,0) \implies \\ h(n+1)-h(n) &= g(n,n+1)-g(n,0)+f(n+1,n+1) \end{aligned}

וכעת נסכום על n בין 0 ל-m-1:

h(m) = h(0)+\sum_{n=0}^{m-1} (g(n,n+1)-g(n,0)+f(n+1,n+1)))

ומנוסחה זו רואים שאם יודעים את h(i) צריך לחשב רק עוד O(1) ביטויים היפר-גיאומטריים נוספים כדי לקבל את h(i+1). מכאן חישוב N ערכים עוקבים של הסכום h(i) יקח  O(N) הערכות פונקציה. מגניב!

שימוש ב': הזהות הנלוות (Companion Identity)

יהי (f,g) זוג-WZ . נניח 2 הנחות סבירות: ש-f_{k}=\lim_{n\to\infty}f(n,k) קיים וסופי, וש-\lim_{L\to\infty}\sum_{n\ge0}g(n,-L)=0. כל זאת בנוסף להנחה הרגילה ש-\lim_{|k|\to\infty}g(n,k)=0.

כדי להגיע לזהות הנלוות, נתחיל במשוואה הבסיסית:

f(n+1,k)-f(n,k) = g(n,k+1)-g(n,k)

נסכום על n=0,\cdots,N:

f(N+1,k)-f(0,k) = \sum_{n=0}^{N}g(n,k+1)-\sum_{n=0}^{N}g(n,k)

נשאיף את N לאינסוף ונקבל:

f_{k}-f(0,k) = \sum_{n\ge0}g(n,k+1)-\sum_{n\ge0}g(n,k)

סכימה על k בין -L ל-K-1 והשאפת L לאינסוף נותנת את הזהות הבאה:

\sum_{k\le K-1}(f_{k}-f(0,k)) = \sum_{n\ge0}g(n,K)

שנקראת הזהות הנלוות (של הזהות \sum_{k} f(n,k) = \text{const}).

טוב, דוגמה. ניקח את \sum_{k}\binom{n}{k}^{2}=\binom{2n}{n}. אחרי נרמול מקבלים \sum_{k}\binom{n}{k}^{2}/\binom{2n}{n}=1. סכום זה מקיים את תופעת WZ, עם R(n,k)=\frac{-k^{2}(3n-2k+3)}{2(2n+1)(n-k+1)^{2}} (המשמעות של זה כזכור היא ש-g = R f).
בנוסף, הוא מקיים את התנאים לקיום זהות נלוות, ומקבלים f_{k}=0,f(0,k)=\delta_{0,k}, מה שגורם לאגף שמאל של הזהות הנלוות להיות מאוד מנוון. הזהות הנלוות יוצאת:

\sum_{n\ge0} R(n,K) \frac{\binom{n}{K}^2}{\binom{2n}{n}} = \begin{cases}  0 & K \le0\\  -1 & K \ge 1  \end{cases}

ניתן לפשט ולקבל (תרגיל):

\sum_{n\ge0}\frac{(3n-2k+1)}{(2n+1)}\frac{\binom{n}{k}^{2}}{\binom{2n}{n}} = 2

עבור k \ge 0 וזו זהות חדשה ומגניבה בטירוף. כבר עבור k=0 מקבלים ערך של טור (לכאורה) הזוי ומוקרץ. אהבתי!

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

8. אלגוריתם ציילברגר

מבוא ומוטיבציה

ציינתי שתופעת WZ לא תמיד קורה. בשביל זה יש את האלגוריתם של ציילברגר, שנציג עכשיו. הוא עובד באותם מקרים שהאלגוריתם סלין עובד (קרי: כל המקרים הסבירים), ולמעשה נותן לנו את אותו פלט – רקורסיה עבור F(n)=\sum_{k}f(n,k). עם זאת, הוא עושה זאת באופן שונה לחלוטין ומהיר יותר משמעותית. היסטורית, הוא הקדים את תופעת WZ ודרכו גילו אותה (הוא מכליל את מה שתיארנו בפרקים 5-7 ובין השאר גם משתמש באלגוריתם גוספר).

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

כדי למצוא g כזו, מפעילים את גוספר על t_{k}=f(n,k). הכל טוב ויפה, ומעבר לכך – נראה שאנחנו מקבלים הרבה יותר ממה שאנחנו צריכים: אנחנו יכולים לחשב את \sum_{k=0}^{N}f(n,k) גם עבור N שרירותי, ולא רק עבור N=n. טוב מידי מכדי להיות אמיתי, וכמו שכבר הזכרנו, ברוב המקרים, ביניהם f(n,k)=\binom{n}{k}, פשוט אין כזו g ולכן אלגוריתם גוספר יחזיר תשובה שלילית (אנלוגי לכך שאנחנו יודעים לחשב את האינטגרל של e^{-t^2} על כל הישר – \int_{\mathbb{R}} e^{-t^2} \,\mathrm{d}t = \sqrt{\pi} – למרות שאין פונקציה קדומה אלמנטרית ל-e^{-t^2}).

אבל אפשר להציל רעיון זה! לדוגמא, ראינו מתופעת WZ שלפעמים גוספר עובד על  f(n+1,k)-f(n,k). אבל גם זה נכשל לעיתים… אולי אפשר להכליל וקחת את זה רחוק יותר? בואו נחפש מקדמים \{a_{j}(n)\}_{j=0}^{J} כך שעל \sum_{j=0}^{J}a_{j}(n)f(n+j,k) אפשר יהיה להפעיל את גוספר בהצלחה, כלומר למצוא g היפר-גיאומטרית ב-k שתקיים:

\sum_{j=0}^{J}a_{j}(n)f(n+j,k)=g(n,k+1)-g(n,k)

כשיש לנו את הזהות הזו, אפשר לסכום על k \in \mathbb{Z} (תחת התנאי \lim_{|k|\to\infty}g(n,k)=0 שלרוב יתקיים), ולקבל רקורסיה הומוגונית על F(n), כמו באלגוריתם סלין:

\sum_{j=0}^{J}a_{j}(n)F(n+j)=0

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

מה נעשה בפרק זה? ראשית, בעזרת אלגוריתם סלין, נוכיח שבהכרח קיימים J ומקדמים a_j מתאימים, ולכן כל הרעיון הזה הוא בר-תוקף. על הדרך נראה ש-R=g/f היא פונקציה רציונלית, כמו שקורה בתופעת WZ.
אבל לא נסתפק בזה. אנחנו נציג  דרך עדיפה למציאת J ו-a_j – עדיפה כי היא תיתן את ה-J המינימלי שיהיה קטן יותר מהחסם של סלין ברוב המקרים.
הסיבה היחידה לקרוא את הוכחת הקיום היא בגלל שבדרך העדיפה לא ברור אפריורי שהאלגוריתם עובד – תחליטו אתם אם זו סיבה טובה.

הוכחת קיום

מאלגוריתם סלין, נקבל \sum_{0\le i \le I, 0\le j \le J} a_{i,j}(n)f(n+j,k+i)=0. הסכימה כאן היא גם על i וגם על j, ואנחנו רוצים רק על j.
נכפיל את שני האגפים במינוס 1, ונוסיף לשניהם \sum_{0\le i \le I, 0 \le j \le J}a_{i,j}(n)f(n+j,k):

\begin{aligned} \sum_{0 \le i \le I, 0 \le j \le J} a_{i,j}(n)f(n+j,k) &= \sum_{0 \le i \le I, 0 \le j \le J}a_{i,j}(n)(f(n+j,k)-f(n+j,k+i))  \implies \\ \sum_{0 \le j \le J}(\sum_{0 \le i \le I}a_{i,j}(n))f(n+j,k) &= \sum_{0 \le j \le J}\sum_{1 \le i \le I}a_{i,j}(n)(f(n+j,k)-f(n+j,k+i)) \end{aligned}

אני טוען שסיימנו! אגף שמאל הוא כמו שרצינו (סוכמים רק על j), רק נותר להראות שאגף ימין הוא מהצורה g(n,k+1)-g(n,k) כאשר g/f פונקציה רציונלית. לשם כך, מספיק לקחת ביטוי בודד a_{i,j}(n)(f(n+j,k)-f(n+j,k+i)). המקדם a_{i,j}(n) לא תלוי ב-k והוא פונקציה רציונלית אז אפשר לוותר עליו, לכן יש לנו את f(n+j,k)-f(n+j,k+i) עם i >0. בגלל שאפשר לכתוב אותו כסכום טלסקופי \sum_{i'=0}^{i-1}(f(n+j,k+i')-f(n+j,k+i'+1)), מספיק להוכיח את זה עבור f(n+j,k+i')-f(n+j,k+i'+1) ואז אפשר לבחור g(n,k)=-f(n+j,k+i') והרציונליות נובעת מההיפר-גיאומטריות של f(n,k)\blacksquare

האלגוריתם באמצעות דוגמא

עכשיו נראה איך מוצאים את המקדמים בפועל, בלי לעבור דרך אלגוריתם סלין. נראה זאת על דוגמא שתכיל את כל המרכיבים של הבעיה. ננסה להוכיח את הזהות \sum_{k=0}^{n}\binom{n}{k}^{2}=\binom{2n}{n} – בלי לדעת את אגף ימין מראש!
נסמן f(n,k)=\binom{n}{k}^{2} (שימוש לב – לא נרמלנו כלום). ננחש את J. נתחיל בקטן:  J=1 (אם לא נצליח, נגדיל ונחזור על הכל – הדבר החכם לעשות הוא חיפוש בינארי. בכל אופן, אלגוריתם סלין נותן חסם עליון שתקף גם כאן, לפי הוכחת הקיום).
אנחנו רוצים להפעיל את גוספר על t_{k}=a_{0}(n)f(n,k)+a_{1}(n)f(n+1,k), כאשר a_{0},a_{1} מקדמים שיבחרו כך שגוספר יצליח (אחרי זה ההמשך ברור – סוכמים על k, מקבלים רקורסיה ופותרים אותה). נחשב את r(k) = \frac{t_{k+1}}{t_k}:

\begin{aligned} \frac{t_{k+1}}{t_{k}} &= \frac{a_{0}(n)f(n,k+1)+a_{1}(n)f(n+1,k+1)}{a_{0}(n)f(n,k)+a_{1}(n)f(n+1,k)} \\ &= \frac{a_{0}(n)\binom{n}{k+1}^{2}+a_{1}(n)\binom{n+1}{k+1}^{2}}{a_{0}(n)\binom{n}{k}^{2}+a_{1}(n)\binom{n+1}{k}^{2}}  \end{aligned}

נשתמש בהיפר-גיאומטריות כדי לפשט את הביטויים ולהישאר עם פונקציות רציונליות. ראשית נחלק ב-\binom{n}{k}^{2}:

\begin{aligned} &= \frac{a_{0}(n)(\frac{n-k}{k+1})^{2}+a_{1}(n)(\frac{n+1}{k+1})^{2}}{a_{0}(n)+a_{1}(n)(\frac{n+1}{n+1-k})^{2}} \end{aligned}

ועכשיו נחשב מכנה משותף כך שבמונה ובמכנה יהיו פולינומים:

\begin{aligned} &= \frac{a_{0}(n)(n-k)^{2}+a_{1}(n)(n+1)^{2}}{a_{0}(n)(n+1-k)^{2}+a_{1}(n)(n+1)^{2}}\frac{(n+1-k)^{2}}{(k+1)^{2}} \end{aligned}

נסמן u(k)=(n+1-k)^{2},v(k)=(k+1)^{2} ו-p(k)=a_{0}(n)(n+1-k)^{2}+a_{1}(n)(n+1)^{2}. השיוויון הופך ל:

r(k) = \frac{t_{k+1}}{t_{k}}=\frac{p(k+1)}{p(k)}\frac{u(k)}{v(k)}

כדי להפעיל את גוספר, צריך להציג את \frac{t_{k+1}}{t_{k}} בצורה \frac{p_1(k+1)}{p_1(k)}\frac{p_{2}(k)}{p_{3}(k)} כאשר \gcd(p_{2}(k),p_{3}(k+h))=1 לכל h \in \mathbb{N}_{0}. המנה \frac{p(k+1)}{p(k)} כבר נמצאת בצורה הזו (זה תמיד יהיה המצב) לכן נשאר למצוא הצגה זו רק עבור \frac{u(k)}{v(k)}, כלומר להציג \frac{u(k)}{v(k)}=\frac{p_{0}(k+1)}{p_{0}(k)}\frac{p_{2}(k)}{p_{3}(k)} ואז נבחר p_1 = p_0 \cdot p.
במקרה שלנו לא צריך להתאמץ, כי ההצגה המתבקשת p_{0}=1,p_{2}=u,p_{3}=v היא כבר הצגה טובה (כי \gcd(n+1-k,k+1+h)=1 כפולינומים ב-k כאשר n משתנה ו-h מספר). לכן אפשר לבחור:

\begin{aligned} p_{2}(k) &= (n+1-k)^{2}  \\p_{3}(k) &= (k+1)^{2} \\ p_1(k) &= p_{0}(k)p(k)  \\ &= a_{0}(n+1-k)^{2}+a_{1}(n+1)^{2} \\ &  = (a_{0}f(n,k)+a_{1}f(n+1,k))\frac{(n+1-k)^{2}}{f(n,k)} \end{aligned}

ועכשיו נותר לפתור את הרקורסיה מעומק 1 הבאה:

p_{2}(k)x(k+1)-p_{3}(k-1)x(k)=p_{1}(k)

היופי הוא שרק אגף ימין תלוי במקדמים הלא ידועים a_{i}(n), ותלות זו היא לינארית! (זה תמיד יקרה.)
לכן אפשר לעשות כרגיל רדוקציה למשוואות לינאריות: אלגוריתם גוספר נותן לנו חסם \Delta למעלה של x(k). נציב x(k)=\sum_{i\le\Delta}\beta_{i}k^{i} ונשווה מקדמים של אותן חזקות k. כך נקבל משוואות בנעלמים \{\beta_{i}\}\cup\{a_{j}\} (סה"כ J+\Delta+2 נעלמים). במקרה שלנו, גוספר נותן \Delta = 1 (בידקו!) ובחרנו J=1, אז יש 4 נעלמים. אם לא נמצא פיתרון, נגדיל את J ונחזור על התהליך, אבל יוצא שכן יש פיתרון למערכת – נציב x(k)=\beta_{0}+\beta_{1}k ונפתור בעצמנו:

\begin{aligned} (n+1-k)^{2} (\beta_{0}+\beta_{1}+\beta_{1}k)-k^{2}(\beta_{0}+\beta_{1}k) &= a_{0}(n)(n+1-k)^{2}+a_{1}(n)(n+1)^{2}\implies  \\ k^{3}: \, \beta_{1}-\beta_{1} &= 0  \\ k^{2}: \, \beta_{0}+\beta_{1}-2(n+1)\beta_{1}-\beta_{0} &= a_{0}  \\ \ k^{1}: \, (n+1)^{2}\beta_{1}-2(n+1)(\beta_{0}+\beta_{1}) &= -2a_{0}(n+1)  \\ k^{0}: \, (n+1)^{2}(\beta_{0}+\beta_{1}) &= (a_{0}+a_{1})(n+1)^{2} \end{aligned}

עכשיו צריך למצוא איבר לא טריוויאלי בגרעין. המשוואה הראשונה היא טאוטולוגיה (נשלח אותה למועדון הזה).
המשוואה השנייה נותנת a_{0}=-(2n+1)\beta_{1}.
המשוואה השלישית, לאחר צמצום ב-n+1 והצבת a_0, נותנת \beta_{0}=-\frac{3}{2}(n+1)\beta_{1}.
המשוואה הרביעית נותנת \beta_{0}+\beta_{1}=a_{0}+a_{1}.
לכן הגרעין נפרש ע"י:

(a_{0},a_{1},\beta_{0},\beta_{1})=\beta_{1}(-2n-1,\frac{n+1}{2},-\frac{3}{2}(n+1),1)

נבחר \beta_{1}=2 ונקבל את הפיתרון x(k)=-3(n+1)+2k, ולכן t_{k}=-2(2n+1)\binom{n}{k}^{2}+(n+1)\binom{n+1}{k}^{2} מקיים משוואה מהצורה:

(***) -2(2n+1)\binom{n}{k}^{2}+(n+1)\binom{n+1}{k}^{2} = g(n+1,k)-g(n,k)

כאשר g(n,k) נתונה ע"י:

\begin{aligned} g(n,k) &= p_{3}(k-1)x(k)\frac{t_{k}}{p_1(k)} \\ &  = k^{2}(-3n-3+2k)\frac{a_{0}f(n,k)+a_{1}f(n+1,k)}{a_{0}(n+1-k)^{2}+a_{1}(n+1)^{2}}  \\ &= k^{2}(-3n-3+2k)\frac{a_{0}f(n,k)+a_{1}f(n+1,k)}{(a_{0}f(n,k)+a_{1}f(n+1,k))\frac{(n+1-k)^{2}}{f(n,k)}} \\ &= (-3n-3+2k)\frac{f(n,k)k^{2}}{(n+1-k)^{2}}  = (-3n-3+2k)\frac{n!^{2}}{(k-1)!^{2}(n-k+1)!^{2}} \end{aligned}

עשיתי משהו מיותר עכשיו: נורא התאמצתי לכתוב את g מפורשות, למרות שהיא עצמה לא תופיע ברקורסיה. הרי, כשנסכום את המשוואה (***) אז g מתבטלת (כי \lim_{ |k| \to \infty} g(n,k) = 0) ונקבל -2(2n+1)F(n)+(n+1)F(n+1)=0, רקורסיה מעומק 1 שנפתרת יחסית בקלות:

F(n+1)=\frac{2(2n+1)}{n+1}F(n)=\frac{(2n+2)(2n+1)}{(n+1)^{2}}F(n)\implies F(n)=\binom{2n}{n}F(1)=\binom{2n}{n}

דוגמא תמציתית נוספת

נסתכל על הסכום F(n)=\sum_{k\ge0}(-1)^{k}\frac{\binom{n}{k}}{\binom{x+k}{k}}. נקרא למחובר f(n,k), ודרך האלגוריתם נקבל את השיוויון הבא:

(n+x)f(n,k)-(n+1+x)f(n+1,k)=g(n,k+1)-g(n,k)

עם R=\frac{g}{f}=\frac{k(k+x)}{n+1-k}.
סכימה על k נותנת F(n+1)/F(n)=\frac{n+x}{n+x+1}, כלומר F(n)=\frac{x}{x+n}F(0)=\frac{x}{x+n}.

סיכום

תרגיל 6: הראו שאלגוריתם ציילברגר על F(n)=\sum_{k}f(n,k) עובד עם J=1 אמ"מ קורה תופעת-WZ עבור f(n,k)/F(n).

לסיום הפרק, אדגיש את הנקודה הבאה: אלגוריתם ציילברגר מוצלח בהרבה מאלגוריתם סלין מבחינת סיבוכיות, בין השאר כי כמות המשתנים היא לינארית (J+\Delta+2) במקום ריבועית: I\cdot J.


מקווה שחידשתי. אלגברה לינארית זה אדיר. ביי!

מודעות פרסומת

אודות Ofir Gorodetsky

Graduate student at TAU. Can be contacted at bambaman1 at gmail dot com.
פוסט זה פורסם בקטגוריה אלגוריתמים, קומבינטוריקה. אפשר להגיע ישירות לפוסט זה עם קישור ישיר.

כתיבת תגובה

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

הלוגו של WordPress.com

אתה מגיב באמצעות חשבון WordPress.com שלך. לצאת מהמערכת / לשנות )

תמונת Twitter

אתה מגיב באמצעות חשבון Twitter שלך. לצאת מהמערכת / לשנות )

תמונת Facebook

אתה מגיב באמצעות חשבון Facebook שלך. לצאת מהמערכת / לשנות )

תמונת גוגל פלוס

אתה מגיב באמצעות חשבון Google+ שלך. לצאת מהמערכת / לשנות )

מתחבר ל-%s