אופרטור הנגזרת הדיסקרטית

שבתי הביתה.

בפוסט זה נחקור את האופרטור $\Delta f(x)=f(x+1)-f(x)$ , הפועל על פולינומים וטורים מסוימים (בפוסט זה נתעסק רק בפולינומים). כמו אופרטור הנגזרת הרגילה, אנחנו יכולים ללמוד הרבה על פונקציה מתוך הנגזרת הדיסקרטית שלה – לדוגמא: להסיק על קצב הגידול של f (אם הנגזרת של f היא פולינום ממעלה n, אז f פולינום ממעלה n+1), ואף את f עצמה עד כדי קבוע (באופן אנלוגי לאינטגרל לא מסוים). באופן כללי, קיימות כל האנלוגיות של החדו"א רק עם האופרטור $\Delta$ , ואפשר גם להגדיר אופרטור האנלוגי לאינטגרל המסויים (פחות טריוויאלי, אך נעשה זאת). במילים אחרות – כל פעם שהייתה לכם פונקצייה על הטבעיים (אנחנו רגילים להיתקל בכאלו בדמות סדרות: $a_0, a_1, a_2, \cdots$ ) ורציתם לגזור ולא ידעתם איך – עכשיו זה אפשרי ואף שימושי. למעשה, יש שימוש אינטנסיבי באופרטור הזה ובהכללותיו (גזירה דיסקרטית במרחק $a$ ) כדי למצוא פתרונות מקורבים למשוואות דיפרנציאליות באמצעות רדוקציה לנוסחאות נסיגה, ובאופן כללי באנליזה נומרית – לא אגע בנושאים אלו בפוסט הקצר והקומבינטורי במהותו הזה.

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

סימונים והגדרות: $[n]$ – קבוצת המספרים הטבעיים בין 1 לn.

מעלה של פולינום בk משתנים – מעלה של מונום $\prod_{i=1}^{k} x_i^{a_i}$ מוגדרת בתור $\sum a_i$ , ומעלה של פולינום כללי מוגדרת בתור המקסימום על פני מעלות המונומים המרכיבים אותו.

——

1. הגדרה פורמלית. נניח שיש לנו שדה $\mathbb{F}$ המכיל את הרציונליים (בפרט, זהו שדה אינסופי ממציין אפס). נגדיר אופרטור לינארי על חוג הפולינומים מעל $\mathbb{F}$ , ע"י $\Delta f(x)= f(x+1)-f(x)$ לכל פולינום f. מה הכוונה ב $f(x+1)$ ? פשוט להציב בפולינום $x+1$ (מבחינה גרפית, מדובר בהזזת הגרף של f יחידה אחת שמאלה) ולקבל פולינום חדש. אם f מוצג בבסיס הסטנדרטי $\{x^i\}_{i\ge 0}$ ואנחנו רוצים שגם $f(x+1)$ יוצג בבסיס זה, יש לפתוח סוגריים באמצעות הבינום של ניוטון, לקבץ גורמים ולחזור ליצוג בבסיס הזה.

באופן קצת לא פורמלי, אפשר להסתכל על האופרטור בתור $\Delta f(x)=\frac{f(x+1)-f(x)}{(x+1)-(x)}$ . כאן רואים את האנלוגיה לאופרטור הנגזרת $Df(x)$ המקיים $Df(x)=\lim_{\epsilon\to0}\frac{f(x+\varepsilon)-f(x)}{(x+\varepsilon)-(x)}$ . אפילו שאת אופרטור הנגזרת אנחנו רגילים לפגוש בהקשרים אנליטיים בדר"כ, אפשר להגדירו באופן מופשט על כל חוג פולינומים, ונסביר: מעל הממשיים, בתורה שדה עם נורמה, אפשר להגדיר נגזרת באמצעות גבול, ולקבל שמתקיים השיווין הבא לכל n טבעי: $\frac{dx^{n}}{dx}=nx^{n-1}$ , כאשר הנגזרת של 1 היא 0. כדי להגדיר את D, אופרטור הנגזרת, על חוג פולינום מעל שדה שאינו בהכרח הממשיים, נגדיר אותו באמצעות פעולתו המתבקשת על הבסיס למרחב הפולינומים: $Dx^{n}=nx^{n-1}$ . אופרטור זה מקיים את התכונות הקלאסיות של נגזרת – כלל המכפלה ('לייבניץ'), כלל השרשרת וכו'. גם הוא בעל שימושים אלגבריים – לדוגמא, $gcd(f,Df)$ מודד כמה אי פריד (inseparable) הפולינום f. אבל זה לא נושא הפוסט.

