|
|
Post by Francehelder on Jan 5, 2015 15:16:15 GMT -3
Dado $n$ natural mostre que
$\displaystyle\sum_{i=0}^n\binom{n}{i}=2^n$
|
|
|
|
Post by Walner Mendonça on Jan 5, 2015 17:40:35 GMT -3
Pode usar o teorema do binomial de Newton?
$$2^n = (1+1)^n = \sum_{i=0}^{n} \binom{n}{i}$$
Uma outra forma de mostrar é a seguinte. Primeiro, se temos uma função polinomial $f(x) = \sum_{k=0}^{n} a_k x^k$, então vale que $a_k = \frac{f^{(k)}(0)}{k!}$, para todo $k=1,2,\ldots,n$. Pois bem. Considere a função polinomial $f(x)=(1+x)^n$. Temos
$$ f^{(k)}(x) = n(n-1)\cdots(n-k+1)(1+x)^{n-k}. $$
Em particular, $ f^{(k)}(0) = n(n-1)\cdots(n-k+1).$ E assim temos que $f(x) = \sum_{k=0}^{n} a_k x^k$, onde
$$a_k = \frac{f^{(k)}(0)}{k!} = \frac{n(n-1)\cdots(n-k+1)}{k!} = \binom{n}{k}.$$
Isto é,
$$f(x) = (1+x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k.$$
Em particular, para $x=1$, temos
$$ 2^n = \sum_{k=0}^{n} \binom{n}{k}.$$
|
|
|
|
Post by Duvidoso on Jan 5, 2015 18:47:36 GMT -3
De fato, seja $X$ um conjunto com $n$ elementos, qual a quantidade do conjunto das partes de $X$ $(P(X))$?
Ora, então para estes elementos iremos dividir a classe dos elementos que tem $0,1,2,...,$ e $n$-elementos do conjunto $X$. Mas de quantos modos podemos escolher $k$ elementos em um conjunto de $n$ elementos e de modo que a ordem em que eles aparecem não importe(já que são conjuntos)?, resposta : $C(n,k)$ modos. logo o número de elementos na classe dos conjuntos que tem $k$ elementos é $C(n,k)$, sendo assim, $\displaystyle \sum_{k=0}^n C(n,k) = card.P(X)$ , só que já sabemos que $card.P(X)$ para $X$ com $n$ elementos é $2^n$, de modo que $\displaystyle \sum_{k=0}^{n} C(n,k) =2^n$. A saber como calcular a cardinalidade de $P(X)$ a marra temos que a escolha de um conjunto para que este pertença ao conjunto das partes é feita de modo que um elemento $x \in X$ pertence ou não ao elemento que estará em $P(X)$ , como só há duas possibilidades para cada elemento o número de possibilidades para cada conjunto pelo principio fundamental da contagem é $2\cdot2\cdot2\cdot2\cdot ... \cdot . 2(n-vezes) = 2^n$, donde segue a outra forma de calcular o cardinalidade de $P(X)$
Obs: $\displaystyle \binom{n}{k}=C(n,k)$
|
|
