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

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

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

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

[עריכה] נוסחת הבינום

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

הנוסחה תקפה לכל 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)^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}$ .

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

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

תוכן עניינים

[עריכה] נוסחת הבינום

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

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

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

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

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

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

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

צפיות

כלים אישיים

חיפוש

ניווט

קהילה

תיבת כלים

שפות אחרות