> Oi pessoal,
>
> Gostaria da ajuda de voces com 2 questoes que não consigo fazer:
> (qualquer comentario/ideia vai ajudar, eu não consigo sair do canto nessas
> questoes)
>
O primeiro eh provar que n^k/k^k <= Binom(n,k) <= n^k/k!.
A segunda desigualdade eh mais facil:
Binom(n,k) = n*(n-1)*...*(n-k+1)/k! <= n*n*...*n/k! = n^k/k!.
Com relacao a primeira, repare que se n = k, entao:
n^k/k^k = Binom(n,k) = 1;
se n > k = 1, entao:
n^k/k^k = Binom(n,k) = n;
finalmente, se n > k > 1, entao:
n/k < (n-1)/(k-1) < (n-2)/(k-2) < .... < (n-k+2)/2 < (n-k+1)/1
Basta provar a primeira desigualdade desta sequencia:
n > k ==>
n-1 > k-1 ==>
1/(n-1) < 1/(k-1) ==>
1 + 1/(n-1) < 1 + 1/(k-1) ==>
n/(n-1) < k/(k-1) ==>
n/k < (n-1)/(k-1)
Binom(n,0) + 2*Binom(n,1) + 2^2*Binom(n,2) + ... + 2^n*Binom(n,n) =
(1 + 2)^n = 3^n.
Uma demonstracao combinatoria seria a seguinte:
Temos um cartao de loteria esportiva com n jogos, cada um dos quais com 3 alternativas (vitoria de um time, vitoria do outro ou empate).
De quantas maneiras podemos preenche-lo?
Obviamente, a resposta eh 3^n.
Por outro lado, poderiamos raciocinar da seguinte forma:
Para cada k (0 <= k <= n), podemos preencher o cartao com k empates e os demais n-k jogos com vitoria de um dois dois times. Assim, para cada k, teremos:
1) Escolha dos jogos em que marcaremos empate:
isso pode ser feito de Binom(n,k) formas diferentes.
2) Em cada um dos (n-k) jogos em que marcaremos vitoria de algum time, poderemos escolher o time de 2 maneiras. Logo, poderemos marcar vitoria de 2^(n-k) formas diferentes.
Somando de k = 0 ateh k = n, acharemos o numero total de maneiras de preencher o cartao:
Binom(n,0)*2^n + Binom(n,1)*2^(n-1) + ... + Binom(n,n-1)*2^1 + Binom(n,n)*1,
ou, levando em conta que Binom(n,k) = Binom(n,n-k):
Binom(n,0)*1 + Binom(n,1)*2 + ... + Binom(n,n-1)*2^(n-1) + Binom(n,n)*2^n.
Mas sabemos que esse numero eh igual a 3^n.
Logo, a identidade estah provada.
[]s,
Claudio.
