Identidades com coeficientes binomiais e contagens (problemas 26-31)

Apuntes

```markdown 26. Mostra por contagem dupla que: $\left( \left( \binom{n}{k} \right) \right) = \sum_{i=0}^{n} \left( \left( \binom{i}{k-1} \right) \right).$ 27. (a) Quantas sequências binárias de comprimento $n$ existem com exatamente $k$ uns e com a propriedade que entre cada dois uns há pelo menos um zero? (b) Usando a alínea anterior, quantos subconjuntos de $[n]$ existem com $k$ elementos e sem números consecutivos? Coeficientes Binomiais 28. Usando a identidade de Pascal, escreve: $\binom{n}{k} + 3 \binom{n}{k-1} + 3 \binom{n}{k-2} + \binom{n}{k-3}$ usando um único coeficiente binomial. 29. Mostra que, para todos os inteiros $m, n \geq 0$: $\sum_{i=0}^{n} \binom{m+i}{m} = \binom{m+n+1}{m+1}.$ 30. Usando uma dupla contagem, mostra que: $1^2 + 2^2 + 3^2 + \cdots + n^2 = 2 \binom{n+1}{3} + \binom{n+1}{2}.$ 31. Usando uma dupla contagem, mostra que: (a) $\binom{2n}{2} = 2 \binom{n}{2} + n^2.$ (b) $\binom{3n}{2} = \binom{n}{2} + 2n^2 + \binom{2n}{2}.$ ```