סדרת אתגרים במתמטיקה - אתגר שני

[Zeta]

אתגר שני במתמטיקה של פורום SolX

ברוכים הבאים לאתגר השני בסדרת אתגרים במתמטיקה. הזוכה של שבוע שעבר הוא @Gilad אשר סיפק הוכחה מצויינת לפתרון. אנחנו שמחים שהיו פתרונות רבים לבעיה של שבוע שעבר. כל הכבוד לכל מי שסיפק פתרון לבעיה - הפתרונות של כולם נבדקו ונמצאו נכונים ומפורטים. אם תצליחו למצוא פתרונות נוספים (ויש כאלה), אתם עדיין מוזמנים לפרסם אותם בפוסט של שבוע שעבר.

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

בעיית השבוע: הוכיחו כי לכל n,m,k\geq0 טבעיים מתקיים:

\sum_{i=0}^{k}{m \choose i}{n \choose k-i}={n+m \choose k}

את תשובתכם לשאלה, אתם מוזמנים לפרסם בתגובות של פוסט זה. זכרו כי תשובתיכם צריכה להיות מלאה, מפורטת ולהשתמש ב-\LaTeX. ראו מדריך כיצד להשתמש בכלי כאן.
בהצלחה לכולם!

עריכה: שימו לב כי בפוסט זה הוכחתם את זהות ונדרמונד (Vandermonde’s identity) והיא מכילה הוכחות מתוחכמות ויפות רבות נוספות. אתם מוזמנים לנסות לחשוב עליהם או לחלופין לחפש אותם ברחבי האינטרנט

[Ben]

נוכיח בעזרת קומבינטוריקה, כי לכל n,m,k\geq0 מתקיים:

\sum_{i=0}^{k}{m \choose i}{n \choose k-i}={n+m \choose k}

בעיה: בחירת ועד של k אנשים מתוך m+n אנשים כאשר m גברים ו-n נשים.
צד ימין: לבחירה של k אנשים מתוך m+n אנשים (ללא חזרות ובלי חשיבות לסדר) נקבל:

{n+m \choose k}

צד שמאל: קודם כל נבחר i מתוך m הגברים. את שאר ה-(k-i) נבחר מתוך n הנשים. כלומר קיבלנו {m \choose i}{n \choose k-i}. נסכום את כל האפשרויות כך שנקבל:

\sum_{i=0}^{k}{m \choose i}{n \choose k-i}

מכיוון ששני האגפים פותרים את אותה בעיה, הם שווים זה לזה.

[DanDan]

נוכיח את הזהות באינדוקציה על n\in\mathbb{N} לכל m ו-k.

בסיס האינדוקציה: עבור n=0 ולכל m ו-k, נוכל להסיק כי מתקיים:

\begin{align*} L&=\sum_{i=0}^{k}{m \choose i}{0 \choose k-i}=\sum_{i=0}^{k}{m \choose i}{0 \choose k-i}+{m \choose k}{0 \choose k-k}={m \choose k}\\R&={0+m \choose k}={m \choose k} \end{align*}

צעד האינדוקציה: נניח כי הזהות נכונה עבור n ולכל k ו-m ונוכיח כי היא נכונה עבור n+1:

\begin{align*} \sum_{i=0}^{k}{m \choose i}{n+1 \choose k-i}&\overset{(1)}{=}\sum_{i=0}^{k}{m \choose i}\left[{n \choose k-i-1}+{n \choose k-i}\right]\\&=\sum_{i=0}^{k}{m \choose i}{n \choose k-i-1}+\sum_{i=0}^{k}{m \choose i}{n \choose k-i}\\&=\sum_{i=0}^{k-1}{m \choose i}{n \choose k-i-1}+{n \choose k-k-1}+\sum_{i=0}^{k}{m \choose i}{n \choose k-i}\\&\overset{(2)}{=}{n+m \choose k}+{n+m \choose k-1}\overset{(1)}{=}{n+1+m \choose k} \end{align*}

כאשר המעבר (1) הוא ע"פ זהות פסקל והמעבר (2) הוא ע"פ הנחת האינדוקציה.
הוכחנו כי n,m,k\geq0 מתקיים:

\sum_{i=0}^{k}{m \choose i}{n \choose k-i}={n+m \choose k}

כנדרש.

[Gilad]

נוכיח את הזהות באמצעות הבינום - נתבונן בביטוי (1+x)^{n+m}, כך שנקבל:

\begin{align*} (1+x)^{n+m} &=(1+x)^{n}\cdot(1+x)^{m}\\& \overset{(1)}{=}\left[\sum_{i=0}^{n}{n \choose i}x^{i}\right]\cdot\left[\sum_{j=0}^{m}{m \choose j}x^{j}\right] =\sum_{i=0}^{n}\sum_{j=0}^{m}{n \choose i}{n \choose j}x^{i+j}\\&\overset{(2)}{=}\sum_{s=0}^{n+m}\sum_{j=0}^{s}{n \choose s-j}{m \choose j}x^{s} =\sum_{s=0}^{n+m}\left[\sum_{j=0}^{s}{n \choose k-j}{m \choose j}\right]x^{s} \end{align*}

המעבר הראשון הוא ע"פ הבינום של ניוטון. המעבר השני הוא על-ידי החלפת אינדקסים: s=i+j ו- i=s-j.
אולם, מצד שני, ע"פ הבינום של ניוטון מתקיים:

(1+x)^{n+m}=\sum_{s=0}^{n+m}{n+m \choose s}x^{s}

לכן בסה"כ נקבל:

\sum_{i=0}^{k}{m \choose i}{n \choose k-i}={n+m \choose k}

כנדרש.

[marbd]

נוכיח את הזהות המבוקשת בעזרת חישוב מספר המסלולים על שריג מנקודה O(0,0) לנקודה A(r,n+m-r). מסלול חוקי הוא מסלול שבו כל צעד הוא ימינה או למעלה. נשרטט את השריג:

ישנם {x+y \choose x}={x+y \choose y} מסלולים חוקיים מהנקודה (0,0) אל נקודה כלשהי (x,y). אנו מעוניינים לחשב את המסלולים החוקיים מהנקודה O(0,0) לנקודה A(r,n+m-r). לכן, מצד אחד, מספר המסלולים החוקיים הוא {n+m \choose r}. מצד שני, כל מסלול אל הנקודה A יעבור דרך האלכסון x+y=m בנקודה כלשהי A_1(j,m-j). ישנם {m \choose j} מסלולים מנקודה O אל נקודה A_1. כמו כן, מספר המסלולים מנקודה A_1 אל נקודה A הוא:

{(n+m-r)-(m-j)+(r-j)\choose r-j}={n \choose r-j}

סה"כ נקבל:

\displaystyle {n+m \choose k} = \sum_{j=0}^{k}{n \choose j}{m \choose k-j}