אי-שיוויון הממוצעים

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

במבוא נעשה את הדברים הבאים:

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

ובחלק של ההוכחות:

  • הוכחות, הוכחות, הוכחות (של אי-שיוויון הממוצעים) – כולל אבחנות אישיות, הכללות ותרגילים הקשורים להוכחות.
    ההוכחות ממסופרות בין 1 ל-14. מספר פעמים בחרתי לתת כמה הוכחות שחולקות את אותו רעיון, ולכן נתתי להן את אותו המספר והוספתי מספר אחרי הנקודה (לדוגמא: הוכחות 1.1 ו-1.2 משתמשות באותו רעיון). אז בפועל יש יותר מ-14 הוכחות.

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

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

חלק א' – מבוא

ממוצעים ותכונותיהם

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

אילו תכונות היינו מצפים שממוצע יקיים?

  1. שהוא ימצא בין המספר הקטן ביותר בקבוצה למספר הגדול ביותר בקבוצה. (מסקנה: אם כל המספרים שווים אז הממוצע יהיה שווה לערך המשותף שלהם.)
  2. מונוטוניות: הממוצע צריך להיות פונקציה עולה (ממש) בכל אחד מהמשתנים.
  3. סימטריות: סדר המשתנים לא צריך לשנות.
  4. רציפות בכל אחד מהמשתנים.
  5. הומוגניות: ניפוח/כיווץ המספרים (כפל בקבוע) ינפח/יכווץ את הממוצע פי אותו הקבוע. כלומר, אם אנחנו מגדילים סימולטנית את כל האיברים שלנו, הממוצע יגדל ביחד איתם באופן פרופורציוני.

בנקודה זו ארצה להעיר שתי הערות – שתיהן לא מאוד מהותיות אך מעניינות:

הערה 1: אף אחד מהתנאים הנ"ל לא באמת חקוק בסלע. לדוגמא, יש ממוצעים שלא מקיימים הומוגניות, כמו "ממוצעים קווזי-אריתמטים": Mean_{f}(x_{1},\cdots,x_{n})=f^{-1}(\frac{1}{n}\sum_{i=1}^{n}f(x_{i})), כאשר f פונקציה רציפה וחח"ע מהמספרים האי-שליליים לעצמם. יש דרך לתקן את ההומוגניות, כמו לנרמל את המספרים ע"י ממוצע הומוגני M', אבל אז התוצאה המתקבלת היא לאו דווקא ממוצע שמקיים את דרישת המונוטוניות:

