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

[בתאל]

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

 

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

תודה מראש ושבוע טוב

[אודי]

שתי הזהויות שלך מוכחות באותו אופן, מכתיבת הקומבינציות ומכנה משותף:

 

http://www.codecogs.com/gif.latex?%5Cbinom%7Bn%7D%7Bk%7D+%5Cbinom%7Bn%7D%7Bk+1%7D=%5Cfrac%7Bn!%7D%7Bk!(n-k)!%7D+%5Cfrac%7Bn!%7D%7B(k+1)!(n-k-1)!%7D=%5Cfrac%7Bn!(k+1+n-k)%7D%7B(k+1)!(n-k)!%7D=%5Cfrac%7Bn!(n+1)%7D%7B(k+1)!(n+1-k-1)!%7D=%5Cfrac%7B(n+1)!%7D%7B(k+1)!(n+1-k-1)!%7D=%5Cbinom%7Bn+1%7D%7Bk+1%7D

 

http://www.codecogs.com/gif.latex?%5Cbinom%7Bn%7D%7Bk-1%7D+%5Cbinom%7Bn%7D%7Bk%7D=%5Cfrac%7Bn!%7D%7B(k-1)!(n-k+1)!%7D+%5Cfrac%7Bn!%7D%7Bk!(n-k)!%7D=%5Cfrac%7Bn!(k+n-k+1)%7D%7Bk!(n-k+1)!%7D=%5Cfrac%7Bn!(n+1)%7D%7Bk!(n+1-k)!%7D=%5Cfrac%7B(n+1)!%7D%7Bk!(n+1-k)!%7D=%5Cbinom%7Bn+1%7D%7Bk%7D

 

לגבי ההוכחה באינדוקציה, עבור n=1

http://www.codecogs.com/gif.latex?%5CSigma%20P_1=1+1=2%5E1

 

כעת נניח ש

http://www.codecogs.com/gif.latex?%5CSigma%20P_n=2%5En

ומהגדרת משולש פסקל ידוע

http://www.codecogs.com/gif.latex?%5CSigma%20P_%7Bn+1%7D=%5Cbinom%7Bn+1%7D%7B0%7D+%5Cbinom%7Bn+1%7D%7B1%7D+...+%5Cbinom%7Bn+1%7D%7Bn+1%7D

http://www.codecogs.com/gif.latex?%5CSigma%20P_%7Bn%7D=%5Cbinom%7Bn%7D%7B0%7D+%5Cbinom%7Bn%7D%7B1%7D+...+%5Cbinom%7Bn%7D%7Bn%7D

נחסר בין השורות איבר איבר. האיבר הראשון מצטמצם כי הוא 1 בשניהם. האיבר האחרון בשורה n+1 לא מצטמצם כי אין לו בן זוג. מתקבל:

http://www.codecogs.com/gif.latex?%5CSigma%20P_%7Bn+1%7D-%5CSigma%20P_n=%5Cbinom%7Bn+1%7D%7B1%7D-%5Cbinom%7Bn%7D%7B1%7D+%5Cbinom%7Bn+1%7D%7B2%7D-%5Cbinom%7Bn%7D%7B2%7D+...+%5Cbinom%7Bn+1%7D%7Bn%7D-%5Cbinom%7Bn%7D%7Bn%7D+%5Cbinom%7Bn+1%7D%7Bn+1%7D

 

נשתמש באחת הזהויות שהוכחנו כרגע, רק נעביר בה אגפים:

http://www.codecogs.com/gif.latex?%5Cbinom%7Bn+1%7D%7Bk%7D-%5Cbinom%7Bn%7D%7Bk%7D=%5Cbinom%7Bn%7D%7Bk-1%7D

ונקבל:

http://www.codecogs.com/gif.latex?%5CSigma%20P_%7Bn+1%7D-%5CSigma%20P_n=%5Cbinom%7Bn%7D%7B0%7D+%5Cbinom%7Bn%7D%7B1%7D+...+%5Cbinom%7Bn%7D%7Bn-1%7D+%5Cbinom%7Bn+1%7D%7Bn+1%7D

 

