Fórum de Matemática
DÚVIDAS? Nós respondemos!

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.

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)

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)