2. חיפוש אחר בסיס נוח. בניגוד לפעולה של D, הפעולה של $\Delta$ על הבסיס הסטנדרטי אינה סימפטית:

$\Delta x^n = (x+1)^n-x^n = \sum_{i=0}^{n-1} \binom {n}{i}x^i$

הינו רוצים למצוא בסיס $\{f_n\}_{n \ge 0}$ של פולינומים ממעלות הולכות וגדלות (ספציפית, $\deg f_n = n$ ), כך ש $\Delta f_{n+1}$ יהיה סקלר כפול $f_n$ , כמו שתוצאת $Dx^{n+1}$ היא כפולה של $x^{n}$ .

נדרוש דרישה חזקה יותר – שהסקלר יהיה 1. אבל האם זו באמת דרישה חזקה יותר? ניזכר רגע בטורי טיילור (אם מרתיע אתכם הסכום האינסופי, דמיינו שהוא סופי): טור טיילור של פונקציה חלקה f הוא סכום של מונומים מהצורה $\frac{x^n}{n!}$ , עם מקדמים ששווים לנגזרת הn-ית של f באפס. פולינומים אלו הם מתיחה של הבסיס הסטנדרטי, והם מקיימים $D\frac{x^{n+1}}{(n+1)!}=\frac{x^{n}}{n!}$ . מכאן באה הגדולה של טור טיילור – גזירה (אפילו פורמלית) של הטור $\sum_{n \ge 0} a_n \frac{x^n}{n!}$ היא הזזה של המקדמים – $\sum_{n\ge0}a_{n+1}\frac{x^{n}}{n!}$ . באופן דומה, אם נמצא סדרה $\{ f_n \}_{n \ge 0}$ המקיימת את הדרישה הראשונה, נוכל לקבל ע"י מתיחה סדרה המקיימת את הדרישה השנייה. אז בואו נחשב רקורסיבית את הבסיס הזה. את $f_0$ נבחר להיות הפולינום הקבוע 1.

$\Delta f_{1}(x)=f_{1}(x+1)-f_{1}(x)=f_{0}(x)=1 \implies \exists c\in F:f_{1}(x)=x+c$

נבחר $c=0$ . אפשר להמשיך בחישובים, אבל בואו נכתוב במפורש מה אנחנו מחפשים ואולי אנחנו כבר מכירים אותו:

$f_{n+1}(x+1)-f_{n+1}(x) = f_{n}(x)$

או:

$f_{n+1}(x+1) = f_{n}(x) + f_{n+1}(x)$

בשלב זה חדי העין צריכים לחשוב על משולש פסקל, שם כל איבר הוא סכום של 2 האיברים שמעליו.

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

כלומר, אנחנו יכולים לנחש שהפיתרון הוא $f_n(x) = \binom{x}{n}$ . אבל מה המשמעות של מקדם בינומי כאשר x משתנה סימבולי ואינו מספר טבעי? ניזכר בהגדרה (תלוי בגישה – יש הרואים בהגדרה הזו תוצאה) של מקדמים בינומיים:

$\binom{m}{n} = \frac{m!}{n!(m-n)!} = \frac{m(m-1)\cdots (m-(n-1))}{n!}$

כאשר m,n טבעיים וm גדול או שווה לn. אם נחליף את m בפולינום $x$ , נקבל פולינום ממעלה n:

$\binom{x}{n} = \frac{x(x-1)\cdots (x-(n-1))}{n!}$

וזאת ההגדרה הכללית ביותר של מקדם בינומי. היא צצה בעוד מקומות, לדוגמא – בטור טיילור של $(1+x)^{\alpha}$ עבור $\alpha$ שאינו בהכרח שלם. כמו מקדמים בינומים רגילים, הוא גם מקיים את נוסחת הנסיגה שלהם (ודאו!).