Mean_{f,M'}(x_{1},\cdots,x_{n})=M'(x_{1},\cdots,x_{n})\cdot f^{-1}(\frac{1}{n}\sum_{i=1}^{n}f(\frac{x_{i}}{M'(x_{1},\cdots,x_{n})}))

הערה 2: אם נוסיף את הדרישה (המעט מלאכותית) שהממוצע של n מספרים (n – קבוע) יהיה פולינום, אז מהמשפט היסודי של הפולינומים הסימטרים, נקבל שהממוצע הוא מהצורה Mean(x_1, \cdots, x_n) = C \sum_{i=1}^{n} x_i , כאשר C קבוע (כי \sum x_i הוא הפולינום הסימטרי האלמנטרי היחיד ממעלה 1). מתנאי 1 נקבל שC=\frac{1}{n}.

ממוצע אריתמטי, גיאומטרי והרמוני, וניסוח אי-שיוויון הממוצעים

מה הוא ממוצע ארימתטי (או: חשבוני)? הממוצע האריתמטי של מספרים a_1, \cdots, a_n הוא סכומם מחולק בכמות שלהם: A = \frac{\sum a_i}{n} (מעתה והלאה הוא יסומן באות A – קיצור של Arithmetic). קל לראות שהוא מקיים את התכונות שציינו. בדר"כ כאשר מדברים על ממוצע, מתכוונים לממוצע זה. עוד דרך להסתכל עליו היא כסכימת כל המספרים בקבוצה, כאשר כל מספר מוכפל במשקולת \frac{1}{n}.

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

אבל יש עוד ממוצעים:

ממוצע גיאומטרי (או: הנדסי) – הוא מוגדר בעזרת מכפלה במקום סכום. הוא קצת יותר מוגבל מממוצע אריתמטי כי הוא מוגדר רק עבור מספרים אי-שליליים. הממוצע הגיאומטרי של המספרים a_1, \cdots, a_n \ge 0 מוגדר כשורש הn-י של המכפלה שלהם , כלומר: G = (a_1 \cdot \cdots \cdot a_n)^\frac{1}{n} (G – מ-Geometric). שוב, קל לראות שמתקיימות התכונות שדרשנו.

דוגמה הממחישה ממוצע גיאומטרי: נניח ויש לנו סכום כסף, לצורך העניין שקל חדש, שתופח כל חודש באחוז כלשהו, נניח שבחודש הi-י (1 \le i \le 12) הוא תופח פי a_i. אם השקל היה תופח כל חודש פי G, הממוצע הגיאומטרי של a_i-ים, הוא היה מקבל בסוף השנה אותו ערך כמו במציאות.

כעת אנחנו מוכנים לחשוף ולהבין מה הוא אותו אי-שיוויון המצויין בכותרת, "אי-שיוויון הממוצעים":

A \ge G

ממוצע אריתמטי גדול/שווה ממוצע גיאומטרי! ושיוויון מתקיים אם ורק אם כל המספרים שווים זה לזה (ואז 2 הממוצעים שווים לערך משותף זה).

ממוצע נפוץ נוסף הוא ממוצע הרמוני (Harmonic), המוגדר באמצעות ההופכיים של המספרים:

H = \frac{n}{\frac{1}{a_1} + \cdots + \frac{1}{a_n} }

תרגיל: הראו שA \ge G גורר, ואף שקול, ל-G \ge H (רמז: הסתכלו על H^{-1} מול G^{-1}). אי-השיוויון A \ge G \ge H הוא עוד גרסה נפוצה של אי-שיוויון הממוצעים.

המקרה n=2

המקרה n=1 טריוויאלי, לכן נתרכז בn=2. מקרה זה אפשר להוכיח אלגברית באופן ישיר: \frac{a+b}{2} \ge \sqrt{ab} שקול ל(\sqrt{a}-\sqrt{b})^{2}\ge0.

תרגיל: הוכיחו ישירות גם עבור n=3,4.

עבור n=2 אפשר לתת פירוש של הממוצעים בשפה של גיאומטריה אוקלידית (מבוסס על המאמר הזה): נניח a=x_{1} > x_{2}=b, בלי הגבלת הכלליות. נשרטט מעגל בקוטר a-b עם מרכז A. נבחר 2 נקודות שיגדירו קוטר, P וQ.

נסתכל על הקרן שמתחילה בP ועוברת דרך Q. נבחר עליה נקודה M המקיימת MP=a. היא מקיימת בנוסף MQ=b.

נעביר משיק מ-M למעגל, ונסמן את נקדת ההשקה בG (יש 2 דרכים לעשות זאת). נעביר אנך מ-G לקוטר PQ, שחותך אותו בH.

שרטוט שמכיל את שלושת הממוצעים החשובים עבור 2 מספרים.

עכשיו אבחנות:
1. AG באורך \frac{a-b}{2} (רדיוס המעגל).

2. AM באורך AQ+QM=\frac{a-b}{2}+b=\frac{a+b}{2}.

3. \bigtriangleup MGA משולש ישר זווית (כי MG משיק למעגל וA המרכז) ומשפט פיתגורס נותן:

GM=\sqrt{AM^{2}-AG^{2}}=\sqrt{\frac{a^{2}+2ab+b^{2}-(a^{2}-2ab+b^{2})}{4}}=\sqrt{ab}

4. \bigtriangleup GHM דומה ל\bigtriangleup AGM, לכן \frac{GM}{AM}=\frac{HM}{GM}, כלומר:

HM=\frac{GM^{2}}{AM}=\frac{2ab}{a+b}=\frac{2}{\frac{1}{a}+\frac{1}{b}}

אי-שיוויון הממוצעים A \ge G \ge H הופך לAM\ge GM\ge HM. אי-השיוויון AM > GM מתקיים כי AM הוא היתר וGM הוא ניצב (במשולש \bigtriangleup AMG). החלק GM > HM נובע מאותה סיבה אבל במשולש \bigtriangleup HMG.

אינטואיציה ודרכי הסתכלות שונות

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

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

  1. אפשר להסתכל על הבעיה כבעיית אופטימיזציה (ספציפית, בעיית מינימיזציה): אנחנו רוצים למזער את הפונקציה a_1 + \cdots + a_n בהינתן G, כלומר בהינתן המכפלה a_1 \cdot \cdots \cdot a_n. למעשה, מהומוגניות של הממוצעים, אפשר להניח שהמכפלה היא 1 ולהוכיח שהערך המינימלי של הסכום הוא n.
  2. לחילופין, אפשר למקסם את G בהינתן A, כלומר את המכפלה a_1 \cdot \cdots \cdot a_n בהינתן הסכום a_{1}+\cdots+a_{n}=nA (המקסימום יוצא A.)
  3. אפשר לתת פירוש גיאומטרי לגדלים: בהינתן a_1, \cdots, a_n חיוביים, נסתכל על תיבה n-מימדית עם צלעות באורכים a_i, כלומר על התיבה \prod_{i=1}^{n} [0,a_i]. סכום הצלעות היוצאות מקודקוד ספציפי הוא nA (וההיקף, כלומר סכום הצלעות, פרופורציוני לסכום זה: 2^{n-1}nA) והשטח G^n. אי-שיוויון הממוצעים אומר שסכום הצלעות היוצאות מקודקוד גדול/שווה nG, כלומר אם השטח קבוע (ז"א G קבוע), ההיקף מינימלי כאשר הa_i שווים, כלומר לקוביה n-מימדית יש היקף מינימלי מבין התיבות עם שטח כמו שלה. זה סוג של אי-שיוויון איזופרימטרי.

שימושים

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

1. המרת מכפלה בסכום – השימוש העיקרי של אי-השיוויון הוא להמיר מכפלה בסכום, ולהיפך. לדוגמא, כשמחשבים גודל כלשהו וחוסמים אותו מלמטה ע"י סכום שלא ברור תמיד איך הוא מתנהג, אפשר להחליף את הסכום \sum_{i=1}^{n} \text{size}_{i} בn\prod_{i=1}^{n} \text{size}_{i}^{\frac{1}{n}} ולפעמים זה נוח יותר להבנה, כי זה ביטוי בודד. (לפעמים צריך להתחכם קצת בשימוש ולא להפעיל אותו ישר – צריך להבין את היחס בין האיברים השונים בסכום.) סכום כזה יכול לצוץ בחישוב קומבינטורי או בחישובי סיבוכיות.

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

נניח ש-x,y מספרים ממשיים אי-שליליים המקיימים x^3 + y^3 = 1. מצאו את הערך המקסימלי של \sqrt{x} + 2\sqrt{y}.

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

x^3 + 5\alpha = x^3 +\underbrace{\alpha + \cdots + \alpha}_{\text{5 times}} \ge 6\sqrt{x} \alpha^{\frac{5}{6}}

y^3 + 5\beta = y^3 + \underbrace{\beta + \cdots + \beta}_{\text{5 times}} \ge 6\sqrt{y} \beta^{\frac{5}{6}}

כאשר המעבר האחרון בכל אי-שיוויון נובע מאי-שיוויון הממוצעים (שיוויון כאשר x^{3}=\alpha,y^{3}=\beta).
אם נסכום את 2 התוצאות האלו נקבל x^{3}+y^{3}+5(\alpha+\beta)\ge6(\alpha^{\frac{5}{6}}\sqrt{x}+\beta^{\frac{5}{6}}\sqrt{y}), כלומר, בעזרת השימוש בנתון x^3 + y^3 = 1:

\alpha^{\frac{5}{6}}\sqrt{x}+\beta^{\frac{5}{6}}\sqrt{y}\le\frac{1+5(\alpha+\beta)}{6}

כדי להיות מסוגלים לחסום מלמעלה את \sqrt{x} +2\sqrt{y} נדרוש שהפרופורציה בין \alpha^{5/6} ל-\beta^{5/6} תהיה 1 ל-2, כלומר \beta=\alpha\cdot 2^{\frac{6}{5}}, וכדי ששני אי-השיוויונים המקוריים יהיו הדוקים, נדרוש x^{3}=\alpha,y^{3}=\beta, כלומר \alpha + \beta = 1. פותרים את המערכת ומקבלים \alpha=(1+2^{\frac{6}{5}})^{-1}. מכאן:

\sqrt{x}+2\sqrt{y}\le\frac{1+5(\alpha+\beta)}{6\alpha^{\frac{5}{6}}}=\alpha^{-\frac{5}{6}}=(1+2^{\frac{6}{5}})^{\frac{5}{6}}

שיוויון מתקבל כאשר x=\alpha^{1/3},y=\beta^{1/3}.\blacksquare

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

קמירות

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

הגדרה: קבוצה קמורה ב-\mathbb{R}^{n} היא קבוצה שסגורה להעברת קטעים, כלומר: אם אני אקח שתי  נקודות בה, אז כל הנקודות על הקטע המחבר אותן יהיו גם בקבוצה. פורמלית, A קמורה אם a,b \in A גורר ש-\forall t \in [0,1] : ta+(1-t)b\in A.

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

הכירו את כוכב הים, צורה לא קמורה.

תרגיל: הוכיחו שאם a_1, \cdots, a_n \in A ו-A קמורה אז: \sum_{i=1}^{n} p_i a_i \in A לכל \{ p_i \}_{i=1}^{n} אי-שליליים המסתכמים ל-1. צירוף כזה נקרא "צירוף קמור".

הגדרה: פונקציה f: I \to \mathbb{R}, כאשר I קטע (סופי או אינסופי), נקראת קמורה אם השטח שמעל הגרף שלה, כולל הגרף עצמו, הוא קבוצה קמורה. הכוונה היא לקבוצה Epigraph(f) = \{ (x,y) | x \in I, y \ge f(y) \}.

ניתן לפשט ולקבל שתנאי הזה שקול לתנאי הגיאומטרי הבאה: עבור x,y \in I, הקטע המחבר את (x,f(x)) עם (y,f(y)) נמצא מעל הגרף או נחתך איתו, כלומר הנקודה (tx+(1-t)y,tf(x)+(1-t)f(y)) נמצאת מעל (tx+(1-t)y,f(tx+(1-t)y) (או מתלכדת איתה) כאשר t \in [0,1], מה שהופך ל:

\forall x,y \in I,t \in [0,1] : tf(x)+(1-t)f(y)\ge f(tx+(1-t)y)

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

  • "פרבולה מחייכת" מימי התיכון – f(x)=ax^2+bx+c עם a>0
  • הפונקציה האקספוננציאלית f(x)=e^x
  • סינוס וקוסינוס אינן פונקציות קמורות.

הגדרה: פונקציה f נקראת קעורה אם המינוס שלה, -f, היא פונקציה קמורה.

אחרי הגדרות ודוגמאות, הגיע זמן טוב לניסוי. ניקח נקודות a<b<c \in I. את b אפשר לכתוב כצירוף קמור של a, c באופן הבא: b=\frac{c-b}{c-a}a+\frac{b-a}{c-a}c. הקמירות של f נותנת:

\frac{c-b}{c-a}f(a)+\frac{b-a}{c-a}f(c)\ge f(b)\implies(c-b)f(a)+(b-a)f(c)\ge(c-a)f(b)

אפשר לשכתב אי-שיוויון זה בתור (c-a)(f(c)-f(b))\ge(c-b)(f(c)-f(a)) וגם בתור (b-a)(f(c)-f(a))\ge(c-a)(f(b)-f(a)), מה שנותן את הלמה הבאה:

למת המיתרים: \forall a<b<c\in I:\frac{f(c)-f(b)}{c-b}\ge\frac{f(c)-f(a)}{c-a}\ge\frac{f(b)-f(a)}{b-a}

מאין השם? slope(x,y)=\frac{f(x)-f(y)}{x-y} מודדת את שיפוע המיתר המחבר את (x,f(x)) עם (y,f(y)). למת המיתרים שקולה לכך שהפונקציה slope מונוטונית עולה בכל אחד מהמשתנים שלה.

דוגמא לפונקציה קמורה – המיתר נמצא מעל הגרף

תרגיל: הראו שלמת המיתרים שקולה לקמירות.

תרגיל: הוכיחו באופן גיאומטרי את למת המיתרים.

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

  1. נגזרת עולה: אם x,y \in I ו-h מספיק קטן, אז x,x+h < y, y+h, ולכן \frac{f(x+h)-f(x)}{h}\le \frac{f(y+h)-f(y)}{h}.
    במידה ו-f גזירה, אז כשנשאיף את h לאפס נקבל f'(y) \ge f'(x), כלומר f' עולה.
    אם f גזירה פעמיים, זה גורר שf'' \ge 0.
    תרגיל: הראו שפונקציה גזירה פעמיים היא קמורה אמ"מ f'' \ge 0.
  2. תחומי עליה/ירידה: פונקציה קמורה בקטע I יכולה להיות או מונוטונית עליו, או לרדת עד נקודת קיצון גלובאלית ואז להתחיל לעלות.
    אם f גזירה, זה פשוט נובע מכך שf' מונוטונית עולה (מסקנה 1). עם זאת, זה נכון גם כאשר f אינה גזירה – אשאיר זאת כתרגיל לכם.
  3. נקודות מינימום: באופן כללי, פונקציה בקטע סופי מקבלת בו מינימום גלובאלי בקצוות או בנקודה קריטית בפנים הקטע. ממסקנה 2 נובע שעבור פונקציה קמורה אין מינימום מקומי שאינו גלובאלי!
    אם הפונקציה גזירה, אנחנו בעצם מקבלים שיש לכל היותר נקודה קריטית אחת.
    זה מפשט חקר נקודות קיצון של פונקציות קמורות באופן משמעותי.
  4. קמורה חסומה מלמטה ע"י המשיקים: מלמת המיתרים, \frac{f(x+h)-f(x) }{h} מונוטונית עולה בh. בפרט, עבור h> 0, אם f גזירה בx נקבל: f'(x) \le \frac{f(x+h)-f(x)}{h}. אם h שלילי, הכיוון מתהפך. אפשר לסכם זאת בf(x+h) \ge hf'(x) + f(x) לכל h. אפשר לנסוח זאת אחרת: f חסומה מלמטה ע"י המשיק בx.
  5. אם f קמורה, מתקיים ש-g(x)=f(x+c)-f(x) פונקציה עולה עבור c חיובי. נוכיח זאת בהמשך מלמת המיתרים, מוזמנים לנסות להוכיח כבר עכשיו.

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

תרגיל: הוכיחו שאם \frac{f(x) + f(y) }{2} \ge f(\frac{x+y}{2}) לכל x,y \in I ו-f רציפה, אז f קמורה. (הערה: מסתבר שלא צריך רציפות – מספיק מדידות לבג!)

חלק ב' – הוכחות

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

הוכחה 1.1 (Crawford) – עיקרון ההחלקה

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

נסתכל על הבעיה כבעיית מקסימיזציה: \frac{1}{n} \sum_{i=1}^{n} a_i = A נתון, ואנחנו רוצים להוכיח שתמיד (\prod_{i=1}^{n}a_{i})^{1/n}\le\frac{1}{n}\sum_{i=1}^{n}a_{i}=A, כלומר \prod_{i=1}^{n}a_{i}\le A^{n}.

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

a'_{1}=A,a'_{2}=a_{1}+a_{2}-A

בכך לא שיניתי את הסכום, והמכפלה גדלה:

a'_{1}a'_{2}=A(a_{1}+a_{2}-A)>a_{1}a_{2}\leftrightarrow(A-a_{1})(A-a_{2})<0\leftrightarrow A-a_{1},a_{2}-A\text{ have the same sign}

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

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

אני טוען שכבר כאן יש קמירות: נסמן f(x) = -\ln x. השתמשנו בכך ש-f(A)+f(a_{1}+a_{2}-A)<f(a_{1})+f(a_{2}). מסתבר שזה נכון לכל פונקציה קמורה (ואכן f קמורה: f''(x) = x^{-2} > 0). איך מראים זאת? נסמן c= A - a_1 > 0, ונגדיר g(x) = f(x) - f(x-c). g עולה: אם y \ge x, מתקיים מלמת המיתרים –

g(x) = \text{slope}(x-c,x) \le \text{slope}(x-c, y) \le \text{slope}(y-c, y) =g(y)

ולכן g(A) \le g(a_2), וזה שקול למה שרצינו להראות.

בעצם, ממש קל להגיע מכאן לאי-שיוויון Jensen: \frac{\sum_{i=1}^{n} f(a_i)}{n} \ge f(\frac{\sum_{i=1}^{n} a_i}{n}) כאשר f קמורה. נקבע את הממוצע: \frac{1}{n}\sum a_{i}=A. אנחנו רוצים להראות שתחת אילוץ זה, \sum f(x)\ge nf(A). איך מראים זאת? כמו מקודם – אם כל הa_i שווים, סיימנו (כי הם שווים לA). אחרת, בה"כ a_1 < A <a_2. אפשר להחליף אותם בa_1 + a_2 - A, A, ורק נקטין את הסכום: f(a_1) + f(a_2) \ge f(A) + f(a_1+a_2 - A). בסופו של דבר מקבלים ש\sum f(a_i)\ge\sum f(A)=nf(A), מש"ל.

תרגיל: הוכיחו את אי-שיוויון Jensen באמצעות התרגיל הראשון בפרק על קמירות.
תרגיל (Ehlers): מצאו הוכחה אנלוגית במקרה בו מקבעים את המכפלה להיות בה"כ 1, וממזערים את \sum_{i=1}^{n}a_{i}.
תרגיל: הראו שפונקציה היא קמורה אמ"מ ההופכית שלה קעורה.

הוכחה 1.2 (Maclaurin)

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

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

כעת ניקח את המספרים שממקסמים את הממוצע הגיאומטרי: a_1, \cdots ,a_n.  אם הם לא כולם שווים, אפשר לבצע את החילוף שלנו ולקבל ממוצע גיאומטרי גדול יותר, סתירה. לכן המקסימום מתקבל כאשר כל המספרים שווים. \blacksquare

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

כרגיל, אפשר להכליל את ההוכחה כדי לקבל את אי-שיוויון ינסן. צעד החילוף נראה שם כך: מחליפים את f(m) + f(M) ב-2f(\frac{m+M}{2}), כאשר f פונקציה קמורה (אי-שיוויון הממוצעים מתאים ל-f(x) = -\ln x). העובדה שהצעד הזה "משפר" נובעת ישירות מההגדרה של קמירות ולא עוברת דרך למת המיתרים, ולכן אני מחבב הוכחה זו במיוחד.

הוכחה 1.3 – דיסקרטזיציה של עיקרון ההחלקה

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

( \frac{a_1 + \cdots + a_n}{n} )^n \ge a_1 a_2 \cdots a_n

שוב מהומוגניות, אפשר להניח שכל המספרים מתחלקים ב-n (באמצעות הכפלת הכל ב-n), ובפרט – סכומם הוא כפולה של n, נניח: a_1 + a_2 + \cdots + a_n = nm.
צריך להסביר למה a_1 a_2 \cdots a_n \le m^n כאשר a_1 + a_2 + \cdots + a_n = nm.

נפרק ל-3 מקרים:

1. אם המספר המקסימלי שווה למינימלי, סיימנו – כי כל המספרים שווים ל-m ויש שיוויון.

2. אם המקסימלי שווה למינימלי ועוד 1, זה אומר שיש לנו 1\le i < n פעמים מספר כלשהו a ושאר הn-i פעמים את המספר a+1. כדי שהסכום יהיה nm צריך להתקיים:

ia + (n-i)(a+1) = nm

מודולו n מקבלים ש-i מתחלק ב-n, סתירה.

3. (המקרה המעניין היחיד) אחרת, המקסימלי גדול מהמינימלי לפחות ב-2. נחליף את המקסימלי והמינימלי בשני מספרים אחרים – אם a_n הוא מקסימלי ו-a_1 מינימלי, נחליף אותם בa_n - 1, a_1 +1. בכך לא שינינו את סכומם, אבל המכפלה גדלה:

(a_1 + 1)(a_n - 1) > a_1 a_n \leftrightarrow a_n > a_1 + 1

אחרי החילוף, או שסיימנו (מקרה 1) או שצריך לעשות שוב חילוף (מקרה 3). נמשיך כל עוד נוכל. התהליך חייב להסתיים כי הוא מגדיל את המכפלה ויש מספר סופי של אפשרויות לה (כי יש מספר סופי של פתרונות בשלמים אי-שליליים ל-\sum a_i = nm). כשהוא מסתיים, בהכרח כל המספרים שווים ואי-השיוויון מתקיים (עם שיוויון…). \blacksquare

ההוכחה הזו יפה כי היא מאוד אלמנטרית. יש המנסחים הוכחה זו בצורה קומבינטורית, בכך שהם מוכיחים שהאלגוריתם במקרה 3 עובד באמצעות הדגמה 'סיפורית' לכך ש-(a+1)(b-1) > ab כאשר b>a.

הוכחה 2 (קושי) – אינדוקציה הפוכה

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

קודם, נוודא עבור n=1,2: עבור n=1 הטענה שקולה לכך ש-a \ge a, ויש שיוויון כאשר a =a.

עבור n=2 הטענה שקולה ל-\frac{a+b}{2}\ge\sqrt{ab}, או: (\sqrt{a}-\sqrt{b})^{2}\ge 0, ואנחנו מקבלים את מקרה השיוויון מתנה (שיוויון אמ"מ a=b).

כעת נוכיח 2 אבחנות קריטיות. אומנם לא פשוט להראות שאם הטענה נכונה ל-n משתנים אז היא נכונה ל-n+1 משתנים, אבל קל להראות את 2 הטענות הבאות:

א. אם אי-השיוויון נכון ל-n משתנים, אז הוא נכון ל-2n משתנים:

\frac{a_{1}+\cdots+a_{2n}}{2n}=\frac{\frac{1}{n}(a_{1}+\cdots+a_{n})+\frac{1}{n}(a_{n+1}+\cdots+a_{2n})}{2}\ge\frac{(a_{1}\cdots a_{n})^{1/n}+(a_{n+1}\cdots a_{2n})^{1/n}}{2}\ge(a_{1}\cdots a_{2n})^{1/2n}

ב. אם הטענה נכונה ל-n+1 \ge 2 משתנים, אז היא נכונה גם לn משתנים ("אינדוקציה הפוכה"): נציב באי-השיווויון עבור n+1 משתנים את x_{1},\cdots,x_{n},A=\frac{x_{1}+\cdots+x_{n}}{n}. חישוב פשוט נותן את התוצאה הדרושה.

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

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

הוכחה 3 – רדוקציה למקרה שכל המשתנים, חוץ מאחד, שווים זה לזה

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

נניח שיש n>1 מספרים, מתוכם n-1 שווים ל-a ויוצא הדופן הוא b. אי-שיוויון הממוצעים נהפך ל:

\frac{a(n-1) + b}{n} \ge \sqrt[n]{a^{n-1}b}

לאחר העלאה בחזקת n וחלוקה ב-a^n, מקבלים את הצורה השקולה הבאה:

(1+x)^n \ge 1+nx עבור x =\frac{b-a}{na} \ge \frac{-1}{n} > -1

זה אי-שיוויון ברנולי, שגרסתו המלאה היא מעט כללית יותר:

(1+x)^{r}\ge1+rx אם r \notin (0,1) ו-x> - 1

לא נתעסק בגרסה הזו, נישאר עם n טבעי. המקרה שלנו נובע מקמירות, אלא מה: נסתכל על f(x) = (1+x)^n - (1+nx). אם גוזרים פעמיים רואים ש-f קמורה בתחום x \ge -1. יש נקודת קיצון ב-x=0 והיא מינימום גלובאלי (קל לראות שהמינימום לא מתקבל בקצוות), שם f(0) = 0, וקיבלנו f(x) \ge 0, מש"ל. \blacksquare

תרגיל: הראו את אי-שיוויון ברנולי המלא.

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

A_n = \frac{(n-1)A_{n-1} + a_n}{n} \ge A_{n-1}^{\frac{n-1}{n}} a_{n}^{1/n}

נוכיח להעלות בחזקת n ולקבל A_{n}^{n}\ge A_{n-1}^{n-1}a_{n}. מפעילים זאת n פעמים ומקבלים:

A_n^{n}\ge a_{1}a_{2}\cdots a_{n}=G_n^{n}

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

(\frac{A_{n}}{G_{n}})^{n}\ge(\frac{A_{n-1}}{G_{n-1}})^{n-1}\ge\cdots\ge (\frac{A_1}{G_1})^1 = \frac{a_1}{a_1}=1

רדוקציה שנייה: שוב נביע רקורסיבית את A_n כפונקציה של A_{n-1} (ומשתנים נוספים). נסמן ב-G_i את הממוצע הגיאומטרי של i המספרים הראשונים. נשתמש בזהות הבאה:

A_{n}=\frac{G_{n-1}}{n}[(n-1)\frac{A_{n-1}}{G_{n-1}}+(G_{n}/G_{n-1})^{n}]

על הביטוי בחזקת n באגף ימין אפשר להפעיל את אי-שיוויון ברנולי, עם x = \frac{G_n - G_{n-1}}{G_{n-1}}, ולקבל לאחר פישוט מסויים: A_{n}\ge G_{n}+\frac{n-1}{n}(A_{n-1}-G_{n-1}), כלומר A_{n}-G_{n}\ge\frac{n-1}{n}(A_{n-1}-G_{n-1}). נחזור על התליך זה n-1 פעמים עד שנקבל את המקרה n=1 הטריוויאלי.

שוב קיבלנו סדרת אי-שיוויונות שמוליכה הדרגתית מהאריתמטי לגיאומטרי:

n(A_{n}-G_{n})\ge(n-1)(A_{n-1}-G_{n-1}) \ge \cdots \ge0

רדוקציה שלישית:  ראינו כבר שאי-שיוויון הממוצעים שקול לבעיית אופטימיזציה: אנחנו רוצים למקסם מכפלה a_1 \cdot a_2 \cdot \cdots \cdot a_n = 1, בהינתן שסכום המשתנים (החיוביים) שווה ל-a. כלומר אנחנו מנסים לחשב את הפונקציה הבאה:

f_n(a) = \max_{a_{1} + \cdots + a_n = a} a_1 \cdots a_n

מההגדרה אפשר לבטא את f_n באמצעות מקסימום ו-f_{n-1}:

f_n(a) = \max_{x<a} xf_{n-1}(a-x)

אי-שיוויון הממוצעים שקול לכך שהמקסימום מתקבל כשהמספרים שווים, כלומר f_n(a) = (\frac{a}{n})^n. באמצעות הקשר בין f_{n-1} ל-f_n וההומוגניות של f_n (f_n(t) = t^n f(1)), אפשר להראות זאת באינדוקציה:

f_n(1) = \max_{x \le 1} xf_{n-1}(1-x) = f_{n-1}(1) \max_{x \le 1} x(1-x)^{n-1}

לאחר שנוכיח שהמקסימום של g_n(x)=x(1-x)^{n-1} בקטע [0,1] הוא \frac{(n-1)^{n-1}}{n^n}, נקבל מכפלה טלסקופית שנותנת לבסוף:

f_n(1) = f_{n-1}(1) \frac{(n-1)^{n-1}}{n^n} = f_{n-2}(1) \frac{(n-2)^{n-2}}{(n-1)^{n-1}}\frac{(n-1)^{n-1}}{n^n} = \cdots = f_n(1) \frac{1^1}{2^2} \frac{2^2}{3^3} \cdots \frac{(n-1)^{n-1}}{n^n} =n^{-n}

\implies f_n(a) = (\frac{a}{n})^n

אפשר לחסום את g_n בעזרת המקרה המנוון שהוכחנו:

g_n(x) = \frac{1}{n-1} ( (n-1)x \cdot \underbrace{ (1-x) \cdots (1-x) }_{(n-1) \text{ times}} ) \le \frac{1}{n-1} (\frac{ (n-1)x + (n-1) \cdot (1-x) }{n})^n = \frac{(n-1)^{n-1}}{n^n}

וסיימנו. \blacksquare

תרגיל: הוכיחו את אי-שיוויון ינסן עם רעיון דומה (רדוקציה למקרה המנוון).

הוכחה 4 – חקירה של פונקציה במשתנה אחד

נניח ש-a_1, \cdots ,a_{n+1} הם n+1 מספרים אי-שליליים. נסמן ב- A_i, G_i את הממוצעים האריתמטי והגיאומטרי של a_1, \cdots, a_i.

נראה מה קורה אם לא מקבעים את a_{n+1}:

f(t)=\frac{a_{1}+\cdots+a_{n}+t}{n+1}-\sqrt[n+1]{a_{1}\cdots a_{n}t} = A_{n+1}-G_{n+1}

אנחנו רוצים להראות ש-f(t) \ge 0. נגזור: f'(t)=\frac{1}{n+1}(1-(G_n/t)^{n/n+1}), ונשים לב שהנגזרת מתאפסת ב-G_n. חישוב נוסף מראה שהנגזרת השנייה אי-שלילית (במילים אחרות, הפונקציה קמורה). לכן מקבלים מינימום גלובאלי ב-G_n, כלומר f(t) \ge f(G_n). המינימום הוא \frac{n}{n+1} (A_n - G_n). באינדוקציה מקבלים את האי-שליליות הרצויה, ובפרט שוב קיבלנו את אי-השיוויון הבא:

A_{n}-G_{n} \ge (\frac{n-1}{n})(A_{n-1}-G_{n-1})

תרגיל (Liouville): ליוביל חקר פונקציה דומה – את f(t)=(\frac{a_{1}+\cdots+a_{n}+t}{n+1})^{n+1}-a_{1}\cdots a_{n}t = A_{n+1}^{n+1}-G_{n+1}^{n+1}. אנחנו רוצים להראות שהיא אי-שלילית.
הראו שהיא קמורה ומקבלת מינימום (גלובאלי) ב-(n+1)G_n - nA_n. מציבים ומקבלים שהמינימום הוא n(A_n-G_n)G_n^n. הראו באינדוקציה שהמינימום אכן אי-שלילי.

הוכחה 5.1 – החלום של Pólya

ההוכחה הבאה הגיע לפוליה בחלומו.
נשתמש באי-שיוויון העזר הפשוט הבא: e^x \ge x+1. הוא מתקיים כי e^x קמורה ובפרט נמצאת מעל המשיק שלה בx=0. נניח שהמספרים שלנו הם כרגיל a_1, \cdots, a_n עם ממוצעים A,G.

נציב x = \frac{a_i}{A} - 1 ונקבל:

\forall 1 \le i \le n: e^{\frac{a_{i}}{A}-1}\ge\frac{a_{i}}{A}

נשים לב ש-\sum\frac{a_{i}}{A}=n. נכפיל את n אי-השיוויונים ונקבל:

e^0 \ge \frac{G^n}{A^n}

כלומר A\ge G! שיוויון מתקיים בבירור כאשר כל הa_i-ים שווים. \blacksquare

על פניו – קסום. השתמשנו באי-שיוויון פשוט ואינטואיטיבי  – קמירות ב-x=0 -ותו לא. יש כמה הסברים לקסם זה:

א. הקמירות של e^x ב-x=0 גוררת קמירות בכל נקודה, בגלל "הדימיון העצמי" של e^x (שם מפוצץ לתכונה e^{x+c} = e^{x}e^{c}).
קמירות שקולה לכל שבכל a \in \mathbb{R} מתקיים שe^x גדול/שווה למשיק ב-a, ובמפורש: e^{x}\ge e^{a}(x-a+1). כשנחלק בe^a נקבל e^{x-a} \ge x-a+1, וזה אי-שיוויון שנובע מהקמירות ב-x=0, כמובטח.

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

הוכחה 5.2 – אי-שיוויון ינסן בעזרת משיקים

תהי f פונקציה קמורה. נניח שהיא גזירה, אם כי זה לא הכרחי אלא רק מפשט. זה גורר f(x) \ge f'(a)(x-a)+f(a) לכל a,x בתחום הפונקציה. נבחר a = A, הממוצע האריתמטי של המספרים שלנו. נקבל:

\frac{1}{n}\sum f(a_{i})\ge\frac{1}{n}\sum(f'(A)(a_{i}-A)+f(A))=f(A)+\frac{f'(A)}{n}\sum(a_{i}-A)=f(A)

זה משלים את ההוכחה של אי-שיוויון ינסן. בשביל לקבל את אי-שיוויון הממוצעים, נבחר f(x) = -\ln x. \blacksquare

תרגיל: הראו שלא צריך גזירות.
תרגיל: הכלילו לאי-שיוויון ינסן עם הסתברויות: \sum p_i f(a_i) \ge f(\sum p_i a_i) כאשר p_i הסתברויות המסתכמות ל-1..

הוכחה 6 – סכום מינימומים, מינימום של סכום

ההוכחה מבוססת על רעיון אלגנטי ממאמר רוסי מהמגזין Kvant.
הרעיון הוא זה: נניח ויש לי פונקציות רציפות f_1, \cdots, f_n, המוגדרות על קבוצה I. אז:

\min_{x \in I} \sum_{i=1}^{n} f_i(x) \ge \sum_{i=1}^{n} \min_{x\in I} f_i(x)

ובמילים: סכום המינימומים קטן/שווה ממינימום הסכום (בהנחה שהמינימום קיים וכו'). הטענה הזו אינטואיטיבית – משתלם יותר למזער כל פונקציה בנפרד מאשר את הסכום: נניח שהסכום של הפונקציות מקבל מינימום בנקודה m, אז \min\sum f_{i}(x)=\sum f_{i}(m)\ge\sum\min f_{i}(x).

אפשר לעשות עם העיקרון הפשוט הזה דברים מדהימים. נדגים איך מוכיחים בעזרתו את אי-שיוויון הממוצעים:
נגדיר את הפונקציה (הקמורה!) f_{a,b}(x)=ae^{x}-b(x+1). המינימום של f_{a,b}, כאשר a,b>0, מתקבל ב-x=\ln\frac{b}{a}, והוא -b\ln\frac{b}{a}. נפעיל את העיקרון שלנו ונקבל:

\sum-b_{i}\ln\frac{b_{i}}{a_{i}}\le\min f_{\sum a_{i},\sum b_{i}}=(-\sum b_{i})\ln\frac{\sum b_{i}}{\sum a_{i}}

ואחרי שנפעיל אקספוננט על שני האגפים:

(\frac{\sum a_{i}}{\sum b_{i}})\ge\prod(\frac{a_{i}}{b_{i}})^{b_{i}/\sum b_{i}}

  • אם נבחר b_i השווים כולם ל-1, נקבל את אי-שיוויון הממוצעים.
  • אם נקבע את ערכו של \sum b_i להיות 1 ונעשה את החלפת המשתנים a_{i}=b_{i}a_{i}', נקבל \sum b_{i}a_{i}'\ge\prod a_{i}'^{b_{i}}. זו הגרסה הממושקלת של אי-שיוויון הממוצעים.
  • אם נבחר a_i השווים כולם ל-1, נקבל \frac{\sum b_i}{n} \le\prod b_{i}^{\frac{b_{i}}{\sum b_{i}}} – תוצאה מעניינת שנוגדת את האינטואיציה (ממוצע שמערב מכפלה קטן מממוצע שמערב סכום).
    אם נעלה בחזקת \frac{\sum b_i}{n} ונוציא לוג, נקבל את אי-שיוויון ינסן עבור f(x) = x\ln x, כלומר: זה שקול לקמירות של f(x) = x \ln x.

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

(\sum a_i b_i)^2 \le (\sum a_i^2)(\sum b_i^2)

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

הרעיון הוא להשתמש בכך שפונקציה קמורה גדולה/שווה למשיקיה: תהי f פונקציה קמורה. נניח שהיא גזירה ברציפות ונגזרתה עולה ממש, לשם הנוחות.
יהיו a_1, \cdots, a_n נקודות בתחום הגדרתה. מהקמירות, f(x) \ge f'(c)(x-c)+f(c) לכל c בתחום. נבחר פונקציות f_{i}(x)=p_{i}(f(x)-f'(a_{i})(x-a_{i})-f(a_{i})), כאשר p_i משקולות אי-שליליות המסתכמות ל-1. המינימום של כל אחת הוא 0, והעיקרון שהוכחנו מקודם מראה ש:

0\le\min\sum f_{i}=\min f(x)-x(\sum p_{i}f'(a_{i}))+\sum p_{i}(a_{i}f'(a_{i})-f(a_{i}))

מרציפות ומונוטוניות, קיים c כך ש-f'(c)=\sum_{i=1}^{n} p_{i}f'(a_{i}). כעת רואים שבאגף ימין המינימום הוא על f פחות המשיק ב-x=c (ועוד איזה קבוע), ולכן ב-x=c מתקבל המינימום. העברת אגפים מראה שאי-השיוויון האחרון הופך ל:

\sum p_i (f ' (a_i)a_i - f(a_i)) \ge f ' (c) c -f(c)

עיכול של אי-שיוויון זה מביא אותנו להבנה שזה אי-שיוויון ינסן עבור הפונקציה g המקיימת g(f'(x))=f'(x)x-f(x)g נקראת טרנספורם לז'נדר של f ותסומן גם f^{\star}. עולות כמה שאלות:

  • האם g כזו מוגדרת היטב? כן, כי f' עולה ורציפה.
  • כאמור, הוכחנו את אי-שיוויון ינסן עבור g, אז כנראה ש-g קמורה. האם יש דרך לראות את הקמירות הזו ישירות? כן: מתקיים g(x)=x(f')^{-1}(x) - f((f')^{-1}(x)) (הסימון "חזקת מינוס 1" מציין פונקציה הופכית), וחישוב מראה ש-g'=f'^{-1}. f קמורה, לכן נגזרתה עולה, ולכן גם ההופכית של נגזרתה עולה, כלומר g' עולה. כך מקבלים ש-g קמורה.
  • האם אני יכול לגרום לזה ש-g תהיה כל פונקציה קמורה שאני רוצה? כן, לפחות אם היא גזירה ברציפות ונגזרתה עולה ממש. זה קורה כי (f^{\star})^{\star} = f (נובע מכך שg' = f'^{-1}), אז אפשר לקחת g = f^{\star}. לדוגמא, עבור e^{x} צריך לבחור x\ln x -x ומקבלים את אי-שיוויון הממוצעים בעוד אופן.

הוכחה 7 (H. Bohr) – מקדמים מולטינומים

נסתכל על המולטינום הבא: (a_{1}+\cdots+a_{n})^{nk}. כשאנחנו פותחים סוגריים, הגורם המרכזי הוא \binom{nk}{\underbrace{k,\cdots,k}_{n\text{ times }}}(\prod a_{i})^{k}. אנחנו מקבלים את אי-השיוויון הטריוויאלי הבא:

(a_1 + \cdots + a_n)^{nk} \ge \binom{nk}{\underbrace{k,\cdots,k}_{n\text{ times }}}(\prod a_{i})^{k}

אם נוציא שורש nk-י, נקבל:

 \sum a_{i}\ge\binom{nk}{\underbrace{k,\cdots,k}_{n\text{ times }}}^{\frac{1}{nk}}(\prod a_{i})^{1/n}

כלומר,

\frac{A}{G}\ge\frac{1}{n}\binom{nk}{\underbrace{k,\cdots,k}_{n\text{ times }}}^{\frac{1}{nk}}

כדי להסיק את אי-שיוויון הממוצעים מספיק להראות ש-

\lim_{k\to\infty}\binom{nk}{\underbrace{k,\cdots,k}_{n\text{ times }}}^{\frac{1}{nk}}=n

יש כמה דרכים להראות זאת.

דרך א': קירוב Stirling. זו הדרך הפשוטה: להשתמש בכך שn!\sim(\frac{n}{e})^{n}\sqrt{2\pi n} כדי להסיק שהמקדם הבינומי המרכזי הוא אסימפטוטית Cn^{nk}\sqrt{\frac{n}{k^{n-1}}}, ולאחר שלוקחים שורש nk הוא n כפול ביטוי השואף ל-1.

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

דרך ב': בגלל שלוקחים שורש nk-י מהמקדם הבינומי, לא צריך את כל כוחו של סטירלינג. מספיק להוכיח את אי-השיוויון (\frac{n+1}{e})^{n}(n+1)>n!>(\frac{n}{e})^{n}, לדוגמא באינדוקציה.
(אם בחרתם בדרך האינדוקציה, אתם תיתקלו באי-השיוויון הבא: \frac{1}{n+1}<\ln(1+\frac{1}{n})<\frac{1}{n}. הוא נובע מקעירות של \ln x וקמירות של x\ln x.)

דרך ג' ואחרונה: אפשר בלי אנליזה בכלל. נסתכל רגע על המקרה n=2: אנחנו רוצים לחסום את \binom{2k}{k} מלמטה. אנחנו יודעים שזהו המקדם הבינומי הגדול מבין 2k+1 המקדמים בשורה שלו במשולש פסקל: \{\binom{2k}{i}|0\le i\le2k\}, ושסכומם 2^{2k}. לכן המקדם הבינומי המרכזי גדול או שווה לממוצע של המקדמים הבינומים בשורה שלו, כלומר:

\binom{2k}{k}\ge\frac{2^{2k}}{2k+1}\implies\binom{2k}{k}^{\frac{1}{2k}}\ge \frac{2}{(2k+1)^{1/(2k)}} \underset{k \to \infty}{\to} 2

ניתן לשער שבאופן כללי \binom{nk}{\underbrace{k,\cdots,k}_{n\text{ times }}} מקסימלי מבין \binom{nk}{\underbrace{i_{1},\cdots,i_{n}}_{n\text{ times }}}, כאשר \sum i_{k} = nk. זה שקול ל:

\binom{nk}{\underbrace{k,\cdots,k}_{n\text{ times }}}\ge\binom{nk}{\underbrace{i_{1},\cdots,i_{n}}_{n\text{ times }}}

או: \frac{1}{n}\sum\ln i_{j}!\ge\ln k!, שבתורו ממש מזכיר את אי-שיוויון ינסן עבור הפונקציה f(n) = \ln (n!). ואכן, היא מקיימת סוג של קמירות: f(n+1)-f(n) פונקציה עולה.
אפשר להשתמש כאן במעין ינסן דיסקרטי (כמו שכבר ניתקלנו בעבר עם הפונקציה f(n)=\binom{n}{2}): אפשר להראות שאם \sum i_j = nk ולא כל הi_j-ים שווים k, אז "שווה" לי להחליף את המקסימלי והמינימלי – M,m – במספרים M-1,m+1:

f(M)-f(M-1)\ge f(m+1)-f(m) \implies f(M)+f(m)\ge f(M-1)+f(m+1)

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

תרגיל: הראו שהלוגריתם של פונקציית גמא (\Gamma), פונקציה שידועה בתור היותה הכלה של עצרת, הוא פונקצייה קמורה. במילים אחרות, גמא היא \log-קמורה. למעשה, היא ההכללה היחידה של עצרת שמקיימת זו, ראו משפט Bohr-Mollerup. (כן, זה אותו Bohr.)

הוכחה 8 (Alzer) – אינטגרלים

אציג הוכחה אלגנטית (כלומר, בלי אינדוקציה…) שמופיעה בספר המוכר "Proofs from the BOOK". אנחנו נוכיח את אי-שיוויון הממוצעים הממושקל: \sum p_i a_i \ge \prod a_i^{p_i}, כאשר \{ p_i \}_{i} הסתברויות המסתכמות ל-1. נמיין את המספרים כמו שאנחנו אוהבים לעשות לפעמים: a_{1}\le\cdots\le a_{k}\le G\le a_{k+1}\le\cdots\le a_{n}.

בגלל שהפונקציה f(t) = \frac{1}{t} יורדת עבור מספרים חיוביים, נקבל:

\sum_{i=1}^{k}p_{i}\int_{a_{i}}^{G}(\frac{1}{t}-\frac{1}{G})dt+\sum_{i=k+1}^{n}p_{i}\int_{a_{i}}^{G}(\frac{1}{G}-\frac{1}{t})dt\ge 0

אפשר לכתוב זאת ביחד כ-

\sum p_{i}\int_{G}^{a_{i}}\frac{1}{G}dt\ge\sum p_{i}\int_{G}^{a_{i}}\frac{1}{t}dt

אגף שמאל הוא \sum p_{i}\frac{a_{i}-G}{G}=\frac{A}{G}-1, ואגף ימין מתאפס: \sum p_{i}(\ln a_{i}-\ln G)=\ln G-\ln G=0. לכן A \ge G. \blacksquare

כשראיתי את ההוכחה הזו, תהיתי האם אפשר להחליף את הפונקציה f(t)=\frac{1}{t} בפונקציה אחרת. התכונה הראשונה שהשתמשנו בה היא שהיא יורדת. נחזור על ההוכחה רק עם פונקציה יורדת אחרת מהחיובים לממשיים, שגם אותה נסמן f:

\sum_{i=1}^{k}p_{i}\int_{a_{i}}^{G}(f(t)-f(G))dt+\sum_{i=k+1}^{n}p_{i}\int_{a_{i}}^{G}(f(G)-f(t))dt\ge0

כלומר \sum p_{i}\int_{G}^{a_{i}}f(G)dt\ge\sum p_{i}\int_{G}^{a_{i}}f(t)dt. נסמן ב-F פונקציה קדומה של f, ונקבל:

\sum p_{i}f(G)(a_{i}-G)\ge\sum p_{i}(F(a_{i})-F(G))

או:

f(G)(A-G) \ge \sum p_{i}F(a_{i})-F(G)

נרצה לחלק ב-f(G), ולכן נוסיף את ההנחה הבאה: f חיובית. נקבל:

A-G\ge\frac{\sum p_{i}F(a_{i})-F(G)}{f(G)}

כדי להסיק A \ge G, היינו רוצים שהמונה של השבר יהיה אי-שלילי, כלומר ש-F תקיים \sum p_{i}F(a_{i})\ge F(G)=F(\prod a_{i}^{p_{i}}).
נגדיר את פונקציית העזר h(x)=F(e^{x}). הדרישה נהיית \sum p_{i}h(\ln a_{i})\ge h(\sum p_{i}\ln a_{i}), כלומר: h קמורה. נרצה לנסח זאת במונחי f, לכן נניח שהיא גזירה, לנוחות. הנגזרת השנייה של h צריכה להיות אי-שלילית:

h(x)''=(F(e^{x}))''=(f(e^{x})e^{x})'=f(e^{x})e^{x}+e^{2x}f'(e^{x})=e^{x}(f(e^{x})+e^{x}f'(e^{x}))

כלומר h קמורה אמ"מ f(x)+xf'(x)\ge 0 לכל x חיובי. (נשים לב שעבור f(x)=\frac{1}{x} יש שיוויון.)

לסיכום, כל מה ש-f צריכה לקיים זה שהיא יורדת, חיובית, ומקיימת f(x)+xf'(x)\ge 0. מצאתי שתי מועמדות טבעיות ל-f:

1. f_c(x)=\frac{1}{x+c}, c\ge0
2. f_c(x)=x^{c}, c\ge-1

המשפחה הראשונה נותנת:

A-G\ge(G+c)(\sum p_{i}\ln(a_{i}+c)-\ln(G+c))

אפשר לוודא שz(c)=(G+c)(\sum p_{i}\ln(a_{i}+c)-\ln(G+c)) פונקציה עולה (בידקו!) המקיימת z(0)=0,z(\infty)=A-G. כלומר יש לנו רצף של ביטויים עולים בין 0 לA-G.

המשפחה השנייה נותנת:

A-G\ge\frac{\sum p_{i}a_{i}^{c+1}-G^{c+1}}{G^{c}(c+1)}

כאשר c \to -1 מקבלים 0, וכאשר c \to 0 מקבלים A-G. שוב קיבלנו רצף של ביטויים בין 0 לA-G, אבל אנחנו לא יודעים מה הסדר שלהם כי כעת הפונקציה z(c) = \frac{\sum p_i a_i^{c+1}-G^{c+1}}{G^c(c+1)} לא עולה.

הוכחה 9.1 – תמורות

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

הוא טוען את הדבר הבא: אם \{a_i\}_{i=1}^{n}, \{ b_i\}_{i=1}^{n} הן 2 סדרות של מספרים ממשיים, אז הסכום \sum_{i=1}^{n} a_i b_{\sigma(i)} (כאשר \sigma תמורה על 1,2,\cdots,n) מינימלי כאשר b_{\sigma(i)} ממויינת הפוך מ-a_i, כלומר: a_i \le a_j \leftrightarrow b_{\sigma(i)} \ge b_{\sigma(j)}.
לדוגמא, אם 2 הסדרות עולות, הסכום מינימלי כאשר b_{\sigma(i)} סדרה יורדת, כלומר \sigma(i) = n+1-i.

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

\sum a_i b_{\sigma(i)} \ge \sum a_i b_{n+1-i}

אם i > j אבל b_{\sigma(i)} > b_{\sigma(j)}, נחליף ב-\sigma בין התמונות של i ו-j:

\sigma'(i) = \sigma(j), \sigma'(j) = \sigma(i)

הפעולה הזו מקטינה ממש את הסכום \sum a_i b_{\sigma(i)}, כי:

 a_i b_{\sigma(i)} + a_j b_{\sigma(i)} \ge a_i b_{\sigma(j)} + a_j b_{\sigma(i)} \leftrightarrow (a_i - a_j)(b_{\sigma(i)} - b_{\sigma(j)}) \ge 0

העובדה הזו, בשילוב העובדה שיש רק מספר סופי של תמורות, מראה שמתישהו התהליך נעצר, כלומר מגיעים למצב ש-b_{\sigma(i)} סדרה יורדת, כמו שרצינו. \blacksquare

אז נשתמש באי-שיוויון זה? יהיו a_1, \cdots, a_n מספרים חיוביים שמכפלתם 1. אנחנו רוצים להוכיח ש-\sum_{i=1}^{n} a_i גדול/שווה n. נבחר 2 סדרות:

(a_1, a_1 \cdot a_2, \cdots, a_1 \cdot a_2\cdots a_{n-1} \cdot a_n =1)
(1, \frac{1}{a_1}, \frac{1}{a_1 a_2}, \cdots, \frac{1}{a_1 \cdot a_2 \cdots a_{n-1}})

לראשונה נקרא \{ b_i \} ולשנייה \{ c_i \}. כרגע, המכפלה איבר-איבר של הסדרות, \sum_{i=1}^{n} b_i c_i, מסתכמת לa_1 + \cdots + a_n. מצד שני, לפי אי-שיוויון התמורות, אם אנחנו רוצים לגרום למכפלה \sum b_i c_{\sigma(i)} להיות מינימלית אנחנו צריכים לבחור \sigma(i) = i+1 (כאשר n עובר ל-1) – ודאו זאת. עבור פרמוטציה זו מקבלים \sum_{i=1}^{n} b_i c_{i+1} = n, כמו שרצינו.
אם עושים שינוי משתנים מתאים, מקבלים עוד דרך שקולה להסתכל על זה:

\frac{x_1}{x_2} + \frac{x_2}{x_3} + \cdots + \frac{x_n}{x_1} \ge \frac{x_1}{x_1} + \frac{x_2}{x_2} + \cdots + \frac{x_n}{x_n} = n

לעוד בנושא זה, קראו על קורלציה ואי-שיוויוני קורלציה, כמו אי-שיוויון צ'בישב ו-FKG.

תרגיל: הוכיחו את אי-שיוויון קושי-שוורץ באמצעות אי-שיוויון התמורות.
תרגיל (גיליס 2012): יהיו a_1, \cdots, a_n מספרים חיוביים עם ממוצע אריתמטי 1. הוכיחו ש-
\sum_{i=1}^{n} \frac{a_i}{a_{i+1}} \le \frac{4}{a_1 \cdot a_2 \cdots a_n} + n-4

הוכחה 9.2 – תמורות רבות

זו וריאציה על ההוכחה הקודמת. אפשר להכליל את אי-שיוויון התמורות למקרה של כמה סדרות – אם יש לנו k סדרות עולות של מספרים אי-שליליים, \{ a_{j,i} \}_{i=1}^{n} לכל 1 \le j \le k, אז:

\sum_{i=1}^{n} \prod_{j=1}^{k} a_{j,i} \ge \sum_{i=1}^{n} a_{1,i} \prod_{j=2}^{k} a_{j,\sigma_j(i)}

לכל אוסף תמורות \{ \sigma_j \}_{j=2}^{n} על \{1,2,\cdots ,n\}. את ההוכחה אתם יכולים לקרוא כאן, או להוכיח בעצמכם. בכל אופן, רעיון ההוכחה דומה להוכחה של אי-שיוויון התמורות הקלאסי.

איך משתמשים בתוצאה זו? נבחר את n הסדרות הבאות: a_{j,i} = a_{i}, ואת התמורות להיות סיבובים מעגליים: \sigma_j(i) = i+j-1. לאחר הפעלת התמורות, הסדרות נראות כך:

(a_1, a_2, \cdots, a_n)
(a_2, a_3, \cdots, a_1)
\cdots
(a_n, a_1, \cdots , a_{n-1})

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

\sum_{i=1}^{n} a_i^n \ge n \prod_{i=1}^{n} a_i

וזה ניסוח שקול לאי-שיוויון הממוצעים.

הוכחה 10 – הכללה (מפשטת!) עם משקולות

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

\sum p_{i}a_{i}\ge\prod a_{i}^{p_{i}}

כאשר p_i משקולות/הסתברויות אי-שליליות המסתכמות ל-1. נציג 2 דרכים שונות להוכיח אותה:

א. כדי להוכיח את אי-השיוויון הזה אפשר להוכיחו תחילה עבור הסתברויות רציונליות: נכתוב את השברים עם מכנה משותף כך שp_i = \frac{n_i}{n}. נשתמש באי-שיוויון הממוצעים ה'רגיל' עם \sum n_i משתנים – המספר a_i מופיע n_i פעמים, ונקבל את התוצאה. עבור משקולות אי-רציונליות נקבל את התוצאה מרציפות של פונקציות בסיסיות כמו f(c)=cx, g(c)=x^c ומצפיפות הרציונליים בתוך הממשיים. (למעשה, צפיפות \mathbb{Q}^{n} בתוך \mathbb{R}^{n}.) \blacksquare

ב. לחילופין, אפשר להוכיח את התוצאה באינדוקציה ישירה (בלי להסתמך על אי-השיוויון המקורי), מה שלא היה אפשרי קודם. נראה ראשית את צעד האינדוקציה. נניח שהטענה נכונה ל-2 ול-n משתנים, ונראה ל-n+1:

\begin{aligned} \sum_{i=1}^{n+1} p_i a_i &= ( \sum_{j=1}^{n} p_j ) ( \sum_{i=1}^{n} \frac{p_i}{\sum_{j=1}^{n} p_j} a_i ) + p_{n+1} a_{n+1} \end{aligned}

\begin{aligned} & \ge (\sum_{j=1}^{n} p_j ) \prod_{i=1}^{n} a_i^{\frac{p_i}{ \sum_{j=1}^{n} p_j } } + p_{n+1} a_{n+1} \\ & \ge \prod_{i=1}^{n+1} a_i^{p_i} \end{aligned}

כאשר המעבר השני נובע מהמקרה של n משתנים והמעבר האחרון נובע מהמקרה של 2 משתנים.

נותר להראות את מקרה הבסיס של 2 משתנים, שמסתבר שהוא לא טריוויאלי:

\begin{aligned} a_1 p_1 + a_2 p_2 &\ge p_1^{a_1} p_2^{a_2} \end{aligned}

נסמן p=\frac{1}{p_1},q=\frac{1}{p2},a=a_1^{p_1},b=a_2^{p_2}. התנאי p_1 + p_2=1 מתרגם ל-\frac{1}{p} + \frac{1}{q} = 1. כעת אי-השיוויון הופך ל:

\begin{aligned} \frac{1}{p} + \frac{1}{q} = 1 \implies \frac{a^{p}}{p}+\frac{b^{q}}{q} &\ge ab \end{aligned}

אי-שיוויון זה מכונה "אי-שיוויון Young". אפשר להוכיח אותו בפשטות עם חדו"א של משתנה אחד, אבל יש גם הוכחה גיאומטרית: נסתכל על המלבן [0,a] \times [0,b] בעל שטח ab. אפשר להסתכל עליו כאיחוד של 2 קבוצות זרות: השטח החסום בין y=0, y=b ומתחת לגרף של x^{p-1} בקטע [0,a], והמשלים שלו. השטח הראשון חסום בבירור ע"י האינטגרל של x^{p-1} בקטע [0,a], שיוצא המחובר הראשון: \frac{a^p}{p}. השטח השני שווה, לאחר שיקוף לפי y=x, לשטח של הפונקציה ההופכית של x^{p-1} בקטע [0,b] החסום בין y=0,a. חישוב מראה שהפונקציה ההופכית היא x^{q-1}, ולכן השטח חסום ע"י המחובר השני: \int_{0}^{b} x^{q-1} dx = \frac{b^q}{q}. שיוויון מתקבל כאשר b=a^{p-1} (למה?), תנאי ששקול לa^p=b^q. מש"ל. \blacksquare

הוכחה בציור

הוכחה גיאומטרית לאי-שיוויון Young.

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

נשים לב שאת ההכללה אפשר לנסח בצורה הבאה: E X \ge e^{E \ln X}, או: \ln (E X) \ge E \ln X, כאשר X הוא משתנה מקרי שמקבל את הערך (החיובי) a_i בהסתברות p_i.

תרגיל: הוכיחו, בשיטה של הוכחה ב', שE f(X) \ge f(E X), לכל פונקציה קמורה f ומשתנה מקרי בדיד X. הכלילו למקרה של משתנה מקרי רציף. זה ניסוח אינטגרלי של אי-שיוויון ינסן (האופרטור E הוא אופרטור אינטגרציה לפי מידה הסתברותית).

תרגיל: הוכיחו באמצעות אי-שיוויון Young, את אי-שיוויונות Hölder ו-Minkowski: יהיו \{ a_i \}_{i=1}^{n}, \{ b_i \}_{i=1}^{n} שתי סדרות של מספרי אי-שליליים, ו-p,q מספרים חיוביים המקיימים \frac{1}{p} + \frac{1}{q} = 1. מתקיים:

\sum a_i b_i \le (\sum a_i^p)^{\frac{1}{p}} (\sum b_j^q)^{\frac{1}{q}}

(\sum (a_i+b_i)^p)^{\frac{1}{p}} \le (\sum a_i^p)^{\frac{1}{p}} +(\sum b_i ^p)^{\frac{1}{p}}

הוכחה 11 – Power Mean

אנחנו רוצים להכליל את כל הממוצעים שאנחנו מכירים – הרמוני, אריתמטי, גיאומטרי ואפילו ריבועי (\sqrt{\frac{\sum_{i=1}^{n} a_i^2}{n} } – גדול/שווה אריתמטי). הפונקציה הבאה נותנת תקווה לכך:

\begin{aligned} f(t) & =(\frac{\sum_{i=1}^{n} a_{i}^{t}}{n})^{1/t} \end{aligned}

f(1) הוא הממוצע האריתמטי, f(-1) הוא ההרמוני ו-f(2) הוא הריבועי. אפשר לנחש ש-f(0) הוא הגיאומטרי, במובן הבא: \lim_{t \to 0} f(t) = G. איך מראים זאת? מנסים ומצליחים-

\lim_{t \to 0} f(t)=e^{\lim_{t \to 0} \ln f(t)}=e^{\lim_{t \to 0} \frac{1}{t}\ln(\frac{\sum a_{i}^{t}}{n})}

אנשים לא זהירים יגידו שזה זועק 'לופיטל', ואני אגיד שזה זועק 'נגזרת' – הגבול הוא e^L כאשר L הוא הנגזרת של \ln(\sum a_{i}^{t}/n) ב-x=0. החישוב סטנדרטי ונותן L = \ln G, כרצוי וכצפוי. (השלימו את החישוב!)

קיבלנו "הַרְצָפַה" של כל הממוצעים שהכרנו: לכל t, הפונקציה f(t) נותנת ממוצע מעניין, שנקרא "ממוצע-חזקה" ("Power Mean"). כדי לקבל מזה את אי-שיוויון הממוצעים, נרצה להוכיח ש-f עולה. איך מוודאים זאת? גוזרים. למעשה, מספיק לגזור את הלוגריתם של הפונקציה, וזה גם יותר נוח:

\begin{aligned} \ln f &= \frac{1}{t}\ln(\sum\frac{a_{i}^{t}}{n}) \implies \\ (\ln f)' & = \frac{t\frac{\sum\frac{a_{i}^{t}\ln a_{i}}{n}}{\sum\frac{a_{i}^{t}}{n}}-\ln(\sum a_{i}^{t}/n)}{t^{2}} \end{aligned}

הנגזרת היא פונקציה של הa_i^t-ים, לכן אפשר לסמן b_i = a_i^t וצריך להוכיח שהמונה אי-שלילי, כלומר:

\begin{aligned} \frac{\sum b_i\ln b_{i}}{\sum b_{i}} & \ge\ln\frac{\sum b_{i}}{n} \end{aligned}

זה נובע למשל מקמירות של x\ln x באמצעות אי-שיוויון ינסן. \blacksquare

ראינו ש-(\ln f)' אי-שלילית בכל נקודה אמ"מ היא אי-שלילית ב-t = 1. זה מעלה את החשד להוכחה נוספת, שתידרשו לספק בתרגיל הבא.

תרגיל: הראו שf(p) \ge f(q) שקול ל-f(p/q) \ge f(1), ואי-שיוויון זה אפשר להראות באמצעות אי-שיוויון ינסן מופעל על הפונקציה הקמורה g(x) = x^{p/q}.
תרגיל: הוכיחו ש-f(t)=(\sum p_{i}a_{i}^{t})^{1/t} מונוטונית עולה כאשר \{ p_i \} משקולות אי-שליליים המסתכמים ל-1.
תרגיל: הסיקו את קושי-שוורץ מתוך f(2) \ge f(1).
תרגיל: חשבו את \lim_{t \to \infty} f(t), \lim_{t \to -\infty} f(t).

הוכחה 12.1 (Hurwitz) – סכום ריבועים

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

\forall a_i \in \mathbb{R} : \frac{1}{n}(\sum_{i=1}^{n} a_{i}^{2n})-(a_{1}\cdots a_{n})^{2}\ge0

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

קודם כל, אבחנה בסיסית:

  • סכום של סכומי ריבועים של פולינומים הוא סכום ריבועים של פולינומים.
  • מכפלה של סכומי ריבועים של פולינומים היא סכום ריבועים של פולינומים.

המטרה שלנו היא לכתוב את \frac{1}{n}(\sum a_{i}^{2n})-(a_{1}\cdots a_{n})^{2} כסכום טלסקופי של ביטויים פשוטים יותר, שקל לוודא שהם סכומי ריבועים בעצמם. לשם כך, נגדיר את האופרטור הלינארי הבא, מפולינומים ב-n משתנים לפולינומים סימטרים ב-n משתנים:

 Sf(a_{1},\cdots,a_{n})=\frac{1}{n!}\sum_{\pi\in S_{n}}f(a_{\pi(1)},\cdots,a_{\pi(n)}).

נשים לב שנקודות השבת שלו הן בדיוק הפולינומים הסימטריים. בפרט, את ההפרש שמעסיק אותנו אפשר לכתוב באופן הבא: S(a_1^{2n}) - S((a_1 a_2 \cdots a_n)^2).

הסכום הטלסקופי שלנו יהיה זה:

\sum_{k=2}^{n} S((a_1^{k}a_{2} \cdots a_{n-k+1})^2)- S((a_1^{k-1}a_2 \cdots a_{n-k+2})^2)

לדוגמא, עבור n=3,

S(a_1^6) -S(a_1^2a_2^2a_3^2) = (S(a_1^6)-S(a_1^4a_2^2))+(S(a_1^4a_2^2)-S(a_1^2a_2^2a_3^2))

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

\begin{aligned} S((a_1^{k}a_{2} \cdots a_{n-k+1})^2)- S((a_1^{k-1}a_2 \cdots a_{n-k+2})^2)&=\frac{1}{2}S((a_1^2-a_2^2)(a_1^{2(k-1)}-a_2^{2(k-1)})a_3^2 \cdots a_{n-k+2}^2)\\ &= \frac{1}{2}S((a_1^2-a_2^2)^2 (\sum_{i=0}^{k-2} a_1^{2i}a_2^{2(k-i-2)})a_3^2 \cdots a_{n-k+2}^2) \end{aligned}

כאשר השיוויון הראשון נובע הסימטריה של S(f) (פתחו סוגריים וודאו), והשיוויון השני נובע מהפירוק המוכר x^m-y^m=(x-y)(x^{m-1}+x^{m-2}y+\cdots + y^{m-1}).

למעשה סיימנו – הגענו ל-S של: ריבוע כפול סכום ריבועים כפול ריבוע, כלומר S של סכום ריבועים שהוא בהכרח סכום ריבועים בעצמו. מש"ל.

הוכחה 12.2  – Muirhead

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

יהיו x_1, \cdots, x_n מספרים אי-שליליים קבועים לאורך ההוכחה. נגדיר פונקציה מוקטורי הסתברות ב-a\in\mathbb{R}^{n} (וקטורים עם ערכים אי-שליליים המסתכמים ל-1), למספרים האי-שליליים:

[a]=\frac{1}{n!}\sum_{\pi}\prod_{i} x_{\pi(i)}^{a_{i}} = S( \prod_{i} x_{i}^{a_{i}})

(אותו אופרטור S מההוכחה הקודמת.) לדוגמא, עבור [a]=[(1,0,\cdots,0)] נקבל את הממוצע האריתמטי. לעומת זאת, [b]=[(\frac{1}{n},\cdots,\frac{1}{n})] נותן את הממוצע הגיאומטרי. אנחנו רוצים להראות שיש יחס סדר מסויים על וקטורי ההסתברות הללו, כך שאם a גדול מb אז יתקיים [a] \ge [b]. היחס הזה הוא יחס המג'ורטה, אותו נגדיר כעת.

הגדרה: יהיו a,b שני וקטורים. נסמן בa^{\downarrow},b^{\downarrow} גרסאות ממויינות בסדר יורד שלהם. a יקרא מג'ורטה של b (באנגלית – a \text{ majorizes } b) אמ"מ מתקיימים שני התנאים הבאים:

1. יש להם אותו סכום.
2. סכום כל רישא של a^{\downarrow} גדול/שווה לסכום הרישא המתאימה של b^{\downarrow}:

\sum_{i\le k}a^{\downarrow}_{i}\ge\sum_{i\le k}b^{\downarrow}_{i}

נסמן יחס סדר זה בעזרת "\succ".

משפט מירהד: יהיו a,b שני וקטורי הסתברות. אם a \succeq b אז [a] \ge [b].

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

1. a \succeq b אמ"מ b בקמור של \{aP|P\text{ is a permutation matrix}\}.
2. משפט Birkhoff-von Neumann: כל מטריצה דו-סטוכסטית היא צירוף קמור של מטריצות פרמוטציה.

משתי התוצאות מקבלים: a \succeq b אמ"מ b = aD עבור מטריצה דו-סטוכסטית D. כלומר צריך להראות: [a]\ge[aD]. לדוגמא, (\frac{1}{n},\cdots,\frac{1}{n}) = (1,0,\cdots,0)D עבור מטריצה דו-סטוכסטית D שכל ערכיה \frac{1}{n}.

בהוכחה הקודמת, הורוביץ למעשה כתב את [(1,0,\cdots,0)]-[(\frac{1}{n}, \cdots, \frac{1}{n})] כסכום טלסקטופי, שכל ביטוי בו הוא אי-שלילי (ובנוסף גם סכום ריבועים):

v_k = (1-\frac{k}{n},\underbrace{\frac{1}{n},\cdots,\frac{1}{n}}_{k\text{ times}},0,\cdots,0)
[(1,0,\cdots,0)]-[(\frac{1}{n},\frac{1}{n},\cdots,\frac{1}{n})] = \sum_{k=0}^{n-2} [v_k] - [v_{k+1}]

נעשה משהו דומה.

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

נניח שa \succeq b, וש-b=aD כאשר D=D_1 \cdot D_2 \cdots D_r הצגה של D כמכפלה של מעבריות. אפשר לכתוב את ההפרש שלנו כסכום טלסקופי:

[a]-[b] = \sum_{k=0}^{r-1} [aD_1D_2\cdots D_k] - [aD_1 \cdots D_{k+1}]

ועשינו רדוקציה לבעיה הבאה: להראות ש-[v] \ge [vD] כאשר D מטריצה מעברית – זו כבר בעיה שאתם יכולים לפתור. פתרו אותה והשוו לשלב האחרון בהוכחה של הורוביץ.
(הוכחה מלאה של אי-השיוויון אפשר למצוא בפרק 2 בספר "Combinatorics, The Rota Way" של Kung וYan, ובמאמר המלונקק.)

תרגיל: הראו מפורשות ש-v_{k+1} הוא מהצורה v_k D_k כאשר D_k מטריצה מעברית. כתבו את המטריצה שכל ערכיה \frac{1}{n} כמכפלה של מטריצות מעבריות.
תרגיל: הוכיחו את אי-שיוויון Karamata: אם a מג'ורטה של b ו-f קמורה, מתקיים:

\sum f(a_{i})\ge\sum f(b_{i})

הוכחה 13 – אי-השיוויונים של ניוטון ומקלורן

עוד עידון של אי-שיוויון הממוצעים, הפעם דיסקרטי.

ניוטון הגדיר סכומים סימטריים S_k:

S_k =\frac{1}{n!} \sum_{\sigma \in S_n} \prod_{i=1}^{k} a_{\sigma(i)} = S(a_1 a_2 \cdots a_k)

(אותו S מהוכחה 12.1.) נסמן S_0=1.

נשים לב ש-S_{1}=A, S_{n}=G^{n}. עוד דוגמא: S_2 = \frac{ \sum_{1 \le i <j \le n} a_i a_j}{\binom{n}{2}}.

ניוטון הוכיח:

S_{k-1}S_{k+1}\le S_{k}^{2}

אם לוקחים לוגריתם של 2 האגפים זה נראה כמו אנלוג דיסקרטי לקעירות של סדרה S_k – "קעירות לוגריתמית". סדרות שמקיימות את אי-השיוויון של ניוטון מופיעות הרבה בקומבינטוריקה – חפשו בגוגל "Log Concave Sequences". דוגמא מוכרת – כל שורה במשולש פסקל היא סדרה לוג-קעורה (הוכיחו!).

ההוכחה של אי-שיוויון ניוטון היא מקסימה (מצאתי אותה במאמר של ריצ'ארד סטאנלי האגדי ): נסתכל על הפולינום f(x) = \prod_{i=1}^{n} (x+a_i) = \sum b_i x^i. נשים לב שהמקדם של x^k הוא S_{n-k} \cdot \binom{n}{k}.

למה 1 לקורא/ת: לפולינום הריבועי ax^2+2bx+c שורשים ממשיים אמ"מ b^2 \ge ac.
למה 2 לקורא/ת: אם לפולינום ממעלה n יש n שורשים ממשיים, אז לנגזרת שלו יש n-1 שורשים ממשיים. (רמז: משפט רול)

נסתכל על הפולינום f שהגדרנו. אנחנו רוצים להגיד משהו מעניין על 3 מקדמים עוקבים שלו – b_{j-1}, b_{j}, b_{j+1}. כדי להיפטר מהמקדמים הנמוכים, נגזור אותו j-1 פעמים. עכשיו אנחנו רוצים להיפטר מהמקדמים הגבוהים –  נסתכל על הפולינום "ההפוך" המתאים לו, g_{\text{rev}}(x) = x^{n-j+1}g(\frac{1}{x}). הוא מאותה מעלה וגם בעל שורשים ממשיים. נגזור אותו n-j-1 פעמים וכך נקבל פולינום ריבועי עם מקדמים ממשיים (שוב מלמה 2), שהמקדמים שלו הם כפולות של b_{j-1}, b_{j}, b_{j+1}. מפורשות, אנחנו מבצעים את הפעולות הבאות:

\begin{aligned} \sum b_i x^i & \xrightarrow{\text{Differentiating j-1 times}} \sum b_i \frac{i!}{(i-j+1)!} x^{i-j+1} \\ & \xrightarrow{\text{Reversing}} \sum b_i \frac{i!}{(i-j+1)!}x^{n-i} \\ & \xrightarrow{\text{Differentiating n-j-1 times}} \sum b_i \frac{i!}{(i-j+1)!} \frac{(n-i)!}{(j-i+1)!} x^{j+1-i} \\ & = b_{j+1} \frac{(j+1)!(n-j-1)!}{2!0!} + b_{j} \frac{j!(n-j)!}{1!1!} x+ b_{j-1} \frac{(j-1)!(n-j+1)!}{0!2!} x^2\\ &= \frac{n!}{2} \left(\frac{b_{j+1}}{\binom{n}{j+1}} + 2\frac{b_{j}}{\binom{n}{j}}x + \frac{b_{j-1}}{\binom{n}{j-1}}x^2 \right) \end{aligned}

מלמה 2 מופעלת n-2 פעמים ואז למה 1, נקבל:

\begin{aligned} \frac{b_j^2}{\binom{n}{j}^2} &\ge \frac{b_{j+1}}{\binom{n}{j+1}}\frac{b_{j-1}}{\binom{n}{j-1}} \end{aligned}

וזה שקול לאי-שיוויון ניוטון S_{n-j}^2 \ge S_{n-j-1}S_{n-j+1}. \blacksquare

מקלורן הראה שS_{k}^{1/k} היא סדרה יורדת. בפרט, S_{n}^{1/n}\le S_{1}, כלומר A \ge G.

איך הוא הראה זאת? \frac{S_{i}}{S_{i-1}} סדרה יורדת לפי אי-שיוויון ניוטון, לכן:

S_{k}=\prod_{i=1}^{k}\frac{S_{i}}{S_{i-1}}=\prod_{i=1}^{k-1}(\frac{S_{k}}{S_{k-1}})^{\frac{1}{k-1}}\frac{S_{i}}{S_{i-1}}\le\prod_{i=1}^{k-1}(\frac{S_{i}}{S_{i-1}})^{\frac{1}{k-1}+1}=S_{k-1}^{\frac{k}{k-1}}

נוציא שורש k-י ונקבל את התוצאה. (למעשה ההוכחה של מקלורן עובדת לכל סדרה לוג-קעורה וחיובית.)

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

הוכחה 14 (Gaines) – מטריצות

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

למה: בהינתן מטריצה מרוכבת A מגודל n \times n, עם ערכים עצמיים \{ \lambda_i \}_{i=1}^{n}, אז \sum_{i=1}^{n}|\lambda_{i}|^{2}\le\sum_{1\le i,j \le n} |a_{i,j}|^{2}.
הוכחה: אם המטריצה אלכסונית, הטענה טריוויאלית. בעצם, גם אם המטריצה משולשית עליונה. באופן כללי, כל מטריצה דומה אוניטרית למטריצה משולשית עליונה (עוד תוצאה של שור – תרגיל בשבילכם!), כלומר ניתנת להצגה בצורה A=U^{*}TU כאשר T משולשית עליונה ו-U^{*}U=I. מהצגה זו אפשר לקבל:

\sum|a_{ij}|^{2}=\mathrm{tr}(AA^{*})=\mathrm{tr}(U^{*}TUU^{*}T^{*}U)=\mathrm{tr}(U^{*}TT^{*}U)=\mathrm{tr}(TT^{*}) = \sum |t_{ij}|^2

ובזאת עשינו רדוקציה למקרה הקל של מטריצה משולשית עליונה. (השתמשנו בכך שדימיון משמר ערכים עצמיים ובפרט את ה\text{trace}.) מש"ל. \blacksquare

יהיו a_1, \cdots, a_n המספרים שלנו. נפעיל את הלמה על המטריצה n \times n שכולה אפסים מלבד n האיברים a_{1,2}, a_{2,3}, \cdots, a_{n-1,n}, a_{n,1} ששווים ל\sqrt{a_1}, \cdots, \sqrt{a_n} בהתאמה.
חישוב הפולינום האופייני יוצא x^n - \sqrt{a_1 \cdot a_2 \cdot \cdots \cdot a_n}, והלמה של שור נותנת במקרה זה בדיוק את אי-שיוויון הממוצעים.

אינטואיציה? אין (לפחות לי).

חלק ג' – סיכום

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

  • קושי-שוורץ
  • ינסן
  • מירהד
  • יאנג
  • תמורות
  • ברנולי

והזכרנו מושגים כמו:

  • קבוצות קמורות, קומפקטיות וצפופות
  • קמירות, קעירות וסדרות לוג-קעורות
  • משפט רול, משיקים, טרנספורם לז'נדר

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

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

תרגילים (וריאציות על אי-שיוויון הממוצעים)

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

שאלה 1 – אי-שיוויון Ky-Fan: יהיו x_1, \cdots, x_n מספרים חיוביים קטנים/שווים 0.5. נסמן בA,G,H את הממוצעים של \{ x_i \}, ובA',G',H' את הממוצעים של הסדרה המשלימה \{1-x_i\}. הוכיחו:

\frac{A}{A'} \ge \frac{G}{G'} \ge \frac{H}{H'}

(הערה: זה עובד גם עבור ממוצעים משוקללים)

שאלה 2 – אי-שיוויון Mahler: הוכיחו שהממוצע הגיאומטרי הוא סופר-אדיטיבי, כלומר:

\prod_{i=1}^{n} (x_i+y_i)^{1/n} \ge \prod_{i=1}^{n} x_i^{1/n} + \prod_{i=1}^{n} y_i^{1/n}

שאלה 3 – חיזוקים של אי-שיוויון הממוצעים:

יהיו A,G הממוצעים של x_1, \cdots, x_n עם הסתברויות p_1, \cdots, p_n.

i. תוצאה של Aldaz (קשה):

\ln (\frac{A}{G}) \ge 2(1-\frac{\sum p_i \sqrt{x_i}}{\sqrt{A}})

ii. תוצאה של Alzer (קשה):

A-G \ge \frac{\sum p_i(x_i-G)^2}{2 \max x_i}

iii. תוצאה של Cartwright ו-Field (קשה):

A-G \le \frac{\sum p_i(x_i-A)^2}{2 \min x_i}

שאלה 4 – מתחרות דרום קוריאנית, 1997:

הוכיחו כי:

\frac{A}{H} \le \begin{cases} -1+2(\frac{A}{G})^n & 2|n \\ -\frac{n-2}{n}+2\frac{n-1}{n}(\frac{A}{G})^n & 2 \nmid n \end{cases}

שאלה 5 – הממוצע האריתמטי-גיאומטרי: יהיו 2 מספרים x,y חיוביים. נבצע את התהליך הבא: נחליף כל פעם את 2 המספרים בממוצע האריתמטי והגיאומטרי שלהם –

(x_{n+1},y_{n+1}) = (\frac{x_n + y_n}{2}, \sqrt{x_n y_n})

שתי הסדרות \{x_n\}, \{y_n\} מתכנסות לגבול משותף, שנקרא הממוצע האריתמטי-גיאמוטרי של x,y. הוכיחו זאת.

לקריאה נוספת

1. הרבה מההוכחות מצאתי בספר "Handbook of Means and Their Inequalities" של P. S. Bullen. פרק 2 מכיל בין היתר 74 הוכחות שונות, ניסיתי לבחור את היפות מביניהן.

2. הספר "Inequalities" של Beckenbach ו-Bellman גם היה לי לעזר.

3. שני ספרים מעולים על אי-שיוויונים:

————–

שבוע מעולה,

אופיר, שמקדיש את הפוסט לענת ולאמילי

נ.ב. אשמח לתגובות, הערות, תיקונים, תוספות, …

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

אודות Ofir Gorodetsky

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

14 תגובות על אי-שיוויון הממוצעים

  1. תום הגיב:

    ווהו! פוסט חדש

    • gorofir הגיב:

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

  2. המעריץ מספר 1 הגיב:

    tuphr יא מלך!

  3. תפוז הגיב:

    איזו השקעה!
    תודה

  4. נוגה הגיב:

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

    • gorofir הגיב:

      תודה. לא שמעתי על אי-שיוויון זה וגם לא מצאתי עליו מידע, את בטוחה לגבי השם? במה הוא עסק?

      • נוגה הגיב:

        אני לא בטוחה לגבי השם, כך שמעתי מהמרצה. דיבר עליו בכמה הקשרים:
        1. להוכיח את אי שוויון קושי בעזרתו,
        2. להוכיח בעזרתו את אי שוויון ברנולי עבור כל X
        וכך נראה אי השוויון המדובר:
        a^(n-1) / b >= (n+1)a-nb
        תודות !

    • gorofir הגיב:

      (אני מגיב לתגובה הזו כמשום מה אני לא מצליח להגיב לתגובה החדשה שלך)
      התכוונת בוודאי לאי-שיוויון הבא:
      a^n / b^(n-1) >= na – (n-1)b
      אני לא מכיר את השם שלו, אבל אם תחלקי את 2 האגפים ב-b ותסמני z=a/b, זה הופך ל:
      z^n >= nz-(n-1)
      אי-שיוויון שהשתמשתי בו בהוכחות מספר 3.1, 3.2 ו-3.3. אפשר לקבל איתו הוכחות קצרות להרבה אי-שיוויונים. נתחיל מזה, שאם כותבים אותו כ-z^n + (n-1) >= nz, הוא שקול לאי-שיוויון הממוצעים על n מספרים כאשר n-1 מתוכם שווים, ועם עובדה זו אפשר לייצר הוכחה באינדוקציה (כמו שנעשה בפוסט). שנית, אם מציבים z+1 במקום z זה *שקול* לאי-שיוויון ברנולי:
      ddd (1+z)^n >= 1+zn ddd
      ולגבי אי-שיוויון קושי-שוורץ: הוא שקול לאי-שיוויון (sum a_i^2 / b_i) >= sum(a_i)^2 / sum(b_i). מהומוגניות, נניח שsum a_i = sum b_i. נפעיל על a_i,b_i את האי-שיוויון עם n=2, כלומר a^2 / b>=2a-b, ונסכום על i כדי לקבל: (sum a_i^2 / b_i) >= 2 sum a_i – sum b_i. בזכות התנאי שבחרנו, אגף ימין יוצא אגף ימין של אי-שיוויון קושי-שוורץ.

      לסיכום, נראה לי שאי-שיוויון ברנולי זה אחלה שם לאי-שיוויון הזה.

  5. ריבוע בנוי הגיב:

    נקלעתי לכאן באקראי וגליתי פוסט נפלא!
    בינתיים רק התחלתי לקרוא.

    1 (שאלה):
    האם תוכל להסביר למה
    \frac{a+b}{2} \ge \sqrt{ab} שקול ל(\sqrt{a}-\sqrt{b})^{2}\ge0

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

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

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

    ונקרב את 2 המספרים "עד הסוף", כלומר עד שיהיו זהים.
    בשביל לקרב את הערך a ל-b נצטרך להקטין את הפער היחסי בין M-P ל- M-Q. דרך אחת לעשות זאת היא לקרב את Q אל P (להקטין את

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

    הנקודות A,G ו-H מתאחדות לנקודה אחת, כך ששלשת המרחקים M-A, M-G ו- M-H שווים. אבל אז "אבדנו את התרשים" ואין לנו 3 קוים

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

    הזוית \bigtriangleup AGH תקטן, כש-H מתקרבת ל-A, אורכו של G-M קרוב יותר לארכו של A-M, וכן הגדלים A-M ו- H-M, קרבים זה לזה,

    כמובן.
    כשנרצה להדגים ערכי a ו-b שווים, נרחיק את M עד ה"אינסוף", אז היא קרובה במדה *שוה* אל Q ואל P, כך ש-a שוה ל-b. ואז יראה התרשים

    את שוויון הממוצעים, כי אז G-H מתלכד עם G-A (הזוית \bigtriangleup AGH = 0), כך ש- M-A ו- M-H מתלכדים אף הם והקו M-G שוה להם

    בארכו (הוא "מקביל" להם…).

    • gorofir הגיב:

      1. אשמח להסביר. התשובה הקצרה היא – פותחים סוגריים וזה יוצא. התשובה הארוכה: הביטוי (\sqrt{a} - \sqrt{b})^2 שווה ל-a + b - 2\sqrt{ab}, ע"י פתיחת סוגריים (מה שנקרא "הבינום של ניוטון"), שזה בדיוק פעמיים ההפרש בין \frac{a+b}{2} ל-\sqrt{ab}. כלומר, ההפרש אי-שלילי אמ"מ a + b - 2\sqrt{ab} אי-שלילי אמ"מ (\sqrt{a} - \sqrt{b})^2 אי-שלילי.

    • gorofir הגיב:

      2. תודה על התוספת. בסוף השתמשת בטיעון רציפות בכל זאת ("היא קרובה במדה *שוה* אל Q ואל P"), אבל אין דרך להתחמק מכך.

  6. פינגבאק: אלגוריתמים להוכחת זהויות קומבינטוריות | One and One

  7. פינגבאק: חדו"א-צ'יט #1 | One and One

  8. תומר הגיב:

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

להשאיר תגובה

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

הלוגו של WordPress.com

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

תמונת Twitter

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

תמונת Facebook

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

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

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

מתחבר ל-%s