Exercício 35. Use indução para demonstrar que para todo
:
Passo 1
O enunciado pede para demonstrar que, para todo
,
Informações e definições relevantes que o enunciado nos dá (essas são as “peças” que vamos usar):
- Para
e inteiros com , o coeficiente binomial é definido por
onde
denota o fatorial de
.
- A soma à esquerda é a soma de todos os coeficientes binomiais de ordem
, ou seja, . - O objetivo é provar que essa soma é igual a
para todo natural.
Passo 2
Começamos pela base da indução. Verificar o caso
.
- Calcular o lado esquerdo: quando
só existe . Pela definição de fatorial,
- Calcular o lado direito:
.
Portanto, paratemos
ou seja, a propriedade é verdadeira para
. (Se preferir, pode verificar também
:
, só para ganhar confiança.)
Passo 3
Enunciamos a hipótese de indução. Suponha que, para um certo
, vale
O objetivo agora é provar que, sob essa hipótese, a propriedade vale para
; isto é, provar que
Passo 4
Vamos usar a identidade de Pascal, que é essencial aqui. A identidade de Pascal diz que, para
,
Explicação e prova rápida (álgebra): partindo da definição por fatoriais,
Multiplicando e dividindo convenientemente, obtemos
Colocando em denominador comum
e simplificando chega-se exatamente a
, que é
. (Intuição combinatória: escolher
de
itens é escolher se um item especial está ou não na seleção, levando às duas parcelas da soma.)
Passo 5
Agora somamos todos os coeficientes para
e aplicamos a identidade de Pascal com cuidado nos índices. Começamos escrevendo explicitamente as extremidades:
Sabemos que
. Para os termos interiores, aplicamos Pascal:
Separando a soma em duas somas:
Fazemos uma mudança de índice na primeira soma: colocando
, quando
temos
e quando
temos
. Assim
A segunda soma já é
Somando as duas e incluindo as extremidades
e
que valem
cada, obtemos
Agora note que, ao juntar as somas internas, cada termo
para
aparece duas vezes, enquanto
e
aparecem uma vez em cada soma de borda; no total isso equivale a somar duas vezes toda a soma
. Em termos algébricos faz-se a combinação:
Substituindo na expressão total:
Portanto, usando a hipótese de indução
, obtemos
Passo 6
Concluímos o passo indutivo: mostramos que se a fórmula vale para
então vale para
. Juntando com a base
, pela indução matemática a igualdade
vale para todo
. (Breve comentário final: uma interpretação combinatória alternativa e rápida — que dá intuição — é que o lado esquerdo conta, por tamanhos, todas as subconjuntos de um conjunto com
elementos, e o lado direito
é o número total de subconjuntos.)