Mostre que, usando o princípio da indução:
Se m, n in Z e n >= m definamos C n, m=n!(n-m)!m! onde n!=1.2 3 ldots n se n >= 1 e 0!=1. Prove, por indução sobre n, sendo n >= m >= 1 inteiros, que
C n, m-1+C n, m=C n+1, n

Passo 1

O enunciado define para inteiros m,n com 0<= m<= n o número
C(n,m)=n!(n-m)!,m!
e pede para provar, por indução em n (com n>= m>=1), que vale a identidade de Pascal
C(n,m-1)+C(n,m)=C(n+1,m)
Vamos usar o princípio da indução matemática sobre n, entendendo que m é fixo e satisfaz 1<= m<= n.

Passo 2

Base da indução: n=m.
Calculamos cada termo:
C(m,m-1)=m!(m-(m-1))!,(m-1)! =m!1!,(m-1)!=m,
C(m,m)=m!(m-m)!,m! =m!0!,m!=1,
logo
C(m,m-1)+C(m,m)=m+1
Por outro lado,
C(m+1,m)=(m+1)!((m+1)-m)!,m! =(m+1)!1!,m!=m+1
Portanto a igualdade
C(m,m-1)+C(m,m)=C(m+1,m)
é verdadeira, estabelecendo a base.

Passo 3

Passo indutivo: suponha que para algum k>= m valha
C(k,m-1)+C(k,m)=C(k+1,m)
Queremos mostrar
C(k+1,m-1)+C(k+1,m)=C(k+2,m)

Passo 4

Usando a definição em fatoriais, escrevemos
C(k+1,m-1) =(k+1)!l((k+1)-(m-1)r)!,(m-1)! =(k+1)!(k-m+2)!,(m-1)!,
C(k+1,m) =(k+1)!l((k+1)-mr)!,m! =(k+1)!(k-m+1)!,m!
Somando-os com denominador comum (k-m+2)!,m!, temos
C(k+1,m-1)+C(k+1,m) =(k+1)!(k-m+2)!,(m-1)! +(k+1)!(k-m+1)!,m!
Escrevendo o segundo termo sobre (k-m+2)!,m! e fatorando, obtemos
=(k+1)!(k-m+2)!,(m-1)!gl(1+k-m+2mgr) =(k+1)!(k-m+2)!,(m-1)!cdotk+2m
Como m,(m-1)!=m! e (k-m+2)!=(k+2-m)!, segue
=(k+2),(k+1)!(k+2-m)!,m! =(k+2)!(k+2-m)!,m! =C(k+2,m),
que é exatamente o que queríamos provar.

Resposta

A identidade
C(n,m-1)+C(n,m)=C(n+1,m)
vale para todo n>= m>=1 por indução em n.

Exercícios relacionados