Teorema: "Sejam ne k Intelros positivos, então:
sum k = 1 to n 2 ^ k * binomial(n,k) = 3 ^ (n, k)
Demonstração: "Utilizaremos o método da contagem dupla para contar duas vezes as sequências de comprimento n do alfabeto (0, 1, 2). Em outras palavras, contaremos as n permutações do multiconjunto ( co + 0 , infty infty* ∞ * 2 \ em que há repetições infinitas dos elementos 0, 1 e 2.
Primeira maneira: existem três possibilidades por elemento, então existem 3 possibilidades no total.
Segunda maneira: primeiro, escolha o número de vezes k que o número 0 deve ser usado (0 <= k <= n) Em seguida, escolha as posições para esses elementos; existem A possibilidades. Finalmente, escolha para cada um das (n - k) posições restantes, que devem ser 1 ou 2, ou seja, existem 2 escolhas. Portanto, no total, há
B
possibilidades.
Ao inverter a ordem da soma, isso é igual a:
sum k = 0 to n 2 ^ k * binomial(n,n - k) = C
Portanto:
sum k = 0 to n 2 ^ k * binomial(n,k) = 3 ^ (n ^ n)
A = binomial(n,k), \mathcal{B} = sum k = 0 to n 2 ^ (n - k) * binomial(n,k) * e * C = sum k = 0 to n 2 ^ (k + 1) * binomial(n,k)
A = binomial(n,k), B = sum k = 0 to n 2 ^ k * binomial(n,k) * e * C = sum k = 0 to n 2 ^ k * binomial(n,k)
A = binomial(n,k - 1) B = sum k = 0 to n 2 ^ k * binomial(n,k) * e * C = sum k = 0 to n 2 ^ (k + 1) * binomial(n,k)
