Tarefa 06 – Todos Subconjuntos Disciplina: Estatística Básica para Bioinformática Discentes: Diego M Salvanha, Madeleine Ernst Enunciado da tarefa: Dado que o número de subconjuntos que podem ser feitos de um conjunto com N elementos é 2n, mostrar que é 2n de fato usando: Princípio da Indução (i) e Teorema da expansão Binomial (ii); Comentando/Comparando cada uma delas em termos da dificuldade, pré-­‐requisitos, etc. e tal. Análise crítica das duas formas de chegar nesse maravilhoso resultado. (i) Resolução com o Princípio da Indução Matemática. A Indução Matemática é um método de prova matemática usado para demonstrar a verdade de um número infinito de proposições[1]. A forma mais simples e mais comum de indução matemática prova que um enunciado vale para todos os números naturais n e consiste de dois principais passos: A.
A base: mostrar que o enunciado vale para n = 1; B.
O passo indutivo: mostrar que, se o enunciado vale para n = k, então o mesmo enunciado vale para n = k + 1; Esse método funciona provando que o enunciado é verdadeiro para um valor inicial, e então provando que o processo usado para ir de um valor para o próximo é valido. Se ambas as coisas são provadas, então qualquer valor pode ser obtido através da repetição desse processo. Para a resolução deste exercício por (i), devemos considerar: O numero possível de subconjuntos com n elementos foi apresentado como sendo 2n. { a1, a2, a3………an} conjuntos = 2n subconjuntos Em primeiro momento, vamos testar a formula dada para verificar se realmente bate com o resultado esperado: n = 2 {a1, a2} = {a1, a2, a1a2, Ø} = 4 conjuntos = 22 subconjuntos A formula é verdadeira para n = 2. n = 3 {a1, a2, a3} = {a1, a2, a3, a1a2, a1a3, a2a3, a1a2a3, Ø} = 8 conjuntos = 23 subconjuntos A formula é verdadeira para n = 3. O princípio da indução matemática, que é afirmado sobre cada número natural, diz que se: 1) Para o caso base n=2 é verdadeiro (já provamos acima); 2) A afirmação é verdadeira para o numero natural n = k, então também deve ser verdadeiro para seu sucessor n = k + 1; O caso 2. apresentado acima é então conhecido como hipótese de indução. Vamos então provar utilizando o teorema de indução assumindo que a hipótese de indução (n=k) é verdadeira. n = k é dado como verdadeira { a1, a2, a3………ak} conjuntos = 2k subconjuntos Assumindo n = k como verdadeiro, devemos conseguir provar que a formula também é verdadeira para o seu sucessor (n = k + 1), então teremos: { a1, a2, a3………ak+1} Conjuntos = 2k+1 Subconjuntos Para fazer isso, adicionaremos (k+1) a nossa hipótese de indução: { a1, a2, a3………ak, ak+1} conjunto = 2k • 2 subconjuntos (1) Foi multiplicado por 2 (na esquerda) para que o novo elemento ak+1 seja adicionado e forme um novo elemento a cada elemento já existente e contido em 2k. Devemos lembrar que o mesmo não forma um novo elemento com Ø. Para n = 2 {a1, a2} = {a1, a2, a1a2, Ø} = 4 conjuntos = 22 subconjuntos n+1 = 3 {a1, a2, a3} = {a1, a2, a3, a1a2, a1a3, a2a3, a1a2a3, Ø} = 8 conjuntos = 2•22 subconjuntos Reescrevendo a formula (1) obteremos: { a1, a2, a3………ak, ak+1} conjuntos = 2k • 2 subconjuntos = 2k • 21 subconjuntos = 2k+1 provando assim que a formula também é verdadeira para n = k+1; (ii) Resolução com o Teorema Binomial. Em matemática, binômio de Newton permite escrever na forma canônica o polinómio correspondente à potência de um binômio. O nome é dado em homenagem ao físico e matemático Isaac Newton. Entretanto deve-­‐
se salientar que o Binômio de Newton não foi o objeto de estudos de Isaac Newton. Na verdade o que Newton estudou foram regras que valem para (a + b)n quando o expoente n é fracionário ou inteiro negativo, o que leva ao estudo de séries infinitas.[2] !
𝑥 +𝑦
= 𝑥 ! + 2𝑥𝑦 + 𝑦 ! O teorema binomial é representado como: !
𝑥+𝑦
!
=
!!!
Os coeficientes
!
!
𝑛 !!! !
𝑥
𝑦 𝑘
são chamados coeficientes binomiais e são definidos como: 𝑛
𝑛!
= 𝑘
𝑘! 𝑛 − 𝑘 !
IMPORTANTE: Devemos lembrar que: O coeficiente binomial !
!
corresponde, em análise combinatória, ao número combinações de n elementos agrupados k a k. Para provarmos que 2k é verdade, utilizando o Teorema Binomial, podemos aplicar a formula acima e verificar o resultado: 2! = 1 + 1
!
=
!
!!!
!
!
1!!! 1! (2) Se olharmos somente para a parte da equação (1n-­‐k 1k) veremos que a mesma vai sumir, pois: Para n = 1 e k=0 ; (1n-­‐k 1k) = (11-­‐0 10) = (111) = 1 Para n = 1 e k=1 ; (1n-­‐k 1k) = (11-­‐1 11) = (1 11) = 1 Para n = 1 e k=2 ; (1n-­‐k 1k) = (11-­‐2 12) = (1112) = 1 Para n = 1 e k=3 ; (1n-­‐k 1k) = (11-­‐3 13) = (1213) = 1 Com isso, vemos que independente do numero atribuído ao k (durante a somatória) para (x = 1 e y = 1) o resultado será sempre igual a 1 pois 1 elevado a qualquer número é sempre ele mesmo, ou seja, a mesma formula (2) pode ser simplificada para o nosso caso como: !
!
2 = 1 + 1
!
=
!!!
𝑛
𝑘
Para provar essa aplicação da formula Binomial, algumas soluções/simulações foram feitas utilizando a poderosa linguagem estatística de programação R. ## Código1 em R para verificar um único caso onde n
= qualquer número natural (formula binomial
completa)
a=1;
b=1;
n=2;
result=0;
for (i in 0:n) {
result = result + (
factorial(n)/((factorial(i))*(factorial(n-i))) ) * (
( (a^(n-i)) ) * (b^i) )
}
print(result)
2^n
result == 2^n
## Código2 em R para verificar um único caso onde n
= qualquer número natural (formula binomial
simplificada)
a=1;
b=1;
n=2;
result=0;
for (i in 0:n) {
result = result + (
factorial(n)/((factorial(i))*(factorial(n-i))) )
}
print(result)
2^n
result == 2^n
Foi desenvolvido uma simulação para verificar se realmente bate para vários casos (o que deve ocorrer sempre). #simula para n=# + n=#+1 ...
a=1;
b=1;
n=0;
result=0;
walk = 10;
vt = 0*(1:walk)
for (j in 0:walk){
for (i in 0:n) {
result = result + (
factorial(n)/((factorial(i))*(factorial(n-i))) ) * (
( (a^(n-i)) ) * (b^i) )
}
print(result)
print(2^n)
print(result == 2^n)
vt[j] = (result == 2^n)
result = 0; ##limpa var
n = n+1; #n++
} #end j
if ( (sum(vt == FALSE)) ==0 ){
print("Todos resultados bateram !")
} else {print("errado!")}
1.
GERSTING, Judith L. Fundamentos Matemáticos para a Ciência da Computação. LTC 3º ed. 2.
GARBI, Gilberto G. O Romance das Equações Algébricas. Editora Livraria da Física. São Paulo, 2007.