Fórum de Matemática | DÚVIDAS? Nós respondemos!
https://forumdematematica.org/

Prove por indução que: ∑ [C(k+i, k)] do i=0 ao i =n-k = C(n+1, k+1) com 0<k<=n
https://forumdematematica.org/viewtopic.php?f=19&t=7486		 Página 1 de 1
Autor:  giovani.desousa [ 30 nov 2014, 03:04 ]
Título da Pergunta:  Prove por indução que: ∑ [C(k+i, k)] do i=0 ao i =n-k = C(n+1, k+1) com 0<k<=n
O problema é o seguinte:
Prove por indução que:
\(\sum_{i=0}^{n-k} C(k+i, k) = C(n+1,k+1)\)
com 0<k<=n

A minha dúvida é como começar a prova, a indução deve ser em qual variável?
Tentei com indução em n-k, mas não consegui montar o passo da indução.
Autor:  Rui Carpentier [ 01 dez 2014, 12:48 ]
Título da Pergunta:  Re: Prove por indução que: ∑ [C(k+i, k)] do i=0 ao i =n-k = C(n+1, k+1) com 0<k<=n  [resolvida]
O melhor é demonstrar por indução em relação à variável n (fixando a variável k).
Neste caso a base de indução seria n=k:
\(\sum_{i=0}^{0}C(k+i,k)=C(k+1,k+1)\)
A hipótese de indução seria:
\(\sum_{i=0}^{n-k}C(k+i,k)=C(n+1,k+1)\)
E a tese de indução seria:
\(\sum_{i=0}^{n+1-k}C(k+i,k)=C(n+2,k+1)\)

Tente resolver desta maneira e diga se consegue ou não.

PS- Pode ser útil usar a identidade de Pascal: C(n+1,k)+C(n+1,k+1)=C(n+2,k+1)
Autor:  giovani.desousa [ 03 dez 2014, 17:39 ]
Título da Pergunta:  Re: Prove por indução que: ∑ [C(k+i, k)] do i=0 ao i =n-k = C(n+1, k+1) com 0<k<=n
Consegui! Obrigado.

A resposta:

Indução em n.

Base: n = k
Pela Definição:
\(\sum_{i =0}^{n-k} C(k+i, k) = C(k, k) = \frac{K!}{K!*0!} = 1\)
Pela tese:
\(C(n+1, k+1) = \frac{(n+1)!}{(k+1)!(n-k)!} = \frac{(n+1)!}{(k+1)!*0!} = 1\)

Hipótese: \(\sum_{i=0}^{n-k} C(k+i, k) = C(n+1, k+1)\)

Passo: Provar para n+1.
\(\sum_{i=0}^{n+1-k} C(k+i, k) = \sum_{i=0}^{n-k} C(k+i, k) + C(k+ (n+1-k),k)\)
Aplicando a hipótese
\(C(n+1, k+1) + C(n+1, k)\)
É possível abrir a combinação, tratar das frações e chegar ao resultado. Mas, pra ser breve, aplica-se a identidade de Pascal e chega ao resultado pretendido que é C(n+2, k+1)
Página 1 de 1 Os Horários são TMG [ DST ]
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/