Resumo MD

Prévia do material em texto

Coeficiente Binomial: 
O coeficiente binomial, também chamado de número binomial, de um número n, na classe k, 
consiste no número de combinações de n termos, k a k. 
 
o coeficiente binomial é uma combinação, onde ele diz qual a quantidade de subconjuntos de ​k 
elementos diferentes de um conjunto de n​ ​elementos diferentes. 
 
exemplo; ​o coeficiente binomial de n = 10 por k = 2 é 0! / 2!(10 2)! 451 − = 
 
O coeficiente binomial é muito utilizado no Triângulo de Pascal, onde o termo na linha n e coluna 
k é 
 = 
Combinação:​ ​Combinação de 3 por 2 ​indica de quantas formas distintas é possível escolher 
2 elementos de um grupo de 3 elementos, digamos as 3 primeiras letras do alfabeto: {a,b,c}. As 
três possíveis combinações são: 
 
ab, ac, bc. Note que em uma combinação não estamos interessados na ordenação dos 
elementos, uma vez que estamos tratando de um subconjunto do conjunto inicial. desta maneira 
ab e ba representam um mesmo conjunto. 
 
indução: 
indução é um método de prova matemática que serve para provar situações em que 
o conjunto de casos dessas situações é infinito. Para provar você pode dividir a 
prova em três casos. 
1 ​Base:​ Mostrar que o caso vale para um exemplo específico. 
2 ​Passo indutivo: ​Mostre que a situação vale para um caso K específico. 
3 ​Tese:​ Com um caso k + 1, reduza ele a dois casos, onde um deles seja o caso k e 
o outro seja a base. 
Exemplo. ​Prove que (1+x)​n ​>= 1+nx se x >=​ ​-1 e n é um número natural. 
n pode ser qualquer número natural e x tem que ser maior que -1. O caso base 
pode ser qualquer valor que respeite essas condições. Vou escolher x = 1 como 
caso base. 
Base: ​fazendo x = 1 temos: (1+1)​4 ​= 16 e 1+1*3 = 3. Logo como 16 > 3, a situação é 
válida para x = 1. 
Passo indutivo:​ fazendo o x como um número k qualquer maior que 2, vamos 
assumir que a equação: 
(1+k)​n ​>= ​1+nk​ é verdadeira. 
Tese: ​Para um número x = k+1, nós temos que: 
(1+(k+1))​n ​= 1​n​*(k+1)​n​ = 1 ​n ​* n(k)​n-1​+n(k)​n-2​+...+​n(k) + 1​. 
Note que a parte em vermelho é igual a parte da direita da equação do nosso passo 
indutivo. Como estamos somando essa ​n(k) + 1​ mais n(k)​n-1​+n(k)​n-2​+...+ (isso tudo), 
podemos assumir que a expressão (k+1)​n ​ é maior que ​n(k) + 1​. Logo, pelo passo 
indutivo fica provado a questão. 
princípio da casa de pombos: 
O ​princípio do pombal​ ou ​princípio da casa dos pombos​ é a afirmação de que se ​n​ pombos 
devem ser postos em ​m​ casas, e se ​n ​> ​m​, então pelo menos uma casa irá conter mais de um 
pombo. Ele serve pra mostrar que uma função não é injetiva. 
 
10 pombos e 9 casas. 
Matematicamente falando, isto quer dizer que se o número de elementos de um conjunto finito A 
é maior do que o número de elementos de um outro conjunto B, então uma função de A em B 
não​ pode ser injetiva. Uma função é injetiva quando cada elemento do contradomínio (ou 
imagem) só é gerado por um elemento do domínio da função, ou seja F(x) = F(y). 
Seja X o domínio e Y o contradomínio: 
função injetiva. (cada elemento de X gera só um elemento de Y) 
função não injetiva. (c é gerado por 3 e 4 do domínio) Considere 
que os elementos do Domínio são os pombos e os elementos no contradomínio são as casas. 
 
Para provar que uma função é injetiva, basta fazer F(x) = F(y). 
Exemplo: 
prove que F = 2x + 3 é injetiva. 
Prova: 
Faça F(x) = F(y). 
2x + 3 = 2y + 3. 
2x = 2y + 3 - 3 
2x = 2y 
x = y. Logo F(x) = F(Y) 
 
Relações de recorrência: 
Recorrência é uma função que chama ela mesma para calcular os novos valores. 
Uma relação de recorrência é uma equação em que cada termo de uma sequência 
é definido em função dos elementos anteriores. 
 
exemplo: 
Seja a recorrência S(n), definida por: 
base: S(1) = 2 
relação de recorrência: S(n) = 2*S(n-1), para n>=2. 
Fazendo alguns casos, nós temos: 
S(1) = 2 
S(2) = 2*S(1) = 2*2 = 4 
S(3) = 2*S(2) = 2*4 = 8 
Logo percebemos que a recorrência cresce a uma taxa constante. O resultado atual 
é duas vezes maior que o anterior. 
podemos então definir uma fórmula para isso. 
S(n) = n​2