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

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

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

הנוסחה בצורתה הבסיסית היא: (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}.