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

מקדם בינומי

ערך מורחב – מקדם בינומי

המקדמים של ${\displaystyle x^{n-k}y^{k}}$ המופיעים בביטויים של נוסחת הבינום הם מספרים שלמים חיוביים המכונה מקדמי הבינום.

לכל ${\displaystyle 0\leq k\leq n}$ נגדיר:

${\displaystyle {n \choose k}={\frac {n!}{k!(n-k)!}}}$

הסימן "!" מציין עצרת, שהיא מכפלת כל המספרים הטבעיים מ-1 ועד למספר נתון.

• כלומר: ${\displaystyle \ n!=1\times 2\times \cdots \times n}$
• ובאופן דומה: ${\displaystyle \ k!=1\times 2\times \cdots \times k}$, ${\displaystyle \ (n-k)!=1\times 2\times \cdots \times (n-k)}$
• כמו כן, ${\displaystyle \ 0!=1}$.

ניתן לכתוב את הנוסחה של מקדם הבינום גם כך:

${\displaystyle {n \choose k}={\frac {n(n-1)\cdots (n-(k-1))}{k!}}={\frac {n(n-1)\cdots (n-k+1)}{k(k-1)\cdots 1}}=\prod _{\ell =1}^{k}{\frac {n-\ell +1}{\ell }}=\prod _{\ell =0}^{k-1}{\frac {n-\ell }{k-\ell }}}$

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

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

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

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

תכונה מעניינת של מקדמי הבינום מתקבלת על ידי הצבה של ${\displaystyle x=y=1}$ בנוסחת הבינום:

${\displaystyle (x+y)^{n}=\sum _{k=0}^{n}{n \choose k}x^{k}y^{n-k}}$

במקרה זה כל החזקות של X ושל Y בבינום הופכות ל-1, וכעת הבינום מבטא למעשה את סכום המקדמים בלבד:

${\displaystyle (2)^{n}=\sum _{k=0}^{n}{n \choose k}}$

ניתן לראות כי סכום המקדמים (כלומר הסכום של כל שורה ושורה במשולש פסקל) יהיה שווה תמיד לחזקה שלמה של 2.

הוכחה קומבינטורית

ראשית, נשים לב כי ${\displaystyle \ (x+y)^{n}=(x+y)\cdot (x+y)\cdot \dots \cdot (x+y)}$. באגף ימין מופיעים ${\displaystyle \ n}$ ביטויים המוכפלים זה בזה. התוצאה היא סכום של כל המכפלות האפשריות שבהן נבחר איבר אחד מכל אחד מהסוגריים. למשל, ${\displaystyle \ (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 מהשניים, וכן הלאה.

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

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

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

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

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

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

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

${\displaystyle {\begin{aligned}(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}\end{aligned}}}$

כאשר השתמשנו בזהות ${\displaystyle {i \choose k-1}+{i \choose k}={i+1 \choose k}}$ ממשולש פסקל. בכך הושלמה הוכחת צעד האינדוקציה.

מ.ש.ל.

המקרה הכללי

ניוטון הראה שלכל r ממשי מתקיים ${\displaystyle \ (1+x)^{r}=\sum _{j=0}^{\infty }{r \choose j}x^{j}}$, כאשר ${\displaystyle \ {r \choose j}={\frac {r(r-1)\cdots (r-j+1)}{j!}}}$. זהו טור אינסופי, המתכנס אל הערך הנכון לכל x, ותקף גם כאשר r מרוכב. את המקרה הכללי אפשר לחשב לפי ${\displaystyle (x+y)^{r}=x^{r}(1+{\tfrac {y}{x}})^{r}}$.

אם r טבעי, רק r+1 המקדמים הראשונים שונים מאפס, והטור הוא למעשה סכום סופי.