Prove que C2 n^n é par, se n >= 1.

Passo 1

O enunciado pede para mostrar que, para todo inteiro n>=1, o coeficiente binomial central
binom2nn
é um número par. O tema aqui é combinatória elementar e usamos um argumento de contagem por involução sem pontos fixos para concluir divisibilidade por 2.

Passo 2

Considere o conjunto U=1,2,dots,2n e o conjunto S de todas as suas partes de tamanho n. Então
l|Sr|=binom2nn
Definimos a bijeção involutiva
fcolon Slongrightarrow S, f(S)=Usetminus S
Note que S e f(S) têm ambos n elementos, e f(f(S))=S. Além disso, não existe S tal que f(S)=S, pois isso exigiria
S=Usetminus S Longrightarrow Scup S=U,;Scap S=varnothing,
o que é impossível quando U tem 2n>0 elementos.

Passo 3

Como f agrupa as partes de U em pares S,f(S) de tamanho 2, segue que l|Sr| é múltiplo de 2. Ou seja,
binom2nn
é par para todo inteiro n>=1.

Resposta

Como há uma involução sem pontos fixos em S, concluímos que binom2nn é sempre par para n>=1.

Exercícios de Livros Relacionados