אז קיבלנו את בסיס ניוטון הנפלא – $f_n(x) = \binom{x}{n}$ (כן, ניוטון – הפיזיקאי ומפתח החדו"א). אם כתבתי פולינום בסיס זה: $\sum_{i=0}^{n} a_i \binom{x}{i}$ , גזירה דיסקרטית סה"כ מזיזה את המקדמים. כמו בטור טיילור.

לבסיס זה יש עוד תוכנה נפלאה: לכל x שלם, הערך של $f_n$ ב-x הוא שלם! עבור x טבעי זה נובע ישירות משלמות המקדמים הבינומים (מה שנקרא גם 'הנס של הקומבינטוריקה'), ועבור x שלילי זה נובע משיקול דומה אבל קודם צריך להביא אותו לצורה של מקדם בינומי 'סטנדרטי' (תרגיל!). שילוב של 2 תכונות אלו מאפשר לנו להוכיח בנקל הרבה טענות חזקות על פולינומים עם ערכים שלמים (לרוב, באינדוקציה על המעלה), נראה זאת כבר בסעיף הבא. נסיים בשתי נוסחאות פורמליות המסכמות את מה שעשינו עד כה – ודאו אותן:

$p(x)=\sum_{i=0}^{\infty}(\Delta^{(i)}p)(0)\binom{x}{n}$

מול

$p(x)=\sum_{i=0}^{\infty}(D^{(i)}p)(0)\frac{x^{n}}{n!}$

כאשר החזקה מסמלת: הפעלת האופרטור ( $D$ או $\Delta$ ) i פעמים על $p$ .

3. פונקציות קדומות: נניח שיש לנו פולינום $p$ , ואנחנו מחפשים לו פונקציה קדומה, כלומר פולינום $P$ כך ש- $\Delta P = p$ . האם זה תמיד אפשרי? כן, ואפשר להיווכח בכך באמצעות הבסיס שלנו: אם $p(x)=\sum_{i=0}^{n}a_{i}\binom{x}{i}$ ו $P(x) = \sum_{i=0}^{n+1} b_{i} \binom{x}{i}$ , אז תנאי הכרחי ומספיק בשביל $\Delta P = p$ (באמצעות גזירה והשוואת מקדמי איבר בסיס) הוא $b_{i+1} = a_{i}$ לכל i. האיבר החופשי $b_0$ יכול לקבל כל ערך (כמו שבחדו"א, באינטגרל לא מסויים יש דרגת חופש של קבוע $C$ ). לכן אפשר להגדיר אופרטור אינטגרציה שפשוט מזיז את המקדמים (ומקבל 0 ב $x=0$ ): $\int (\sum a_i \binom{x}{i}) = (\sum_{i \ge 1} a_{i-1} \binom{x}{i})$

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

$\sum_{i=1}^{n}i^{0}=n,\sum_{i=1}^{n}i=\frac{n(n+1)}{2}$

וחלקנו אפילו נחשפנו לסכום ריבועים:

$\sum_{i=1}^{n}i^{2}=\frac{n(n+1)(2n+1)}{6}$

נשאלת השאלה הטבעית – האם הפונקציה $S_{k}(n)=\sum_{i=1}^{n}i^{k}$ יוצאת תמיד פולינום ממעלה $k+1$ ב $n$ ? לפי האבחנה האחרונה, קיים פולינום P המקיים $P(x+1)-P(x) = x^k$ , והוא אכן ממעלה $k+1$ .. איך מוצאים אותו? כותבים את $x^k$ בבסיס המגניב שלנו (מקדמיו יסומנו $a_i$ ), ואז מזיזים את מקדמי הבסיס. איך בוחרים את האיבר החופשי $b_0$ של P? מציבים $x=0$ ומקבלים $b_0 = 0$ . פולינום זה מקיים: $S_k(n) = P(n+1)$ עבור $n$ טבעי (ודאו!).

עולה השאלה – איך כותבים את $x^k$ בבסיס הזה? זו רוטינה באלגברה לינארית. אבל בגלל הבסיס הנוח יש קיצור דרך: כמו בטורי טיילור, אם גוזרים (דיסקרטית!) את $x^k$ m פעמים ומציבים $x=0$ , נקבל את $a_m$ (ראו סוף סעיף 2). איך נראית הנגזרת הm-ית?

$\Delta^{m}f(x)=\sum_{i=0}^{m}f(x+i)\binom{m}{i}(-1)^{m-i}$

זאת מראים באמצעות אינדוקציה ישירה. מכאן נובע ש-

$a_{m} = (\Delta^{m}x^k)(0) = \sum_{i=0}^{m} i^k (-1)^{m-i} \binom{m}{i}$

באינדוקציה ישירה, וקיבלנו נוסחה מפורשת ל $S_k$ :

$S_k(n) = \sum_{i=1}^{k+1} a_{i-1} \binom{n+1}{i}$

שיגעון! נפשט עוד טיפה. בגלל ש $\binom{x+1}{n} = \binom{x}{n} + \binom{x}{n-1}$ , ומכיוון ש $a_0=0$ , נובע:

$S_k(n) = \sum_{i=1}^{k+1} (a_i + a_{i-1}) \binom{n}{i}$

אז יכלנו לסיים כאן ולהגיד שקיבלנו נוסחה ל $a_i$ . אבל מסתתרת כאן עוד מתמטיקה. לדוגמא, קיבלנו על הדרך עוד דברים מגניבים – הרי אנחנו יודעים שמעלת $x^k$ היא k, לכן בפרט $a_{k+1} = 0$ :

$a_{k+1}=\sum_{i=0}^{k+1}i^{k}\binom{k+1}{i}(-1)^{k+1-i}=0\implies\sum_{i\equiv 0(2)}i^{k}\binom{k+1}{i}=\sum_{i\equiv 1(2)}i^{k}\binom{k+1}{i}$

מה הערך של $a_{k}$ ? מתברר שהוא $k!$ :

$b_{k+1} = a_{k} = \sum_{i=0}^{k}i^{k} \binom{k}{i}(-1)^{i-k} = k!$

ולמה? אז מתברר ש $a_m$ שווה למספר הפונקציות מ $\{1,2,\cdots,k\}$ ל $\{1,2,\cdots ,m\}$ שהן על! הסימנים המתחלפים מרמזים על הכלה-הדחה, ואכן כך הדבר.

(הראו זאת! רמז: הביטוי $m^k$ סופר את כל הפונקציות מקבוצה בגודל k לקבוצה בגודל m והמקדם הבינומי סופר תתי-קבוצות בגודל m.)

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

$a_{1}=1,a_{2}=2^{k}-2,a_k = k!, a_{k-1}=\frac{k!(k-1)}{2}$

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

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

$n^k = \sum_{i=0}^{k} \binom{n}{i} \cdot \# \text{Surjective functions from set of size k to set of size i}$

אגף שמאל סופר פונקציות מ $[k]$ ל $[n]$ , אגף ימין מחלק אותן למחלקות לפי גודל התמונה שלהן – הביטוי ה $i$ מתאים לפונקציות עם תמונה בגודל $i$ . יש לנו זהות פולינומיאלית שנכונה לכל מספר טבעי, ולכן נכונה באופן פורמלי.

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

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

4. דוגמאות רציניות (ז"א, לא דוגמאות צעצוע שניתנות לפיתרון קומבינטורי):
א. פולינום המקבל ערכים שלמים: בסיס ניוטון מאפשר לנו לאפיין באופן פשוט את הפולינום המקיימים $f(\mathbb{Z})\subseteq\mathbb{Z}$ , כלומר: מעבירים מספרים שלמים למספרים שלמים. ברור שפולינומים עם מקדמים שלמים (בבסיס סטנדרטי) יקיימו זאת, אבל גם פולינומים עם מקדמים שלמים בבסיס ניוטון מקיימים זאת בגלל 'נס המקדמים הבינומים' (ולפי הדוגמא האחרונה, כל פולינום בבסיס הסטנדרטי עם מקדמים שלמים הוא צירוף עם מקדמים שלמים של פולינומים בבסיס ניוטון). אבל האם תנאי זה הכרחי? מתברר שכן, וההוכחה באינדוקציה ישירה:

נניח שהטענה נכונה לכל פולינום ממעלה עד n. יהי פולינום p ממעלה n+1 המקיים זאת. $\Delta p$ גם חייב לקיים זאת (הרי הפרש מספרים שלמים הוא שלם), ומהנחת האינדוקציה הוא קומבינציה עם מקדמים שלמים של איברי הבסיס של בסיס ניוטון. לכן p הוא מהצורה $c\binom{x}{0}+\sum_{i\ge1}a_{i-1}\binom{x}{i}$ . נציב $x=0$ ונקבל $c = p(0) \in \mathbb{Z}$ , ולכן מקדמי p שלמים גם הם, מש"ל. $\blacksquare$

אז ראינו שבסיס ניוטון בעלת תכונה מגניבה – כל פולינום המקבל מספרים שלמים כשמציבים בו מספרים שלמים, הוא קומבינציה עם מקדמים שלמים של פולינומים בבסיס ניוטון, וגם הכיוון השני נכון, כי אפילו שאיברי הבסיס אינם בעלי מקדמים שלמים בבסיס סטנדרטי (לדוגמא: $\binom{x}{2} = \frac{x^2 - x}{2}$ ), הם מקבלים ערכים שלמים כשמציבים מהם מספרים שלמים.

ב. באותו הקשר של א': נניח ויש פולינום $p$ ממעלה n המקבל ערכים שלמים בn+1 נקודות שלמות עוקבות $a, a+1, \cdots, a+n$ (בשימושים אמיתיים בדר"כ $a=0$ ). משפט: נובע שהוא מקבל תמיד ערכים שלמים בנקודות שלמות.

לפי א', משפט זה שקול לכך ש $p$ קומבינציה עם מקדמים שלמים של איברי בסיס ניוטון, אבל לא נפנה בדרך זו כעת – ראו תרגיל בסוף הפוסט. במקום זאת, נשתמש באינדוקציה על המעלה n: עבור $n=0$ זה טריוויאלי (פונקציה קבועה שמקבלת ערך שלם בנקודה כלשהי, תמיד תקבל ערך שלם). נניח שהטענה נכונה למעלה $d$ , וניקח פולינום ממעלה $d+1$ שמקיים את התנאים. אזי $\Delta p$ גם מקיים את התנאים והוא ממעלה $d$ , ומהנחת האינדוקציה הוא תמיד מקבל ערכים שלמים. כעת מספיק להראות ש $p$ מקבל ערך שלם בנקודה ספציפית, כי $\Delta p$ שלם גורר ש $p(n)-p(m)$ מספר שלם לכל $n,m$ שלמים (ודאו!). בגלל ש $p(a)$ שלם, סיימנו.

ג. התאפסות על תיבה: נתחיל בטענה פשוטה: פולינום ממעלה n לא יכול להתאפס על קבוצה מהצורה $\{ a, a+1,\cdots, a+n\}$ (הערה: פולינום האפס אינו ממעלה 0).

הוכחה: באינדוקציה ובשלילה. עבור $n=0$ זה מיידי – פולינום קבוע שאינו פולינום האפס שמתאפס בנקודה כלשהי הוא פולינום האפס, סתירה.

נניח שהטענה נכונה עבור מעלה $n$ , ונוכיח עבור $n+1$ : גזירה דיסקרטית של פולינום $p$ המקיים את התנאים נותנת לנו פולינום $\Delta p$ ממעלה $n$ שמקיים את התנאים כי הוא מתאפס על $a,a+1,\cdots ,a+n$ . לפי הנחת האינדוקציה, הוא זהותית אפס, כלומר $p$ קבוע, סתירה למעלתו החיובית $n+1$ . $\blacksquare$ .

האם אפשר להכליל את הטענה לכמה משתנים? למה לא:

יהי $g(x,y)$ פולינום ב-2 משתנים, עם מעלה שווה ל $n$ , כלומר יש מונום ב $g$ מהצורה $x^{n_{1}}y^{n_{2}}, n_{1}+n_{2}=n$ . אז $g$ לא יכול להתאפס על $\{ (a+i,b+j) | 0 \le i \le n_1, 0\le j \le n_2 \}$ (תיבה דיסקרטית שכזו). ההוכחה – באינדוקציה על n. נשתמש בעובדה ש $\{ \binom{x}{i} \binom{y}{j}, i,j\in \mathbb{N}_{0} \}$ בסיס לפולינומים ב2 משתנים. נשים לב שגזירה של $\binom{x}{i}\binom{y}{j}$ לפי x מקטינה את i ב1 וגזירה לפי y מקטינה את j ב1. לכן נגזור דיסקרטית לפי $x$ $n_1$ פעמים, ולפי $y$ $n_2$ פעמים. מקבלים פולינום קבוע שונה מאפס – הקבוע הוא המקדם של $\binom{x}{n_1} \binom{y}{n_2}$ בהצגה לפי בסיס ניוטון ב2 משתנים (שונה מאפס כי $x^{n_1} y^{n_2}$ מונום ממעלה מקסימלית בפולינום המקורי). מצד שני, הוא חייב להתאפס על $(a,b)$ (התיבה עליה הפולינום מתאפס מתקצרת באופן הדרגתי, כל גזירה: גזירה לפי $x$ מקצרת את ה'צלע' הראשונה ב1 וגזירה לפי $y$ מקצרת את ה'צלע' השנייה ב1), סתירה.

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

בכמה מישורים לכל הפחות אפשר לכסות את $\{ 0,1,\cdots, n\}^3 \setminus \{(0,0,0)\}$ בצורה כזו שהם לא עוברים דרך $(0,0,0)$ ? אפשר להגיע ל $3n$ בכמה דרכים, לדוגמא: $x+y+z=i, i \in [3n]$ . מתברר שזה המינימום: נניח בשלילה שיש כיסוי עם פחות מישורים, נסמן את המשוואות שלהם ב $h_i(x,y,z) = 0$ , כאשר $1\le i \le d <3n$ . נגדיר את הפולינום $g(x,y,z)=\prod_{i=1}^{3n}(x+y+z-i)-C\prod_{i=1}^{d} h_i(x,y,z)$ . נבחר קבוע $C$ כך ש $g$ יתאפס ב $(0,0,0)$ . לכן $g$ מתאפסת על התיבה $\{0,1,\cdots,n\}^{3}$ . מעלת $g$ היא $3n$ – ספציפית, המונום $x^{n}y^{n}z^{n}$ מופיע בה מקדם שאינו אפס. לכן $g$ לא יכול להתאפס על כזו תיבה בלי להיות פולינום האפס (כי כל 'צלע' של התיבה מכילה יותר מ $n$ מספרים עוקבים), סתירה.

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

——

כמה הערות:

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

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

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

1. א. באמצעות ספירת פונקציות, חשבו את $S_k(n)$ עבור $k$ -ים קטנים.

ב. הוכיחו שלכל $k$ , המקדם המוביל של $S_k$ הוא $\frac{1}{k}$ .

ג. הוכיחו שלכל $k$ , המקדם של $x^k$ ב $S_k$ הוא $\frac{1}{2}$ .

ד. הוכיחו שלכל $k>1$ , הפולינום $S_k$ מתחלק ב $x(x+1)$ .

2. הוכיחו שפולינום ב-n משתנים שמקבל ערכים שלמים על מספרים שלמים הוא קומבינציה לינארית עם מקדמים שלמים של $\binom{x_{1}}{i_{1}}\binom{x_{2}}{i_{1}}\cdots\binom{x_{n}}{i_{n}}$

(רמז: אינדוקציה ולגזור.)

3. א. הראו שההופכית של המטריצה $a_{ij} = \binom{i}{j}, 0\le i,j \le n$ היא $b_{ij}=(-1)^{i-j}\binom{i}{j}$ .

(רמז: $\binom{i}{k}\binom{k}{j} = \binom{i}{j}\binom{i-j}{i-k}$ .)

ב. אינטרפולציה על n+1 נקודות: נניח ונתון הערך של p – פולינום ממעלה n – על $\{ 0,1,\cdots ,n\}$ . הראו באמצעות א שמקדמי הפולינום בבסיס ניוטון הם $a_{i}=\sum_{j=0}^{i}\binom{i}{j}(-1)^{i-j}p(j)$ . תנו הוכחה חדשה למשפט הראשון בסעיף 4 בפוסט (n+1 ערכים שלמים עוקבים גורר ערכים שלמים תמיד).

ג. נתון שפולינום $p$ ממעלה d מקיים $p(i)=c^i$ עבור $0\le i \le d$ , כאשר c קבוע כלשהו. חשבו את $p(d+1)$ , ומצאו את $p$ בבסיס ניוטון.

4. מעבר בסיס בכיוון השני: הוכיחו ש $\binom{x}{n} = \frac{1}{n!} \sum_{i=0}^{n} (-1)^{n-i} \left[{n \atop i}\right] x^i$ כאשר $\left[{n \atop i}\right]$ סופר את מספר הפרמוטציות על n איברים עם i מעגלים. הסיקו את האורתוגנליות בין מספרי סטירלינג מהסוג הראשון לאלו מהסוג השני.

5. שאלה מתחרות IMC 2011: נתון פולינום ממשי f ממעלה n, כך שהמנות $\frac{f(m)-f(k)}{m-k}$ שלמות עבור $0\le k<m\le n$ . צריך להראות ש $a-b | f(a)-f(b)$ כש-a,b שלמים שונים.

(רמז: הכלילו – הראו שפולינום ב2 משתנים עם מעלה n שמקבל ערכים שלמים על הקבוצה $0\le k < m \le n+1$ , תמיד מקבל ערכים שלמים. איך מוכיחים? בגזירה.)

—————

עריכה [30.6.12]

2 תוספות קטנות:

1. שאלה 3א: אפשר להוכיח אותה באמצעות אינטרפרטציה של המטריצות $A, B$ בתור מטריצות מעבר בסיס בין $\{ x^i \}_{i \ge 0}$ ל $\{ (1+x)^i \}_{i \ge 0}$ .

2. משפט ב' בסעיף 4: אפשר להכלילו למשפט הבא: אם פולינום $p$ מרובה משתנים ממעלה $n$ הוא ממעלה $a_i$ במשתנה $x_i$ , ומקבל ערכים שלמים על הקבוצה $\prod_{i=1}^{k} [0,1,\cdots,a_i]$ (או הזזה שלמה שלו), אז הוא מקבל ערכים שלמים על כל $\mathbb{Z}^{k}$ . ההוכחה סטנדרטית (גזירה דיסקרטית), ובפוסט הבא יש שימוש יפה לתוצאה.

——–

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

ליל מנוחה

11 תגובות על אופרטור הנגזרת הדיסקרטית

פינגבאק: מנה שלמה | One and One
דורון שפריר הגיב:

11 ביולי 2012 בשעה 7:32

תודה רבה על פוסט מצוין! למדתי הרבה.

כמה הערות טכניות:
בפסקה שמתחילה ב:
"האם אפשר להכליל את הטענה לכמה משתנים? למה לא:"
לא מספיק לומר שg פולינום n ממעלה כוללת (קטנה או שוה ל-) n, אלא צריך לומר לדרוש שמעלתו ב x קטנה או שוה ל n1 וב y קטנה או שוה ל n2. מה שכתוב כרגע לא נכון, כי קיים פולינום ממעלה קטנה מ n שמתאפס על התיבה, למשל:
(x-a)(x-a-1)…(x-a-n1) ממעלה כוללת n1+1 בלבד.
גם מבחינת המימד רואים שדרגות החופש במספר מקדמי פולינום כנ"ל שוה למספר הנקודות במלבן (תיבה במקרה הכללי).

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

להגיב
- gorofir הגיב:
  
  12 ביולי 2012 בשעה 21:31
  
  לגבי ההערה השנייה עם הטווח – צודק, תיקנתי. לגבי ההערה הראשונה – אני לא בטוח שאתה צודק. לא הבנתי איפה הדוגמה שלך סותרת את הטענה שלי, או איפה ההוכחה שלי נכשלת. טיעון המימד הוא נכון אבל הוא לא דוגמה נגדית. למעשה, אני דיי משוכנע בהכללה מסיבה פשוטה – היא מקרה פרטי של משפט האפסים.
  בנוסף, יש הבדל בין שאלה 5 (שמדברת על ערכים שלמים) והפסקה שדיברת עליה (שמתייחסת לקבוצת אפסים).
  
  להגיב
פינגבאק: הקסם של הפונקציה האקספוננציאלית של ארטין-הסה (חלק 1/2) | One and One
פינגבאק: הקסם של הפונקציה האקספוננציאלית של ארטין-הסה (חלק 2/2) | One and One
פינגבאק: הקסם של הפונקציה האקספוננציאלית של ארטין-הסה (חלק 2/2) | One and One
פינגבאק: על שלוש זהויות, אינבולוציות הופכות סימן ומשפט מקמהון | One and One
פינגבאק: מי מפחד מ-n עצרת? | One and One
פינגבאק: על שלוש זהויות, אינבולוציות הופכות סימן ומשפט מקמהון | One and One
פינגבאק: הקסם של הפונקציה האקספוננציאלית של ארטין-הסה (חלק 2/2) | One and One
פינגבאק: הקסם של הפונקציה האקספוננציאלית של ארטין-הסה (חלק 1/2) | One and One