עכשיו נרשום את האחד שיש לנו בסוף השורה כ-http://www.codecogs.com/gif.latex?%5Cbinom%7Bn%7D%7Bn%7D במקום http://www.codecogs.com/gif.latex?%5Cbinom%7Bn+1%7D%7Bn+1%7D ונקבל:

 

http://www.codecogs.com/gif.latex?%5CSigma%20P_%7Bn+1%7D-%5CSigma%20P_n=%5Cbinom%7Bn%7D%7B0%7D+%5Cbinom%7Bn%7D%7B1%7D+...+%5Cbinom%7Bn%7D%7Bn-1%7D+%5Cbinom%7Bn%7D%7Bn%7D=%5CSigma%20P_n

כלומר

http://www.codecogs.com/gif.latex?%5CSigma%20P_%7Bn+1%7D=2%5CSigma%20P_n

 

ומכיוון שהנחנו:

http://www.codecogs.com/gif.latex?%5CSigma%20P_n=2%5En

נובע משני השוויונות ישר

http://www.codecogs.com/gif.latex?%5CSigma%20P_%7Bn+1%7D=2%5Ctimes2%5En=2%5E%7Bn+1%7D

 

מש"ל באינדוקציה.

[אודי]

אגב, אפשר לשאול למה את צריכה את זה? כי זה לא נראה לי כמו שיעורי בית באלגברה

[בתאל]

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

[אודי]

אה. משום מה קראתי "נתנאל" ולא "בתאל". השעה, כנראה

