הבינום של ניוטון

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

הנוסחה בצורתה הבסיסית היא: $(x+y)^n=\sum_{k=0}^n{n \choose k}x^ky^{n-k}$ .

כאשר ${n \choose k}=\frac{n!}{k!(n-k)!}$ . מספרים אלו נקראים מקדמי הבינום, ויש להם חשיבות רבה בקומבינטוריקה. כלי נוח למציאת מקדמי הבינום הוא משולש פסקל.

נשים לב כי ${n \choose k}$ הינו מספר האפשרויות לבחור $\ k$ איברים מתוך $\ n$ ללא חזרות וללא חשיבות לסדר. דבר זה אינו מקרי, כפי שנראה להלן בהוכחת נכונות הנוסחה.

מקרה פרטי חשוב של הנוסחה, בעל שימושים רבים בקומבינטוריקה, הוא $(1+x)^n=\sum_{k=0}^n{n \choose k}x^k$ .

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

$\ ( x + y )^r = \sum_{i=0}^\infty {r \choose i} x^i y^{r-i}$ כאשר $\ {r \choose i} = \frac{r (r-1) \cdots (r-i)}{i !}$

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

[עריכה] הבינום הרגיל

[עריכה] דוגמה

נראה את שלושת המקרים הראשונים של הנוסחה:

$\ (x+y)^2=x^2+2xy+y^2$

$\ (x+y)^3=x^3+3x^2y+3xy^2+y^3$

$\ (x+y)^4=x^4+4x^3y+6x^2y^2+4xy^3+y^4$

[עריכה] הוכחה

ראשית, נשים לב כי $\ (x+y)^n=(x+y)\cdot(x+y)\cdot\dots\cdot(x+y)$ . יש לנו $\ n$ סוגריים שמוכפלים אלה באלה. התוצאה המתקבלת (על פי כללי האלגברה) היא סכום של כל המכפלות האפשריות שבהן נבחר איבר יחיד מכל אחד מהסוגריים. נדגים זאת עבור מקרה פרטי: $\ (x+y)^2=(x+y)\cdot(x+y)=x\cdot x+x\cdot y +y\cdot x+y\cdot y=x^2+2xy+y^2$ .

בדוגמה זו:

האיבר הראשון התקבל מבחירת $\ x$ מהסוגריים הראשונים ו $\ x$ מהסוגריים השניים.
האיבר השני התקבל מבחירת $\ x$ מהסוגריים הראשונים ו $\ y$ מהסוגריים השניים.
האיבר השלישי התקבל מבחירת $\ y$ מהסוגריים הראשונים ו $\ x$ מהסוגריים השניים.
האיבר הרביעי התקבל מבחירת $\ y$ מהסוגריים הראשונים ו $\ y$ מהסוגריים השניים.

בצורה זו ניתן לפתח כל ביטוי מהסוג $\ (x+y)^n$ כסכום של כל המחוברים האפשריים, כאשר כל מחובר הוא מכפלה של איברים שנבחרו מהסוגריים.

על כן, עבור האיבר $\ ax^ky^j$ המקדם $\ a$ הוא בדיוק מספר האפשרויות לבחור $\ k$ פעמים את $\ x$ ו- $\ j$ פעמים את $\ y$ . מאחר שניתן לבחור רק מתוך שני האיברים הללו, די לבדוק בכמה אפשרויות ניתן לבחור את $\ x$ כי בהכרח מתקיים $\ k+j=n$ (אם בחרנו $\ k$ פעמים את $\ x$ , אנחנו חייבים לבחור $\ n-k$ פעמים את $\ y$ , כי זו האפשרות האחרת היחידה).

מספר האפשרויות לבחור את $\ x$ מתוך $\ n$ סוגריים בדיוק $\ k$ פעמים נתון על ידי $\ {n\choose k}$ ולכן זהו בדיוק המקדם של $\ x^ky^j$ .

