עלי להוכיח בעזרת אינדוקציה, כי לכל n,m,k\geq 0 מתקיים:
\sum_{i=0}^{k}{m \choose i}{n \choose k-i}={n+m \choose k}
כמו כן, נראה כיאלו אני צריך להשתמש במשולש פסקל אבל אני לא בטוח איך ואיפה.
כיצד עלי לגשת לשאלות כאלה?
נוכיח את הזהות באינדוקציה על 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+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}
כנדרש.
לייק 1