אני מנסה להוכיח את הזהות הבאה בצורה אלגברית:
\sum_{k=4}^{n}{n \choose k}{k \choose 3}={n \choose 3}(2^{n-3}-1)
ניסיתי להשתמש בבינום של ניוטון אבל ללא הצלחה.
אשמח להכוונה כיצד להוכיח את הזהות הנ"ל בצורה אלגברית.
תודה רבה.
כדי להוכיח את הזהות בצורה אלגברית, נשתמש בזהות הבאה:
\binom{n}{k}\binom{k}{j}=\binom{n}{j}\binom{n-j}{k-j}
לכן נקבל:
{n \choose k}{k \choose 3}={n \choose 3}{n-3 \choose k-3}
כמו כן, נשים לב כי מתקיים:
\sum_{k=4}^{n}{n-3 \choose k-3}=-1+\sum_{k=3}^{n}{n-3 \choose k-3}=-1+\sum_{k=0}^{n-3}{n-3 \choose k}
בנוסף לכך, ע"פ הבינום של ניוטון מתקיים:
\sum_{k=0}^{n-3}{n-3 \choose k}=2^{n-3}
בסה"כ, נשלב את המעברים ונקבל:
\begin{align*}
\sum_{k=4}^{n}{n \choose k}{k \choose 3}&=\sum_{k=4}^{n}{n \choose 3}{n-3 \choose k-3}={n \choose 3}\sum_{k=4}^{n}{n-3 \choose k-3}\\&={n \choose 3}\left(-1+\sum_{k=3}^{n}{n-3 \choose k-3}\right)={n \choose 3}\left(-1+\sum_{k=0}^{n-3}{n-3 \choose k}\right)\\&={n \choose 3}(2^{n-3}-1)
\end{align*}
כנדרש.