[עריכה] הוכחה באינדוקציה

צריך להוכיח: $(a+b)^n=\sum_{k=0}^n {n \choose k}a^kb^{n-k}$

בדיקה עבור n=2: $(a+b)^2=\sum_{k=0}^2 {2 \choose k}a^kb^{2-k}$ .

$\sum_{k=0}^2 {2 \choose k}a^kb^{2-k}={2 \choose 0}a^0b^2+{2 \choose 1}a^1b^1+{2 \choose2}a^2b^0=a^2+2ab+b^2$ .

הנחת האינדוקציה: נניח נכונות עבור n=i : $(a+b)^i=\sum_{k=0}^i {i \choose k}a^kb^{i-k}$ .

ונוכיח נכונות עבור n=i+1: $(a+b)^{i+1}=\sum_{k=0}^{i+1} {i+1 \choose k}a^kb^{i+1-k}$ .

הוכחה:

$\ (a+b)^{i+1}=(a+b)^i(a+b)$ . נשתמש בהנחת האינדוקציה ונחליף את $\ (a+b)^i$ ב- $\sum_{k=0}^i {i \choose k}a^kb^{i-k}$

$(a+b)\sum_{k=0}^i {i \choose k}a^kb^{i-k}=a\sum_{k=0}^i {i \choose k}a^kb^{i-k}+b\sum_{k=0}^i {i \choose k}a^kb^{i-k}=$

$\sum_{k=0}^i {i \choose k}a^{k+1}b^{i-k}+\sum_{k=0}^i {i \choose k}a^kb^{i-k+1}=\sum_{k=1}^{i+1} {i \choose k-1}a^kb^{i-k+1}+$

$\sum_{k=0}^i {i \choose k}a^kb^{i-k+1}={i \choose i}a^{i+1}b^0+\sum_{k=1}^{i} {i \choose k-1}a^kb^{i-k+1}+{i \choose 0}a^0b^{i+1}+$

$\sum_{k=1}^i {i \choose k}a^kb^{i-k+1}=a^{i+1}+b^{i+1}+\sum_{k=1}^i\left({i \choose k-1}+{i \choose k}\right)a^kb^{i-k+1}=$

$a^{i+1}+b^{i+1}+\sum_{k=1}^{i} {i+1 \choose k}a^kb^{i-k+1}=\sum_{k=0}^{i+1} {i+1 \choose k}a^kb^{i-k+1}$

[עריכה] המקרה הכללי

[עריכה] דוגמאות

עבור r=1/2, מתקבלת הנוסחה השימושית:

$\ (1+x) ^ \frac{1}{2} = \sqrt{1+x} = 1 + \frac{1}{2} x - \frac{1}{8} x^2 +\dots$

עבור r=-1 מתקבל הטור הגאומטרי: $\ (1+x)^{-1} = \frac{1}{1+x} = 1 - x + x^2 - x^3 + \dots$

[עריכה] הוכחה

הוכחת הנוסחה נעשית באמצעות פיתוח טור טיילור עבור הפונקציה המרוכבת $\ f(z) = (1+z)^r$ , והצבה $\ z=\frac{x}{y}$ .

מקור: http://he.wikipedia.org../../../%D7%94/%D7%91/%D7%99/%D7%94%D7%91%D7%99%D7%A0%D7%95%D7%9D_%D7%A9%D7%9C_%D7%A0%D7%99%D7%95%D7%98%D7%95%D7%9F.html

קטגוריות: אלגברה | קומבינטוריקה

הבינום של ניוטון

מתוך ויקיפדיה, האנציקלופדיה החופשית

תוכן עניינים

[עריכה] הבינום הרגיל

[עריכה] דוגמה

[עריכה] הוכחה

[עריכה] הוכחה באינדוקציה

[עריכה] המקרה הכללי

[עריכה] דוגמאות

[עריכה] הוכחה

Views

ניווט

קהילה

חיפוש

שפות אחרות