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

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

במתמטיקה, הבינום של ניוטון הוא נוסחה לפיתוח חזקות של סכום של שני איברים. אף שהנוסחה קרויה על שמו של ניוטון, היא מיוחסת פעמים רבות לבלז פסקל, שעסק בה במהלך המאה ה-17, אך הייתה ידועה למתמטיקאים שקדמו לו, ובהם הסיני יאנג חווי בן המאה ה-13, הפרסי עומר כיאם בן המאה ה-11, וההודי פינגלה בן המאה ה-3.

נוסחת הבינום

הנוסחה בצורתה הבסיסית היא: $(x+y)^{n}=\sum _{k=0}^{n}{n \choose k}x^{k}y^{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}$.

הנוסחה תקפה לכל r מרוכב, כפי שאפשר לראות באמצעות פיתוח טיילור של הפונקציה $\ (1+x)^{r}$: הטור המתקבל הוא $\ (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+1)}{i!}}$. אם r שלם, רק r+1 המקדמים הראשונים שונים מאפס, והטור הוא למעשה סכום סופי.

הבינום הרגיל

דוגמה

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

$\ (x+y)^{1}=x+y$

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

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

$\ (x+y)^{4}=x^{4}+4x^{3}y+6x^{2}y^{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^{k}y^{j}$ המקדם $\ a$ הוא בדיוק מספר האפשרויות לבחור $\ k$ פעמים את $\ x$ ו-$\ j$ פעמים את $\ y$. מאחר שניתן לבחור רק מתוך שני האיברים הללו, די לבדוק בכמה אפשרויות ניתן לבחור את $\ x$ כי בהכרח מתקיים $\ k+j=n$ (אם בחרנו $\ k$ פעמים את $\ x$, אנחנו חייבים לבחור $\ n-k$ פעמים את $\ y$, כי זו האפשרות האחרת היחידה).

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

הוכחה באינדוקציה

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

בדיקה עבור n=1 (ניתן לבדוק גם החל מ-n=0): $(a+b)^{1}=\sum _{k=0}^{1}{1 \choose k}a^{k}b^{1-k}$.

$\sum _{k=0}^{1}{1 \choose k}a^{k}b^{1-k}={1 \choose 0}a^{0}b^{1}+{1 \choose 1}a^{1}b^{0}=b+a$.

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

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

הוכחה:

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

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

$\sum _{k=0}^{i}{i \choose k}a^{k+1}b^{i-k}+\sum _{k=0}^{i}{i \choose k}a^{k}b^{i-k+1}=\sum _{k=1}^{i+1}{i \choose k-1}a^{k}b^{i-k+1}+$

$\sum _{k=0}^{i}{i \choose k}a^{k}b^{i-k+1}={i \choose i}a^{i+1}b^{0}+\sum _{k=1}^{i}{i \choose k-1}a^{k}b^{i-k+1}+{i \choose 0}a^{0}b^{i+1}+$

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

$a^{i+1}+b^{i+1}+\sum _{k=1}^{i}{i+1 \choose k}a^{k}b^{i-k+1}=\sum _{k=0}^{i+1}{i+1 \choose k}a^{k}b^{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}}$.

קישורים חיצוניים

גדי אלכסנדרוביץ', הבינום של ניוטון, באתר "לא מדויק",