Relações de recorrência de coeficientes binomiais no triângulo de Pascal
Triângulo de Pascal, linhas de 0 a 7. A identidade do taco de hóquei confirma, por exemplo: para
n = 6,
r = 2: 1 + 3 + 6 + 10 + 15 = 35.
Na matemática combinatória , a identidade
∑
eu
=
r
n
(
eu
r
)
=
(
n
+
1
r
+
1
)
para
n
,
r
∈
N
,
n
≥
r
{\ displaystyle \ sum _ {i = r} ^ {n} {i \ escolher r} = {n + 1 \ escolher r + 1} \ qquad {\ text {para}} n, r \ in \ mathbb {N }, \ quad n \ geq r}
ou equivalentemente, a imagem no espelho pela substituição :
j
→
eu
-
r
{\ displaystyle j \ to ir}
∑
j
=
0
n
-
r
(
j
+
r
r
)
=
∑
j
=
0
n
-
r
(
j
+
r
j
)
=
(
n
+
1
n
-
r
)
para
n
,
r
∈
N
,
n
≥
r
{\ displaystyle \ sum _ {j = 0} ^ {nr} {j + r \ escolher r} = \ sum _ {j = 0} ^ {nr} {j + r \ escolher j} = {n + 1 \ escolha nr} \ qquad {\ text {para}} n, r \ in \ mathbb {N}, \ quad n \ geq r}
é conhecida como a identidade do taco de hóquei ou meia de Natal . O nome deriva da representação gráfica da identidade no triângulo de Pascal : quando os adendos representados na soma e a própria soma são destacados, a forma revelada lembra vagamente aqueles objetos (ver taco de hóquei , meia de Natal ).
Provas As provas indutivas e algébricas fazem uso da identidade de Pascal :
(
n
k
)
=
(
n
-
1
k
-
1
)
+
(
n
-
1
k
)
.
{\ displaystyle {n \ escolha k} = {n-1 \ escolha k-1} + {n-1 \ escolha k}.}
Prova indutiva Esta identidade pode ser comprovada por indução matemática on .
n
{\ displaystyle n}
Caso base
Let ;
n
=
r
{\ displaystyle n = r}
∑
eu
=
r
n
(
eu
r
)
=
∑
eu
=
r
r
(
eu
r
)
=
(
r
r
)
=
1
=
(
r
+
1
r
+
1
)
=
(
n
+
1
r
+
1
)
.
{\ displaystyle \ sum _ {i = r} ^ {n} {i \ escolher r} = \ sum _ {i = r} ^ {r} {i \ escolher r} = {r \ escolher r} = 1 = {r + 1 \ escolha r + 1} = {n + 1 \ escolha r + 1}.}
Passo indutivo
Suponha, para alguns ,
k
∈
N
,
k
⩾
r
{\ displaystyle k \ in \ mathbb {N}, k \ geqslant r}
∑
eu
=
r
k
(
eu
r
)
=
(
k
+
1
r
+
1
)
{\ displaystyle \ sum _ {i = r} ^ {k} {i \ escolher r} = {k + 1 \ escolher r + 1}}
Então
∑
eu
=
r
k
+
1
(
eu
r
)
=
(
∑
eu
=
r
k
(
eu
r
)
)
+
(
k
+
1
r
)
=
(
k
+
1
r
+
1
)
+
(
k
+
1
r
)
=
(
k
+
2
r
+
1
)
.
{\ displaystyle \ sum _ {i = r} ^ {k + 1} {i \ escolher r} = \ esquerda (\ sum _ {i = r} ^ {k} {i \ escolher r} \ direita) + { k + 1 \ escolha r} = {k + 1 \ escolha r + 1} + {k + 1 \ escolha r} = {k + 2 \ escolha r + 1}.}
Prova algébrica Usamos um argumento telescópico para simplificar o cálculo da soma:
∑
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
por telescopagem
=
(
n
+
1
k
+
1
)
.
{\ displaystyle {\ begin {alinhados} \ 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 = \ cor {verde} {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 {telescopando}} \\ & = {\ binom {n + 1} {k + 1}}. \ end {alinhado}}}
Imagine que estejamos distribuindo doces indistinguíveis para crianças distintas. Por uma aplicação direta do método de estrelas e barras , existem
n
{\ displaystyle n}
k
{\ displaystyle k}
(
n
+
k
-
1
k
-
1
)
{\ displaystyle {\ binom {n + k-1} {k-1}}}
maneiras de fazer isso. Alternativamente, podemos primeiro dar doces ao filho mais velho para que estejamos essencialmente dando doces às crianças e, novamente, com estrelas e barras e contagem dupla , temos
0
⩽
eu
⩽
n
{\ displaystyle 0 \ leqslant i \ leqslant n}
n
-
eu
{\ displaystyle ni}
k
-
1
{\ displaystyle k-1}
(
n
+
k
-
1
k
-
1
)
=
∑
eu
=
0
n
(
n
+
k
-
2
-
eu
k
-
2
)
,
{\ displaystyle {\ binom {n + k-1} {k-1}} = \ sum _ {i = 0} ^ {n} {\ binom {n + k-2-i} {k-2}} ,}
que simplifica para o resultado desejado tomando e , e observando que :
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
)
=
∑
eu
=
0
n
(
n
′
-
eu
r
)
=
∑
eu
=
r
n
′
(
eu
r
)
.
{\ displaystyle {\ binom {n '+ 1} {r + 1}} = \ sum _ {i = 0} ^ {n} {\ binom {n'-i} {r}} = \ sum _ {i = r} ^ {n '} {\ binom {i} {r}}.}
Outra prova combinatória Podemos formar um comitê de tamanho de um grupo de pessoas em
k
+
1
{\ displaystyle k + 1}
n
+
1
{\ displaystyle n + 1}
(
n
+
1
k
+
1
)
{\ displaystyle {\ binom {n + 1} {k + 1}}}
maneiras. Agora distribuímos os números para as pessoas. Podemos dividir isso em casos separados. Em geral, no caso de , pessoa está no comitê e pessoas não estão no comitê. Isso pode ser feito em
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}}}
maneiras. Agora podemos somar os valores desses casos disjuntos, obtendo
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}}.}
Veja também Referências links externos
<img src="https://en.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">
![{\ displaystyle {\ begin {alinhados} \ 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 = \ cor {verde} {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 {telescopando}} \\ & = {\ binom {n + 1} {k + 1}}. \ end {alinhado}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9ce84ab741d7707c5b7c8fd325a2db456d91c14c)
