1. Prove que, para todo \mathbf{n} \in \mathbb{Z}_{+}^{*}, a seguinte igualdade é verdadeira:
\sum_{i=0}^{\left[\frac{n}{2}\right]} 2^{n-3} \cdot\binom{n}{n-2 i} \cdot\binom{2 i}{i}=\binom{2 n}{n}

Passo 1

O enunciado pede para provar, para todo n\in\mathbb{Z}_{+}^{*}, a igualdade entre uma soma e o coeficiente binomial central. O enunciado escrito é
\sum_{i=0}^{\left[\frac{n}{2}\right]} 2^{n-3}\cdot\binom{n}{n-2i}\cdot\binom{2i}{i}=\binom{2n}{n}.
Antes de começar, faço uma observação prática: a fatoração 2^{n-3} como fator constante fora da soma não permite emparelhar os casos de pequenas n (por exemplo n=1 levaria a um lado esquerdo diferente do lado direito), portanto parece haver um erro de digitação no expoente de 2. A identidade que é clássica e consistente com o que se espera aqui é
\sum_{i=0}^{\left[\frac{n}{2}\right]} 2^{\,n-2i}\,\binom{n}{n-2i}\,\binom{2i}{i}=\binom{2n}{n}.
Como \binom{n}{n-2i}=\binom{n}{2i}, posso reescrever a identidade correta alvo como
\sum_{i=0}^{\left[\frac{n}{2}\right]} 2^{\,n-2i}\,\binom{n}{2i}\,\binom{2i}{i}=\binom{2n}{n}.
A partir de agora vou provar essa identidade (assumindo que esse era o objetivo). Vou listar claramente o que tenho:
  • Queremos provar a igualdade para todo n\ge1.
  • A soma percorre i=0,1,\dots,\left\lfloor \dfrac{n}{2}\right\rfloor.
  • Os termos usam os binomiais \binom{n}{2i} e \binom{2i}{i} e um fator 2^{\,n-2i}.

Passo 2

Estratégia escolhida (sem usar jargões pesados): contar de duas maneiras o número de maneiras de escolher n elementos dentre 2n elementos organizados em n pares. Esse tipo de argumento combinatório costuma ser o mais direto e elementar para identidades com \binom{2n}{n}.
Explicando o modelo: imagine n pares disjuntos, cada par contendo exatamente 2 elementos (por exemplo, pares \{a_1,b_1\},\{a_2,b_2\},\dots,\{a_n,b_n\}). No total há 2n elementos. O número de maneiras de escolher n elementos dentre os 2n é, por definição,
\binom{2n}{n}.
Esse será o lado direito que queremos obter contando de outra maneira.

Passo 3

Agora vamos contar as mesmas escolhas agrupando-as pelo número de pares dos quais tiramos os dois elementos. Defina i como o número de pares dos quais escolhemos ambos os elementos. Observações básicas:
  • i pode ser 0,1,\dots,\left\lfloor \dfrac{n}{2}\right\rfloor. O teto inferior vem porque, se escolhemos i pares completos (cada um fornece 2 elementos), estes 2i elementos consomem parte das n escolhas; restam n-2i elementos a escolher, cada um obrigatoriamente vindo de pares nos quais escolhemos apenas 1 elemento. Como há no total n pares, i não pode exceder \lfloor n/2\rfloor.
  • Para um valor fixo de i, vamos contar quantas escolhas resultam em exatamente i pares completos.

Passo 4

Contagem para um i fixo:
  1. Escolher quais i pares serão os que contribuem com os dois elementos: há \binom{n}{i} maneiras.
  2. Dos n-i pares restantes, precisamos escolher exatamente n-2i pares onde pegaremos apenas um elemento (os outros n-i-(n-2i)=i pares restantes nos quais não pegamos nenhum elemento). O número de maneiras de escolher essas n-2i pares é \binom{n-i}{\,n-2i\,}.
  3. Para cada par escolhido na etapa 2 (isto é, para cada par do qual pegamos só um elemento), há exatamente 2 escolhas possíveis (o primeiro ou o segundo elemento do par). Como são n-2i desses pares, obtém-se um fator 2^{\,n-2i}.
Multiplicando as escolhas independentes, o número de seleções com exatamente i pares completos é
\binom{n}{i}\,\binom{n-i}{\,n-2i\,}\,2^{\,n-2i}.

Passo 5

Somando sobre todos os i possíveis obtemos o total de maneiras de escolher n elementos dentre os 2n:
\sum_{i=0}^{\left\lfloor\frac{n}{2}\right\rfloor}\binom{n}{i}\,\binom{n-i}{\,n-2i\,}\,2^{\,n-2i}.
Pelo raciocínio do Passo 2 esse total deve ser igual a \binom{2n}{n}. Portanto
\binom{2n}{n}=\sum_{i=0}^{\left\lfloor\frac{n}{2}\right\rfloor}\binom{n}{i}\,\binom{n-i}{\,n-2i\,}\,2^{\,n-2i}.

Passo 6

Agora mostramos que o termo \binom{n}{i}\,\binom{n-i}{\,n-2i\,} é igual ao termo usado na forma pedida, isto é, a \binom{n}{2i}\,\binom{2i}{i}. Faço essa igualdade algébrica para fechar o laço:
Começo usando a identidade \binom{n-i}{\,n-2i\,}=\binom{n-i}{i}. Então
\binom{n}{i}\,\binom{n-i}{\,n-2i\,}=\binom{n}{i}\,\binom{n-i}{i}.
Agora expresso em fatoriais:
\binom{n}{i}\,\binom{n-i}{i}=\frac{n!}{i!(n-i)!}\cdot\frac{(n-i)!}{i!(n-2i)!}=\frac{n!}{i!\,i!\,(n-2i)!}.
Por outro lado,
\binom{n}{2i}\,\binom{2i}{i}=\frac{n!}{(2i)!(n-2i)!}\cdot\frac{(2i)!}{i!\,i!}=\frac{n!}{i!\,i!\,(n-2i)!}.
Portanto
\binom{n}{i}\,\binom{n-i}{\,n-2i\,}=\binom{n}{2i}\,\binom{2i}{i}.

Passo 7

Substituindo essa igualdade na soma do Passo 5 obtemos exatamente a forma desejada:
\binom{2n}{n}=\sum_{i=0}^{\left\lfloor\frac{n}{2}\right\rfloor}2^{\,n-2i}\,\binom{n}{2i}\,\binom{2i}{i}.
Isso conclui a prova da identidade (a qual coincide com a forma corrigida indicada no Passo 1). A ideia central é que o mesmo conjunto de escolhas — escolher n itens dentre 2n organizados em n pares — foi contado de duas maneiras diferentes: diretamente (dando \binom{2n}{n}) e classificando pelo número de pares escolhidos completamente (dando a soma).

Resposta

\sum_{i=0}^{\left\lfloor\frac{n}{2}\right\rfloor}2^{\,n-2i}\,\binom{n}{n-2i}\,\binom{2i}{i}=\binom{2n}{n}

Exercícios relacionados