Prove que:
C(n, r)=C(n-1, r)+C(n-1, r-1)

Passo 1

Estamos querendo provar a identidade para coeficientes binomiais
\binom{n}{r} = \binom{n-1}{r} + \binom{n-1}{r-1}.
O que vamos usar é a interpretação combinatória: \binom{n}{r} conta o número de maneiras de escolher r elementos de um conjunto com n elementos.

Passo 2

Escolhemos um elemento especial do conjunto de tamanho n; vamos chamá-lo de “ x”. Vamos separar todas as escolhas de r elementos em dois casos disjuntos:
  1. As escolhas que não incluem x.
    O número de maneiras de escolher r elementos dentre os n sem usar x é o mesmo que escolher r de um conjunto de tamanho n-1. Logo esse caso contribui com
\binom{n-1}{r}.

Passo 3

  1. As escolhas que incluem x.
    Se x já está incluído, precisamos escolher mais r-1 elementos dentre os outros n-1. O número de maneiras de fazer isso é
\binom{n-1}{r-1}.

Passo 4

Como esses dois casos (incluir x e não incluir x) são mutuamente exclusivos e cobrem todas as possibilidades de escolha de r elementos, somamos as quantidades:
\binom{n}{r} = \underbrace{\binom{n-1}{r}}_{\substack{\text{sem }x}} + \underbrace{\binom{n-1}{r-1}}_{\substack{\text{com }x}}.

Resposta

A identidade está provada:
\binom{n}{r} = \binom{n-1}{r} + \binom{n-1}{r-1}.

Exercícios relacionados