8-[

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

 

שיהיה בהצלחה!

[בתאל]

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

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

תודה רבה מראש על העזרה...

[אודי]

צ"ל

http://www.codecogs.com/gif.latex?(x+y)%5En=%5Csum_%7Bk=0%7D%5En%20%5Cbinom%7Bn%7D%7Bk%7D%20x%5Eky%5E%7Bn-k%7D

לכל n.

 

נבדוק עבור n=1:

http://www.codecogs.com/gif.latex?%5Csum_%7Bk=0%7D%5E1%5Cbinom%7B1%7D%7Bk%7Dx%5Eky%5E%7B1-k%7D=%5Cbinom%7B1%7D%7B0%7Dx%5E0y%5E1+%5Cbinom%7B1%7D%7B1%7Dx%5E1y%5E0=x+y

 

עובד.

עכשיו נניח

 

http://www.codecogs.com/gif.latex?(x+y)%5En=%5Csum_%7Bk=0%7D%5En%20%5Cbinom%7Bn%7D%7Bk%7D%20x%5Eky%5E%7Bn-k%7D

 

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

 

http://www.codecogs.com/gif.latex?(x+y)%5E%7Bn+1%7D=%5Csum_%7Bk=0%7D%5E%7Bn+1%7D%20%5Cbinom%7Bn+1%7D%7Bk%7D%20x%5Eky%5E%7Bn+1-k%7D

 

ננסה לחשב את הבינום ה-n+1-י תוך שימוש בהנחה לגבי הבינום ה-n-י:

http://www.codecogs.com/gif.latex?(x+y)%5E%7Bn+1%7D=(x+y)(x+y)%5En=(x+y)%5Csum_%7Bk=0%7D%5En%20%5Cbinom%7Bn%7D%7Bk%7D%20x%5Eky%5E%7Bn-k%7D=%5Csum_%7Bk=0%7D%5En%20%5Cbinom%7Bn%7D%7Bk%7D%20x%5E%7Bk+1%7Dy%5E%7Bn-k%7D+%5Csum_%7Bk=0%7D%5En%20%5Cbinom%7Bn%7D%7Bk%7D%20x%5Eky%5E%7Bn-k+1%7D

 

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

 

http://www.codecogs.com/gif.latex?(x+y)%5E%7Bn+1%7D=%5Csum_%7Bk=1%7D%5E%7Bn+1%7D%20%5Cbinom%7Bn%7D%7Bk-1%7D%20x%5E%7Bk%7Dy%5E%7Bn-k+1%7D+%5Csum_%7Bk=0%7D%5En%20%5Cbinom%7Bn%7D%7Bk%7D%20x%5Eky%5E%7Bn-k+1%7D

 

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

 

http://www.codecogs.com/gif.latex?(x+y)%5E%7Bn+1%7D=%5Csum_%7Bk=1%7D%5E%7Bn%7D(%5Cbinom%7Bn%7D%7Bk-1%7D+%5Cbinom%7Bn%7D%7Bk%7D)%20x%5E%7Bk%7Dy%5E%7Bn+1-k%7D+%5Cbinom%7Bn%7D%7Bn%7Dx%5E%7Bn+1%7D+%5Cbinom%7Bn%7D%7B0%7Dy%5E%7Bn+1%7D

 

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

http://www.codecogs.com/gif.latex?%5Cbinom%7Bn%7D%7Bk-1%7D+%5Cbinom%7Bn%7D%7Bk%7D=%5Cbinom%7Bn+1%7D%7Bk%7D

ונזכור ש

http://www.codecogs.com/gif.latex?%5Cbinom%7Bn%7D%7B0%7D=%5Cbinom%7Bn+1%7D%7B0%7D=%5Cbinom%7Bn%7D%7Bn%7D=%5Cbinom%7Bn+1%7D%7Bn+1%7D=1

 

ונקבל:

http://www.codecogs.com/gif.latex?(x+y)%5E%7Bn+1%7D=%5Csum_%7Bk=1%7D%5E%7Bn%7D%5Cbinom%7Bn+1%7D%7Bk%7D%20x%5E%7Bk%7Dy%5E%7Bn+1-k%7D+%5Cbinom%7Bn+1%7D%7Bn+1%7Dx%5E%7Bn+1%7D+%5Cbinom%7Bn+1%7D%7B0%7Dy%5E%7Bn+1%7D

 

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

 

http://www.codecogs.com/gif.latex?(x+y)%5E%7Bn+1%7D=%5Csum_%7Bk=0%7D%5E%7Bn+1%7D%20%5Cbinom%7Bn+1%7D%7Bk%7D%20x%5Eky%5E%7Bn+1-k%7D

[בתאל]

תודה רבה רבה אודי 

[בתאל]

היי אודי, הבנתי נהדר את ההסבר עד השורה הזו-

 

 

 

ננסה לחשב את הבינום ה-n+1-י תוך שימוש בהנחה לגבי הבינום ה-n-י:

http://www.codecogs.com/gif.latex?(x+y)%5E%7Bn+1%7D=(x+y)(x+y)%5En=(x+y)%5Csum_%7Bk=0%7D%5En%20%5Cbinom%7Bn%7D%7Bk%7D%20x%5Eky%5E%7Bn-k%7D=%5Csum_%7Bk=0%7D%5En%20%5Cbinom%7Bn%7D%7Bk%7D%20x%5E%7Bk+1%7Dy%5E%7Bn-k%7D+%5Csum_%7Bk=0%7D%5En%20%5Cbinom%7Bn%7D%7Bk%7D%20x%5Eky%5E%7Bn-k+1%7D

 

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

 

הסיגמה רצה מ-1 עד ל  n+1 השאלה - המקדם הבינומאלי לא אמור להיות k+1 מעל n+1 

אשמח אם תוכל להסביר לי את זה ... 

תודה רבה רבה רבה מראש  :lol:

[אודי]

הזזנו את אינדקס הסכימה k ביחידה קדימה (כלומר, k החדש שלנו הוא בעצם k'=k+1)

 

n שנמצא במקדם הבינומי לא השתנה (כי הוא מספר קבוע שלא תלוי בבחירת אינדקס הסכימה).

 

מה שישתנה (חוץ מהחזקות של x ו-y שעבורם עשינו את התיקון הזה) הוא טווח הריצה של אינדקס הסכימה החדש ו-k שהיה במקדם הבינומי:

1. אם k הישן רץ מ-0 עד n, נובע ש-k החדש (שהוא כזכור בעצם k'=k+1) ירוץ מ-1 עד n+1 כדי לייצר את אותם איברים בסכום.

2. כמו כן, k שהיה בתוך המקדם הבינומי של הסכום הישן הוא k-1 במונחי האינדקס החדש, ולכן גם את החלק התחתון של המקדם הבינומי צריך לתקן.

 

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

[בתאל]

תודה רבה אודי  :lol: