Ensino Superior ⇒ Análise Combinatória

[gab1234]

Sejam n e r números inteiros positivos em que 1<= r <= n-1 prove que:
C(n,r) = C(n-1,r-1) + C(n-1,r)

[Idocrase]

[tex3]C^{r-1}_{n-1}=\frac{(n-1)!}{(r-1)!(n-r)!}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]C^{r-1}_{n-1}=\frac{(n-1)!}{(r-1)!(n-r)!}[/tex3]

[tex3]C^{r}_{n-1}=\frac{(n-1)!}{r!(n-r-1)!}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]C^{r}_{n-1}=\frac{(n-1)!}{r!(n-r-1)!}[/tex3]

Somando as duas expressões, temos:

[tex3]C^{r-1}_{n-1}+C^{r}_{n-1}=\frac{(n-1)!}{(r-1)!(n-r)!}+\frac{(n-1)!}{r!(n-r-1)!}=\frac{(n-1)!}{(r-1)!(n-r)(n-r-1)!}+\frac{(n-1)!}{r(r-1)!(n-r-1)!}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]C^{r-1}_{n-1}+C^{r}_{n-1}=\frac{(n-1)!}{(r-1)!(n-r)!}+\frac{(n-1)!}{r!(n-r-1)!}=\frac{(n-1)!}{(r-1)!(n-r)(n-r-1)!}+\frac{(n-1)!}{r(r-1)!(n-r-1)!}[/tex3]

Agora, vamos encontrar um denominador comum:

[tex3]C^{r-1}_{n-1}+C^{r}_{n-1}=\frac{r(n-1)!+(n-r)(n-1)!}{r(r-1)!(n-r)(n-r-1)!}=\frac{(n-1)!(\cancel r+n-\cancel r)}{r!(n-r)!}=\frac{(n-1)!n}{r!(n-r)!}=\frac{n!}{r!(n-r!)}=C^r_n[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]C^{r-1}_{n-1}+C^{r}_{n-1}=\frac{r(n-1)!+(n-r)(n-1)!}{r(r-1)!(n-r)(n-r-1)!}=\frac{(n-1)!(\cancel r+n-\cancel r)}{r!(n-r)!}=\frac{(n-1)!n}{r!(n-r)!}=\frac{n!}{r!(n-r!)}=C^r_n[/tex3]