Identitatea crosei de hochei

							1
						1		1
					1		2		1
				1		3		3		1
			1		4		6		4		1
		1		5		10		10		5		1
	1		6		15		20		15		6		1
1		7		21		35		35		21		7		1
Triunghiul lui Pascal, rândurile de la 0 la 7. Identitatea crosei de hochei confirmă că, de exemplu pentru n=6, r=2, 1+3+6+10+15=35.

În combinatorică identitatea:

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

pentru $n,r\in \mathbb {N} ,\ n\geq r,$ sau echivalent, imaginea în oglindă prin substituția $j\to i-r$ :

\sum _{j=0}^{n-r}{j+r \choose r}=\sum _{j=0}^{n-r}{j+r \choose j}={n+1 \choose n-r}

pentru $n,r\in \mathbb {N} ,\ n\geq r$ este cunoscută drept crosă de hochei,^[1] Denumirea provine din reprezentarea grafică a identității pe triunghiul lui Pascal: când sunt evidențiați termenii sumați și suma însăși, forma care apare amintește vag de o crosă de hochei.

Demonstrații

Generarea demonstrației funcției

Fie

X^{r}+X^{r+1}+\dots +X^{n}={\frac {X^{r}-X^{n+1}}{1-X}}

și $X=1+x$ , și se compară coeficienții lui $x^{r}$ .

Demonstrații inductive și algebrice

Atât demonstrațiile inductive, cât și cele algebrice folosesc formula lui Pascal:

{n \choose k}={n-1 \choose k-1}+{n-1 \choose k}.

Demonstrație inductivă

Această identitate poate fi demonstrată prin inducție matematică pe $n$ .

Cazul inițial: fie $n=r$ ;

\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}.

Pasul inductiv: se presupune că pentru un $k\in \mathbb {N} ,k\geqslant r$ ,

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

Atunci

\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}.

Demonstrație algebrică

Se folosește un argument telescopic^⁠(d) pentru a simplifica calculul sumei:

{\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{prin telescopare}}\\&={\binom {n+1}{k+1}}.\end{aligned}}

Demonstrații combinatorice

Prima demonstrație

Se presupune că se distribuie $n$ bomboane care nu se pot individualiza la $k$ copii care se individualizează. Aplicând direct metoda stele și bare^⁠(d), se obțin

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

moduri de a face asta. Ca alternativă, mai întâi se pot oferi $0\leqslant i\leqslant n$ bomboane celui mai mare, astfel încât, în esență, să se dea $n-i$ bomboane la $k-1$ copii, și din nou cu stele și bare și dubla numărare^⁠(d), se obține

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

care se simplifică la rezultatul dorit luând $n'=n+k-2$ și $r=k-2$ și observând că $n'-n=k-2=r$ :

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

A doua demonstrație

se poate forma un comitet de mărimea $k+1$ dintr-un grup de $n+1$ oameni în

{\binom {n+1}{k+1}}

moduri.

Acum se distribuie numerele $1,2,3,\dots ,n-k+1$ la $n-k+1$ din cei $n+1$ oameni. Se poate diviza asta în $n-k+1$ cazuri disjuncte. În general, în cazul în care $x$ , $1\leqslant x\leqslant n-k+1$ , persoana $x$ este în comitet, iar persoanele $1,2,3,\dots ,x-1$ nu sunt în comitet. Acest lucru se poate face în