Vizualizare sursă pentru „Identitatea crosei de hochei”

{| style="margin:0 0 0 1.5em; width:300px; float:right; text-align:center;"
|-
| || || || || || || || 1
|-
| || || || || || || 1 || || 1
|-
| || || || || || 1 || || 2 || || bgcolor="#c0f0a0"|1
|-
| || || || || 1 || || 3 || || bgcolor="#c0f0a0"|3 || || 1
|-
| || || || 1 || || 4 || || bgcolor="#c0f0a0"|6 || || 4 || || 1
|-
| || || 1 || || &nbsp;5&nbsp; || || bgcolor="#c0f0a0"|10 || || 10 || || &nbsp;5&nbsp; || || 1
|-
| || 1 || || &nbsp;6&nbsp; || || bgcolor="#c0f0a0"|15 || || 20 || || 15 || || &nbsp;6&nbsp;  || || 1
|-
| &nbsp;1&nbsp; || || &nbsp;7&nbsp; || || 21 || || bgcolor="#f0c0a0"|35 || || 35 || || 21 || || &nbsp;7&nbsp; || || &nbsp;1&nbsp;
|-
| colspan=15|[[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:
:<math>\sum^n_{i=r}{i\choose r}={n+1\choose r+1}</math>
pentru <math>n,r\in\mathbb{N}, \ n\geq r,</math> sau echivalent, imaginea în oglindă prin substituția <math>j\to i-r</math>:
:<math>\sum^{n-r}_{j=0}{j+r\choose r}=\sum^{n-r}_{j=0}{j+r\choose j}={n+1\choose n-r}</math>
pentru <math>n,r\in\mathbb{N}, \ n\geq r</math> este cunoscută drept '''crosă de hochei''',<ref>{{en icon}} C.H. Jones (1996) ''Generalized Hockey Stick Identities and N-Dimensional Block Walking.'', ''Fibonacci Quarterly'' '''34'''(3), 280-288.</ref> 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
:<math>X^r + X^{r+1} + \dots + X^{n} = \frac{X^r-X^{n+1}}{1-X}</math>
și <math>X=1+x</math>, și se compară coeficienții lui <math>x^r</math>.

=== Demonstrații inductive și algebrice ===
Atât demonstrațiile inductive, cât și cele algebrice folosesc [[formula lui Pascal]]:
:<math>{n \choose k}={n-1\choose k-1}+{n-1\choose k}.</math>

==== Demonstrație inductivă ====
Această identitate poate fi demonstrată prin [[inducție matematică]] pe {{mvar|n}}.

Cazul inițial: fie <math>n=r</math>;
:<math>\sum^n_{i=r} {i\choose r} = \sum^r_{i=r}{i\choose r}={r\choose r} = 1 = {r+1\choose r+1} = {n+1\choose r+1}. </math>

Pasul inductiv: se presupune că pentru un <math>k\in\mathbb{N}, k \geqslant r</math>,
:<math>\sum^k_{i=r}{i\choose r}={k+1\choose r+1}</math>

Atunci
:<math>\sum^{k+1}_{i=r} {i\choose r} = \left(\sum^k_{i=r} {i\choose r} \right) + {k+1\choose r}={k+1\choose r+1}+{k+1\choose r}={k+2\choose r+1}.</math>

==== Demonstrație algebrică ====
Se folosește un argument {{ill-wd| Q2164293||telescopic}} pentru a simplifica calculul sumei:
:<math>
\begin{align}
\sum_{t=\color{blue}0}^n \binom{t}{k} 
=\sum_{t=\color{blue}k}^n\binom tk
&= \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{align}
</math>

=== Demonstrații combinatorice ===
====Prima demonstrație ====
Se presupune că se distribuie <math>n</math> bomboane care nu se pot individualiza la <math>k</math> copii care se individualizează. Aplicând direct {{ill-wd| Q7602343||metoda stele și bare}}, se obțin
:<math>\binom{n+k-1}{ k-1}</math>
moduri de a face asta. Ca alternativă, mai întâi se pot oferi <math>0\leqslant i\leqslant n</math> bomboane celui mai mare, astfel încât, în esență, să se dea <math>n-i</math> bomboane la <math>k-1</math> copii, și din nou cu stele și bare și {{ill-wd| Q1191750||dubla numărare}}, se obține
:<math>\binom{n+k-1}{ k-1}=\sum_{i=0}^n\binom{n+k-2-i}{k-2},</math>
care se simplifică la rezultatul dorit luând <math>n' = n+k-2</math> și <math>r=k-2</math> și observând că <math>n'-n = k- 2=r</math>:
:<math>\binom{n'+1}{ r+1}=\sum_{i=0}^n \binom {n'-i}r = \sum_{i=r}^{n'} \binom {i}r .</math>

==== A doua demonstrație ====
se poate forma un comitet de mărimea <math>k+1</math> dintr-un grup de <math>n+1</math> oameni în
:<math> \binom{n+1}{k+1}</math>
moduri.

Acum se distribuie numerele <math>1,2,3,\dots,n-k+1</math> la <math>n-k+1</math> din cei <math>n+1</math> oameni. Se poate diviza asta în <math>n-k+1</math> cazuri disjuncte. În general, în cazul în care <math>x</math>, <math>1\leqslant x\leqslant n-k+1</math>, persoana <math>x</math> este în comitet, iar persoanele <math>1,2,3,\dots, x-1</math> nu sunt în comitet. Acest lucru se poate face în
:<math>\binom{n-x+1}{k}</math>
moduri. Acum se pot însuma valorile acestor <math>n-k+1</math> cazuri disjuncte, obținând
:<math> \binom{n+1}{k+1} = \binom n k + \binom {n-1} k + \binom{n-2} k + \cdots + \binom{k+1} k+ \binom k k.</math>

== Note ==
<references responsive/>

== Legături externe ==
* {{en icon}} [http://artofproblemsolving.com/wiki/index.php?title=Combinatorial_identity#Hockey-Stick_Identity On AOPS]
* {{en icon}} [https://math.stackexchange.com/q/1490794 On StackExchange, Mathematics]
* {{en icon}} [https://forums.dyalog.com/viewtopic.php?f=30&t=1650 ''Pascal's Ladder'' on the Dyalog Chat Forum]

{{Portal|Matematică}}

[[Categorie:Combinatorică]]
[[Categorie:Subiecte factoriale și binomiale]]
[[Categorie:Articole care conțin demonstrații]]