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:
∑
i
=
r
n
(
i
r
)
=
(
n
+
1
r
+
1
)
{\displaystyle \sum _{i=r}^{n}{i \choose r}={n+1 \choose r+1}}
pentru
n
,
r
∈
N
,
n
≥
r
,
{\displaystyle n,r\in \mathbb {N} ,\ n\geq r,}
j
→
i
−
r
{\displaystyle j\to i-r}
∑
j
=
0
n
−
r
(
j
+
r
r
)
=
∑
j
=
0
n
−
r
(
j
+
r
j
)
=
(
n
+
1
n
−
r
)
{\displaystyle \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
∈
N
,
n
≥
r
{\displaystyle n,r\in \mathbb {N} ,\ n\geq r}
crosă de hochei ,[ 1] 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 .
Fie
X
r
+
X
r
+
1
+
⋯
+
X
n
=
X
r
−
X
n
+
1
1
−
X
{\displaystyle X^{r}+X^{r+1}+\dots +X^{n}={\frac {X^{r}-X^{n+1}}{1-X}}}
și
X
=
1
+
x
{\displaystyle X=1+x}
x
r
{\displaystyle x^{r}}
Atât demonstrațiile inductive, cât și cele algebrice folosesc formula lui Pascal :
(
n
k
)
=
(
n
−
1
k
−
1
)
+
(
n
−
1
k
)
.
{\displaystyle {n \choose k}={n-1 \choose k-1}+{n-1 \choose k}.}
Această identitate poate fi demonstrată prin inducție matematică pe n .
Cazul inițial: fie
n
=
r
{\displaystyle n=r}
∑
i
=
r
n
(
i
r
)
=
∑
i
=
r
r
(
i
r
)
=
(
r
r
)
=
1
=
(
r
+
1
r
+
1
)
=
(
n
+
1
r
+
1
)
.
{\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}.}
Pasul inductiv: se presupune că pentru un
k
∈
N
,
k
⩾
r
{\displaystyle k\in \mathbb {N} ,k\geqslant r}
∑
i
=
r
k
(
i
r
)
=
(
k
+
1
r
+
1
)
{\displaystyle \sum _{i=r}^{k}{i \choose r}={k+1 \choose r+1}}
Atunci
∑
i
=
r
k
+
1
(
i
r
)
=
(
∑
i
=
r
k
(
i
r
)
)
+
(
k
+
1
r
)
=
(
k
+
1
r
+
1
)
+
(
k
+
1
r
)
=
(
k
+
2
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}.}
Se folosește un argument telescopic (d
∑
t
=
0
n
(
t
k
)
=
∑
t
=
k
n
(
t
k
)
=
∑
t
=
k
n
[
(
t
+
1
k
+
1
)
−
(
t
k
+
1
)
]
=
∑
t
=
k
n
(
t
+
1
k
+
1
)
−
∑
t
=
k
n
(
t
k
+
1
)
=
∑
t
=
k
+
1
n
+
1
(
t
k
+
1
)
−
∑
t
=
k
n
(
t
k
+
1
)
=
(
n
+
1
k
+
1
)
−
(
k
k
+
1
)
⏟
0
prin telescopare
=
(
n
+
1
k
+
1
)
.
{\displaystyle {\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}}}
Se presupune că se distribuie
n
{\displaystyle n}
k
{\displaystyle k}
metoda stele și bare (d
(
n
+
k
−
1
k
−
1
)
{\displaystyle {\binom {n+k-1}{k-1}}}
moduri de a face asta. Ca alternativă, mai întâi se pot oferi
0
⩽
i
⩽
n
{\displaystyle 0\leqslant i\leqslant n}
n
−
i
{\displaystyle n-i}
k
−
1
{\displaystyle k-1}
dubla numărare (d
(
n
+
k
−
1
k
−
1
)
=
∑
i
=
0
n
(
n
+
k
−
2
−
i
k
−
2
)
,
{\displaystyle {\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
{\displaystyle n'=n+k-2}
r
=
k
−
2
{\displaystyle r=k-2}
n
′
−
n
=
k
−
2
=
r
{\displaystyle n'-n=k-2=r}
(
n
′
+
1
r
+
1
)
=
∑
i
=
0
n
(
n
′
−
i
r
)
=
∑
i
=
r
n
′
(
i
r
)
.
{\displaystyle {\binom {n'+1}{r+1}}=\sum _{i=0}^{n}{\binom {n'-i}{r}}=\sum _{i=r}^{n'}{\binom {i}{r}}.}
se poate forma un comitet de mărimea
k
+
1
{\displaystyle k+1}
n
+
1
{\displaystyle n+1}
(
n
+
1
k
+
1
)
{\displaystyle {\binom {n+1}{k+1}}}
moduri.
Acum se distribuie numerele
1
,
2
,
3
,
…
,
n
−
k
+
1
{\displaystyle 1,2,3,\dots ,n-k+1}
n
−
k
+
1
{\displaystyle n-k+1}
n
+
1
{\displaystyle n+1}
n
−
k
+
1
{\displaystyle n-k+1}
x
{\displaystyle x}
1
⩽
x
⩽
n
−
k
+
1
{\displaystyle 1\leqslant x\leqslant n-k+1}
x
{\displaystyle x}
1
,
2
,
3
,
…
,
x
−
1
{\displaystyle 1,2,3,\dots ,x-1}
(
n
−
x
+
1
k
)
{\displaystyle {\binom {n-x+1}{k}}}
moduri. Acum se pot însuma valorile acestor
n
−
k
+
1
{\displaystyle n-k+1}
(
n
+
1
k
+
1
)
=
(
n
k
)
+
(
n
−
1
k
)
+
(
n
−
2
k
)
+
⋯
+
(
k
+
1
k
)
+
(
k
k
)
.
{\displaystyle {\binom {n+1}{k+1}}={\binom {n}{k}}+{\binom {n-1}{k}}+{\binom {n-2}{k}}+\cdots +{\binom {k+1}{k}}+{\binom {k}{k}}.}
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/08305fb20448113afa66dcc3a0f6a080b2894f7f)
