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} (\binom{i}{r}) = (\binom{n + 1}{r + 1})

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

\sum_{j = 0}^{n - r} (\binom{j + r}{r}) = \sum_{j = 0}^{n - r} (\binom{j + r}{j}) = (\binom{n + 1}{n - r})

pentru $n, r \in ℕ, 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:

(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k}) .

Demonstrație inductivă

Această identitate poate fi demonstrată prin inducție matematică pe Format:Mvar.

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

\sum_{i = r}^{n} (\binom{i}{r}) = \sum_{i = r}^{r} (\binom{i}{r}) = (\binom{r}{r}) = 1 = (\binom{r + 1}{r + 1}) = (\binom{n + 1}{r + 1}) .

Pasul inductiv: se presupune că pentru un $k \in ℕ, k ⩾ r$ ,

\sum_{i = r}^{k} (\binom{i}{r}) = (\binom{k + 1}{r + 1})

Atunci

\sum_{i = r}^{k + 1} (\binom{i}{r}) = (\sum_{i = r}^{k} (\binom{i}{r})) + (\binom{k + 1}{r}) = (\binom{k + 1}{r + 1}) + (\binom{k + 1}{r}) = (\binom{k + 2}{r + 1}) .

Demonstrație algebrică

Se folosește un argument Format:Ill-wd pentru a simplifica calculul sumei:

\begin{matrix} \sum_{t = 0}^{n} (\binom{t}{k}) = \sum_{t = k}^{n} (\binom{t}{k}) & = \sum_{t = k}^{n} [(\binom{t + 1}{k + 1}) - (\binom{t}{k + 1})] \\ = \sum_{t = k}^{n} (\binom{t + 1}{k + 1}) - \sum_{t = k}^{n} (\binom{t}{k + 1}) \\ = \sum_{t = k + 1}^{n + 1} (\binom{t}{k + 1}) - \sum_{t = k}^{n} (\binom{t}{k + 1}) \\ = (\binom{n + 1}{k + 1}) - \underset{0}{\underset{⏟}{(\binom{k}{k + 1})}} & prin telescopare \\ = (\binom{n + 1}{k + 1}) . \end{matrix}

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 Format:Ill-wd, se obțin

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

moduri de a face asta. Ca alternativă, mai întâi se pot oferi $0 ⩽ i ⩽ 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 Format:Ill-wd, 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 ⩽ x ⩽ 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}) + \dots + (\binom{k + 1}{k}) + (\binom{k}{k}) .

Note

↑ Format:En icon C.H. Jones (1996) Generalized Hockey Stick Identities and N-Dimensional Block Walking., Fibonacci Quarterly 34(3), 280-288.

Legături externe

Format:Portal

[1] Format:En icon C.H. Jones (1996) Generalized Hockey Stick Identities and N-Dimensional Block Walking., Fibonacci Quarterly 34(3), 280-288.

[1]

Identitatea crosei de hochei

Cuprins

Demonstrații

Generarea demonstrației funcției

Demonstrații inductive și algebrice

Demonstrație inductivă

Demonstrație algebrică

Demonstrații combinatorice

Prima demonstrație

A doua demonstrație

Note

Legături externe

Meniu de navigare

Identitatea crosei de hochei

Demonstrații

Generarea demonstrației funcției

Demonstrații inductive și algebrice

Demonstrație inductivă

Demonstrație algebrică

Demonstrații combinatorice

Prima demonstrație

A doua demonstrație

Note

Legături externe

Meniu de navigare

Căutare