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, 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

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

moduri. Acum se pot însuma valorile acestor $n-k+1$ cazuri disjuncte, obținând

${\binom {n+1}{k+1}}={\binom {n}{k}}+{\binom {n-1}{k}}+{\binom {n-2}{k}}+\cdots +{\binom {k+1}{k}}+{\binom {k}{k}}.$

Legături externe

• en On AOPS
• en On StackExchange, Mathematics
• en Pascal's Ladder on the Dyalog Chat Forum