هوية عصا الهوكي

يمكن إثبات هذه المتطابقة بالاستقراء الرياضي على${\displaystyle n}$.

الحالة الأساسية لي${\displaystyle n=r}$;

${\displaystyle \sum _{i=r}^{n}{i \choose r}=\sum _{i=r}^{r}{i \choose r}={r \choose r}=1={r+1 \choose r+1}={n+1 \choose r+1}.}$

الخطوة الاستقرائية : لنفترض، لبعض${\displaystyle k\in \mathbb {N} ,k\geqslant r}$،

${\displaystyle \sum _{i=r}^{k}{i \choose r}={k+1 \choose r+1}}$

ثم

${\displaystyle \sum _{i=r}^{k+1}{i \choose r}=\left(\sum _{i=r}^{k}{i \choose r}\right)+{k+1 \choose r}={k+1 \choose r+1}+{k+1 \choose r}={k+2 \choose r+1}.}$

نستخدم حجة التلسكوب لتبسيط حساب المجموع:

$\begin{aligned}\sum _{t=\color {blue}0}^{n}{\binom {t}{k}}=\sum _{t=\color {blue}k}^{n}{\binom {t}{k}}&=\sum _{t=k}^{n}\left[{\binom {t+1}{k+1}}-{\binom {t}{k+1}}\right]\\&=\sum _{t=\color {green}k}^{\color {green}n}{\binom {\color {green}{t+1}}{k+1}}-\sum _{t=k}^{n}{\binom {t}{k+1}}\\&=\sum _{t=\color {green}{k+1}}^{\color {green}{n+1}}{\binom {\color {green}{t}}{k+1}}-\sum _{t=k}^{n}{\binom {t}{k+1}}\\&={\binom {n+1}{k+1}}-\underbrace {\binom {k}{k+1}} _{0}&&{\text{بالتلسكوب}}\\&={\binom {n+1}{k+1}}.\end{aligned}}}$

تخيل أننا نقوم بالتوزيع${\displaystyle n}$حلوى لا يمكن تمييزها${\displaystyle k}$أطفال مميزون. من خلال تطبيق مباشر لطريقة النجوم والخطوط ، هناك

${\displaystyle {\binom {n+k-1}{k-1}}}$

هناك طرق للقيام بذلك. أو بدلاً من ذلك، يمكننا أولاً أن نقدم${\displaystyle 0\leqslant i\leqslant n}$نعطي الحلوى للطفل الأكبر سناً، بحيث نكون في الأساس نعطي${\displaystyle ni}$حلوى لـ${\displaystyle k-1}$ومرة أخرى، مع النجوم والخطوط والعد المزدوج ، لدينا

${\displaystyle {\binom {n+k-1}{k-1}}=\sum _{i=0}^{n}{\binom {n+k-2-i}{k-2}},}$

والذي يتبسط إلى النتيجة المرجوة عن طريق أخذ${\displaystyle n'=n+k-2}$و${\displaystyle r=k-2}$ولاحظ ذلك${\displaystyle n'-n=k-2=r}$:

${\displaystyle {\binom {n'+1}{r+1}}=\sum _{i=0}^{n}{\binom {n'-i}{r}}=\sum _{i=r}^{n'}{\binom {i}{r}}.}$

عد${\displaystyle (k+1)}$مجموعات فرعية من عناصر المجموعة${\displaystyle \{1,2,\ldots ,n+1\}}$بطريقتين.

من الواضح أن${\displaystyle {\binom {n+1}{k+1}}}$هذه المجموعات الفرعية إجمالاً.

أو بدلاً من ذلك، قسّم هذه المجموعات الفرعية وفقًا لأكبر عنصر فيها. إذا كان أكبر عنصر هو${\displaystyle r+1}$، أين${\displaystyle k\leq r\leq n}$ثم الباقي${\displaystyle k}$يجب اختيار العناصر من${\displaystyle \{1,2,\ldots ,r\}}$، وهو ما يمكن القيام به في${\displaystyle {\binom {r}{k}}}$طرق.

لذلك، $${\displaystyle \sum _{r=k}^{n}{\binom {r}{k}}={\binom {n+1}{k+1}}.}$$