Baixe o app para aproveitar ainda mais
Prévia do material em texto
MA12 - Unidade 1 Números Naturais Paulo Cezar Pinto Carvalho PROFMAT - SBM February 25, 2013 Os Números Naturais Números Naturais: modelo abstrato para contagem. N = {1, 2, 3, ...} Uma descrição precisa e concisa de N é dada pelos Axiomas de Peano. Noção fundamental: a de sucessor de um número natural (ou seja, o número que, intuitivamente, vem logo depois dele). PROFMAT - SBM MA12 - Unidade 1 , Números Naturais slide 2/9 Os Axiomas de Peano a) Todo número natural tem um único sucessor; b) Números naturais diferentes têm sucessores diferentes; c) Existe um único número natural, chamado um e representado pelo śımbolo 1, que não é sucessor de nenhum outro; d) Seja X um conjunto de números naturais (isto é, X ⊂ N). Se 1 ∈ X e se, além disso, o sucessor de todo elemento de X ainda pertence a X , então X = N. PROFMAT - SBM MA12 - Unidade 1 , Números Naturais slide 3/9 O Axioma da Indução O último dos axiomas de Peano é conhecido como Axioma da Indução e é a base para um método de demonstração para propriedades relativas aos números naturais (demonstrações por indução). Seja P(n) uma propriedade relativa ao número natural n. Suponhamos que: i) P(1) é válida; ii) Para todo n ∈ N, a validez de P(n) implica a validez de P(n′), onde n′ é o sucessor de n. Então P(n) é válida qualquer que seja o número natural n. PROFMAT - SBM MA12 - Unidade 1 , Números Naturais slide 4/9 As Duas Operações: Adição e Multiplicação A soma n + p é o número natural que se obtém a partir de n aplicando-se p vezes seguidas a operação de tomar o sucessor. Em particular, n + 1 é o sucessor de n, n + 2 é o sucessor do sucessor de n, etc. Quanto ao produto, põe-se n · 1 = n por definição e, quando p 6= 1, np é a soma de p parcelas iguais a n. Entretanto, até que saibamos utilizar os números naturais para efetuar contagens, não tem sentido falar em “p vezes” e “p parcelas”. Por esta razão, é preciso definir estas operações por indução. PROFMAT - SBM MA12 - Unidade 1 , Números Naturais slide 5/9 Usando indução para definir as operações Adição: n + 1 = sucessor de n n + (p + 1) = (n + p) + 1 . Multiplicação: n · 1 = n n(p + 1) = np + n. As propriedades destas operações (comutativa, associativa, etc) podem ser demonstradas por indução. PROFMAT - SBM MA12 - Unidade 1 , Números Naturais slide 6/9 A Ordenação nos Números Naturais Dados m, n ∈ N, diz-se que m é menor do que n, e escreve-se m < n, para significar que existe algum p ∈ N tal que n = m + p. Propriedades: Transitividade: Se m < n e n < p então m < p. Tricotomia: Dados m, n ∈ N, vale uma, e somente uma, das alternativas: m = n, m < n ou n < m. Monotonicidade: Se m < n então, para qualquer p ∈ N, tem-se m + p < n + p e mp < np. Boa-ordenação: Todo subconjunto não-vazio X ⊂ N possui um menor elemento. A boa-ordenação pode muitas vezes substituir com vantagem a indução como método de prova de resultados referentes a números naturais. PROFMAT - SBM MA12 - Unidade 1 , Números Naturais slide 7/9 Exemplo: uma demonstração por indução Provar a validez, para todo número natural n, da igualdade P(n) : 1 + 3 + 5 + . . . + (2n − 1) = n2 Para n = 1, P(1) se resume a afirmar que 1 = 1. Supondo P(n) verdadeira para um certo valor de n, somamos 2n + 1 a ambos os membros da igualdade acima, obtendo 1 + 3 + 5 + . . . + (2n − 1) + (2n + 1) = n2 + 2n + 1, ou seja: 1 + 3 + 5 + . . . + [2(n + 1)− 1] = (n + 1)2. Mas esta última igualdade é P(n + 1). Logo P(n) ⇒ P(n + 1). Assim, P(n) vale para todo n ∈ N. PROFMAT - SBM MA12 - Unidade 1 , Números Naturais slide 8/9 Exemplo: uma demonstração por boa ordenação Provar que todo número natural é primo ou é um produto de fatores primos Seja X o conjunto dos números naturais que são primos ou produtos de fatores primos. Observemos que se m e n pertencem a X então o produto mn pertence a X . Seja Y o complementar de X . Assim, Y é o conjunto dos números naturais que não são primos nem são produtos de fatores primos. Queremos provar que Y é vazio. Com efeito, se Y não fosse vazio, haveria um menor elemento a ∈ Y . Então todos os números menores do que a pertenceriam a X . Como a não é primo, ter-se-ia a = m · n, com m < a e n < a, logo m ∈ X e n ∈ X . Sendo assim, mn ∈ X . Mas mn = a, o que daria a ∈ X , uma contradição. Segue-se que Y = ∅ , concluindo a demonstração. PROFMAT - SBM MA12 - Unidade 1 , Números Naturais slide 9/9 MA12 - Unidade 2 Números Cardinais Paulo Cezar Pinto Carvalho PROFMAT - SBM February 25, 2013 Introdução A importância dos números naturais provém do fato de que eles constituem o modelo matemático que torna posśıvel o processo de contagem. Para contar os elementos de um conjunto é necessário usar a noção de correspondência biuńıvoca, ou bijeção, que é um caso particular do conceito de função. PROFMAT - SBM MA12 - Unidade 2 ,Números Cardinais slide 2/12 Funções Dados os conjuntos X , Y , uma função f : X → Y (lê-se “uma função de X em Y ”) é uma regra (ou conjunto de instruções) que diz como associar a cada elemento x ∈ X um elemento y = f (x) ∈ Y . O conjunto X chama-se o doḿınio e Y é o contra-doḿınio da função f . Para cada x ∈ X , o elemento f (x) ∈ Y chama-se a imagem de x pela função f , ou o valor assumido pela função f no ponto x ∈ X . Escreve-se x 7→ f (x) para indicar que f transforma (ou leva) x em f (x) PROFMAT - SBM MA12 - Unidade 2 ,Números Cardinais slide 3/12 Exemplos Sejam X o conjunto dos triângulos do plano Π e R o conjunto dos números reais (que abordaremos logo mais). Se, a cada t ∈ X , fizermos corresponder o número real f (t) = área do triângulo t, obteremos uma função f : X → R. Sejam S o conjunto dos segmentos de reta do plano Π e ∆ o conjunto das retas desse mesmo plano. A regra que associa a cada segmento AB ∈ S sua mediatriz g(AB) define uma função g : S → ∆. A correspondência que associa a cada número natural n seu sucessor n + 1 define uma função s : N→ N, com s(n) = n + 1. PROFMAT - SBM MA12 - Unidade 2 ,Números Cardinais slide 4/12 Funções Injetivas Uma função f : X → Y chama-se injetiva quando elementos diferentes em X são transformados por f em elementos diferentes em Y . Ou seja, f é injetiva quando x 6= x ′ em X ⇒ f (x) 6= f (x ′). Esta condição pode também ser expressa em sua forma contrapositiva: f (x) = f (x ′) ⇒ x = x ′. Nos três exemplos dados anteriormente, apenas o terceiro é de uma função injetiva. (Dois triângulos diferentes podem ter a mesma área e dois segmentos distintos podem ter a mesma mediatriz mas números naturais diferentes têm sucessores diferentes.) PROFMAT - SBM MA12 - Unidade 2 ,Números Cardinais slide 5/12 Funções Sobrejetivas Diz-se que uma função f : X → Y é sobrejetiva quando, para qualquer elemento y ∈ Y , pode-se encontrar (pelo menos) um elemento x ∈ X tal que f (x) = y . Nos três exemplos dados anteriormente, apenas o segundo apresenta uma função sobrejetiva. (Toda reta do plano é mediatriz de algum segmento mas apenas os números reais positivos podem ser áreas de triângulos e o número 1 não é sucessor de número natural algum.) PROFMAT - SBM MA12 - Unidade 2 ,Números Cardinais slide 6/12 Bijeções Uma função f : X → Y chama-se uma bijeção, ou uma correspondência biuńıvoca entre X e Y quando é ao mesmo tempo injetiva e sobrejetiva. Exemplo. Sejam X = {1, 2, 3, 4, 5} e Y = {2, 4, 6, 8, 10}. Definindo f : X → Y pela regra f (n) = 2n, temos uma correspondência biuńıvoca, onde f (1) = 2, f (2) = 4, f (3) = 6, f (4) = 8 e f (5) = 10. Exemplo. Seja P o conjunto dos números naturais pares (P = {2, 4, 6, . . . , 2n, . . .}). Obtém-se uma correspondência biuńıvoca f : N→ P pondo-se f (n) = 2n para todo n ∈ N. O interessante deste exemplo é que P é um subconjunto próprio de N. PROFMAT - SBM MA12 - Unidade 2 ,Números Cardinais slide 7/12Números Cardinais Diz-se que dois conjuntos X e Y tem o mesmo número cardinal quando se pode definir uma correspondência biuńıvoca f : X → Y . Nos dois exemplos do slide anterior, os conjuntos têm o mesmo número cardinal. Exemplo Sejam X = {1} e Y = {1, 2}. Evidentemente não pode existir uma correspondência biuńıvoca f : X → Y , portanto X e Y não têm o mesmo número cardinal. PROFMAT - SBM MA12 - Unidade 2 ,Números Cardinais slide 8/12 Conjuntos Finitos Seja X um conjunto. Diz-se que X é finito, e que X tem n elementos quando se pode estabelecer uma correspondência biuńıvoca f : In → X , onde In o conjunto dos números naturais de 1 até n. O número natural n chama-se então o número cardinal do conjunto X ou, simplesmente, o número de elementos de X . A correspondência f : In → X chama-se uma contagem dos elementos de X . A fim de evitar exceções, admite-se ainda incluir o conjunto vazio ∅ entre os conjuntos finitos e diz-se que ∅ tem zero elementos. PROFMAT - SBM MA12 - Unidade 2 ,Números Cardinais slide 9/12 Conjuntos Infinitos Diz-se que um conjunto X é infinito quando ele não é finito. Isto quer dizer que X não é vazio e que, não importa qual seja n ∈ N , não existe correspondência biuńıvoca f : In → X . O conjunto N dos números naturais é infinito. Com efeito, dada qualquer função f : In → N , não importa qual n se fixou, pomos k = f (1) + f (2) + · · ·+ f (n) e vemos que, para todo x ∈ In, tem-se f (x) < k , logo não existe x ∈ In tal que f (x) = k . Assim, é imposśıvel cumprir a condição de sobrejetividade na definição de correspondência biuńıvoca. PROFMAT - SBM MA12 - Unidade 2 ,Números Cardinais slide 10/12 Propriedades dos números cardinais 1 O número de elementos de um conjunto finito é o mesmo, seja qual for a contagem que se adote. Isto significa que se f : Im → X e g : In → X são correspondências biuńıvocas então m = n. 2 Todo subconjunto Y de um conjunto finito X é finito e n(Y ) ≤ n(X ). Tem-se n(Y ) = n(X ) somente quando Y = X . 3 Se X e Y são finitos então X ∪ Y é finito e tem-se n(X ∪ Y ) = n(X ) + n(Y )− n(X ∩ Y ) . 4 Sejam X , Y conjuntos finitos. Se n(X ) > n(Y ), nenhuma função f : X → Y é injetiva e nenhuma função g : Y → X é sobrejetiva. A primeira parte da propriedade 4 é conhecida como o prinćıpio das casas de pombos: se há mais pombos do que casas num pombal, qualquer modo de alojar os pombos deverá colocar pelo menos dois deles na mesma casa. PROFMAT - SBM MA12 - Unidade 2 ,Números Cardinais slide 11/12 Uma Aplicação do Prinćıpio da Casa dos Pombos Provar que, numa reunião com n pessoas (n ≥ 2), há sempre duas pessoas (pelo menos) que têm o mesmo número de amigos naquele grupo. Imaginemos n caixas, numeradas com 0, 1, . . . , n − 1. A cada uma das n pessoas entregamos um cartão que pedimos para depositar na caixa correspondente ao número de amigos que ela tem naquele grupo. As caixas de números 0 e n − 1 não podem ambas receber cartões pois se houver alguém que não tem amigos ali, nenhum dos presentes pode ser amigo de todos, e vice-versa. Portanto temos, na realidade, n cartões para serem depositados em n − 1 caixas. Pelo prinćıpio das gavetas, pelo menos uma das caixas vai receber dois ou mais cartões. Isto significa que duas ou mais pessoas ali têm o mesmo número de amigos entre os presentes. PROFMAT - SBM MA12 - Unidade 2 ,Números Cardinais slide 12/12 MA12 - Unidade 3 O Poder do Método de Indução Paulo Cezar Pinto Carvalho PROFMAT - SBM 28 de Fevereiro de 2013 Prinćıpio da Indução Matemática Como atribuir significado preciso a expressões como 1 + 2 + · · ·+ n e 1 · 2 · . . . · n? Prinćıpio de Indução Matemática Se P(n) é uma propriedade relativa ao número natural n, tal que i) P(1) é válida; ii) Para todo n ∈ N, a validez de P(n) implica a validez de P(n + 1). Então P(n) é válida qualquer que seja o número natural n. Base para demonstrações e definições por indução ou recorrência. Equivalente ao último axioma de Peano, com X = {n ∈ N;P(n) é válida}. PROFMAT - SBM MA12 - Unidade 3, O Poder do Método de Indução slide 2/9 Exemplos de definição por recorrência Como definir, apropriadamente, Sn = 1 + 2 + · · ·+ n? Definimos S1 = 1 A seguir, supondo Sn definido, fazemos Sn+1 = Sn + (n + 1). Como definir, apropriadamente, n! = 1 · 2 · . . . · n? Definimos 1! = 1 A seguir, supondo n! definido, fazemos (n + 1)! = n! · (n + 1). PROFMAT - SBM MA12 - Unidade 3, O Poder do Método de Indução slide 3/9 Somatórios e Produtórios Seja (xn) uma sequência de elementos de um conjunto A dotado de operações de adição e multiplicação. O somatório Sn = n∑ i=1 xi = x1 + x2 + · · ·+ xn e o produtório Pn = n∏ i=1 xi = x1 · x2 · . . . · xn podem ser definidos como se segue: S1 = P1 = x1 Sn+1 = Sn + xn+1, para todo n ∈ N Pn+1 = Pn · xn+1, para todo n ∈ N PROFMAT - SBM MA12 - Unidade 3, O Poder do Método de Indução slide 4/9 Exemplo: a soma Sn = 1 + 2 + · · ·+ n Encontrando uma expressão para Sn Sn = 1 + 2 + · · · + n Sn = n + (n − 1) + · · · + 1 2Sn = (n + 1) + (n + 1) + · · · + (n + 1) Dáı, 2Sn = n(n + 1) e, portanto, Sn = n(n+1) 2 . PROFMAT - SBM MA12 - Unidade 3, O Poder do Método de Indução slide 5/9 Formalizando por Indução Considere a sentença sobre os naturais: P(n) : 1 + 2 + · · ·+ n = n(n+1)2 . i) P(1) : 1 = 1(1+1)2 é verdadeira. ii) Suponhamos que para algum n ∈ N, tenhamos P(n) verdadeira. Somando n + 1 a ambos os lados dessa igualdade, temos: 1 + 2 + · · ·+ n + (n + 1) = n(n + 1) 2 + n + 1 = n(n + 1) + 2(n + 1) 2 = (n + 1)(n + 2) 2 , o que estabelece a veracidade de P(n + 1). Pelo Prinćıpio de Indução, tem-se que a fórmula P(n) é verdadeira para todo n ∈ N. PROFMAT - SBM MA12 - Unidade 3, O Poder do Método de Indução slide 6/9 Exemplo Mostrar que 3 divide 5n + 2 ·11n nos inteiros, para todo n ∈ N i) Para n = 1, temos que 3 divide 51 + 2 · 111 = 27. ii) Suponha, agora, que, para algum n ≥ 1, saibamos que 3 divide 5n + 2 · 11n. Logo, 5n + 2 · 11n = 3a, para algum inteiro a. Mutiplicando por 11 ambos os lados: 11 · 3a = 11 · 5n + 2 · 11n+1 = 5n+1 + 6 · 5n + 2 · 11n+1. Dáı: 5n+1 + 2 · 11n+1 = 11 · 3a− 6 · 5n = 3(11a− 2 · 5n) Portanto, 3 divide 5n+1 + 2 · 11n+1. Logo, pelo Prinćıpio de Indução Matemática, 3 divide 5n + 2 · 11n, para todo número natural n. PROFMAT - SBM MA12 - Unidade 3, O Poder do Método de Indução slide 7/9 Generalizando o Prinćıpio da Indução Matemática Seja P(n) uma sentença sobre N, e seja a ∈ N. Suponha que: i) P(a) é verdadeira, ii) Qualquer que seja n ∈ N, com n ≥ a, sempre que P(n) é verdadeira, segue-se que P(n + 1) é verdadeira. Então, P(n) é verdadeira para todo número natural n ≥ a. Prova: Basta mostrar, por indução, que o conjunto S = {m ∈ N; P(m + a− 1) é verdadeira} é igual a N. PROFMAT - SBM MA12 - Unidade 3, O Poder do Método de Indução slide 8/9 Exemplo Mostrar que P(n) : 2n > n2, para todo número natural n ≥ 5. i) Temos que P(5) : 25 > 52 é verdadeira. ii) Seja n ≥ 5 tal que 2n > n2. Multiplicando ambos os lados da desigualdade acima por 2, obtemos 2n+1 > 2n2. Mas 2n2 > (n + 1)2? Sim, para n ≥ 3, pois é equivalente a n(n − 2) > 1. Dáı, 2n+1 > (n + 1)2, o que significa que P(n + 1) é verdadeira. Logo, pela forma generalizada do Prinćıpio de Indução Matemática, a desigualdade vale para todo número natural n ≥ 5. PROFMAT - SBM MA12 - Unidade 3, O Poder do Método de Indução slide 9/9 MA12 - Unidade 4 Aplicações do Prinćıpio de Indução Matemática Paulo Cezar Pinto Carvalho PROFMAT - SBM 28 de Fevereiro de 2013 A Torre de Hanói �� ���� ���� ���� �� �� �� Transferir a pilha de discos para uma outra haste, deslocando um disco de cada vez, de modo que, a cada passo, um disco nunca esteja colocado sobre um disco menor. 1 O jogo tem solução para cada n ∈ N? 2 Em caso afirmativo, qual é o número ḿınimo jn de movimentos pararesolver o problema com n discos? PROFMAT - SBM MA12 - Unidade 4, Aplicações do Prinćıpio de Indução Matemática slide 2/12 Torre de Hanói: o jogo sempre tem solução! Obviamente, o jogo tem solução para n = 1. Suponhamos que o jogo tenha solução para n discos e vamos mostrar que, dáı, decorre que o jogo também tem solução para n + 1 discos. Primeiro, transferimos os n discos superiores para uma das outras hastes (isto é posśıvel, pela hipótese de indução). �� �� �� ���� ���� ���� �� �� �� PROFMAT - SBM MA12 - Unidade 4, Aplicações do Prinćıpio de Indução Matemática slide 3/12 A seguir, transferimos o disco inferior para a outra haste. �� �� �� ���� ���� ���� �� �� �� Finalmente, transferimos os demais n discos para a haste em que colocamos o disco maior (é posśıvel, pela hipótese de indução e pelo fato de o disco inferior ser maior que todos os outros) �� ���� ���� ���� �� �� ���� �� Pelo Prinćıpio da Indução, conclúımos que o jogo tem solução para todo n ∈ N. Torre de Hanói: Qual é o número ḿınimo de movimentos? Executar a tarefa para n + 1 discos necessariamente envolve retirar os n discos superiores, colocando-os em outra haste e, depois de mover o disco inferior, recolocá-los sobre ele. O número ḿınimo jn de movimentos é, portanto, tal que j1 = 1 jn+1 = jn + 1 + jn = 2jn + 1, para todo n ∈ N. É fácil mostrar, por indução, que jn = 2 n − 1. (Na Unidade 8, aprenderemos a encontrar a expressão para o termo geral de sequências definidas por recorrências como esta.) PROFMAT - SBM MA12 - Unidade 4, Aplicações do Prinćıpio de Indução Matemática slide 5/12 Os coelhos de Fibonacci Um casal de coelhos recém-nascidos foi posto num lugar cercado. Determinar quantos casais de coelhos ter-se-ão após um ano, supondo que, a cada mês, um casal de coelhos produz outro casal e que um casal começa a procriar dois meses após o seu nascimento. mês número de casais do mês anterior número de casais recém-nascidos total 1o 0 1 1 2o 1 0 1 3o 1 1 2 4o 2 1 3 5o 3 2 5 6o 5 3 8 7o 8 5 13 8o 13 8 21 PROFMAT - SBM MA12 - Unidade 4, Aplicações do Prinćıpio de Indução Matemática slide 6/12 O número de casais de coelhos em um determinado mês (a partir do terceiro) é igual ao número total de casais do mês anterior acrescido do número de casais nascidos no mês em curso, que é igual ao número total de casais do mês anterior ao anterior. Se un é o número de casais no n-ésimo mês, temos u1 = 1 u2 = 1 un+2 = un + un+1, para todo n ∈ N Estas relações definem a chamada sequência de Fibonacci. Retornaremos a ela na Unidade 8, quando obteremos uma expressão para o seu termo geral: un = ( 1+ √ 5 2 )n − ( 1− √ 5 2 )n √ 5 PROFMAT - SBM MA12 - Unidade 4, Aplicações do Prinćıpio de Indução Matemática slide 7/12 A Pizza de Steiner Qual é o maior número de partes em que se pode dividir o plano com n cortes retos? Número de cortes Número máximo de partes 1 2 2 4 3 7 . . . . . . n − 1 pn−1 n pn n + 1 pn+1 O padrão observado acima sugere que o número máximo de pedaços obtidos com n cortes é: pn = 2 + 2 + 3 + . . . + n = n(n + 1) 2 + 1 . PROFMAT - SBM MA12 - Unidade 4, Aplicações do Prinćıpio de Indução Matemática slide 8/12 A Pizza de Steiner: prova por indução Com apenas um corte obtemos dois pedaços. Portanto, a fórmula está correta para n = 1, pois p1 = 1(1+1) 2 + 1 = 2. Admitamos que, para algum valor de n, a fórmula para pn esteja correta. Vamos mostrar que a fórmula para pn+1 também está correta. O ponto crucial é mostrar que são acrescentados n + 1 pedaços no (n + 1)-ésimo corte. PROFMAT - SBM MA12 - Unidade 4, Aplicações do Prinćıpio de Indução Matemática slide 9/12 Para que o (n + 1)-ésimo corte produza o número máximo de pedaços, ele deve encontrar cada um dos n cortes anteriores em pontos que não são de interseção de dois cortes. Neste caso, como n pontos subdividem uma reta em n+ 1 partes, ele subdivide n + 1 regiões, criando assim, n + 1 novos pedaços. Logo, pn+1 = pn +n+1 = n(n + 1) 2 +1+n+1 = (n + 1)(n + 2) 2 +1 o que mostra que a fórmula está correta para n + 1. Pelo Prinćıpio da Indução, a fórmula está correta para todo n ∈ N. PROFMAT - SBM MA12 - Unidade 4, Aplicações do Prinćıpio de Indução Matemática slide 10/12 O enigma do cavalo de Alexandre O cavalo de Napoleão era branco, eanquanto o de Alexandre tinha cor de bronze. No entanto, vamos “provar” que todos os cavalos têm a mesma cor! Considere a sentença: P(n) : Num conjunto com n cavalos, todos têm a mesma cor. P(1) é obviamente verdadeira. PROFMAT - SBM MA12 - Unidade 4, Aplicações do Prinćıpio de Indução Matemática slide 11/12 Suponha o resultado válido para conjuntos contendo n cavalos e considere um conjunto C = {C1,C2, . . . ,Cn,Cn+1}, com n + 1 cavalos. Pela hipótese de indução: Os cavalos em {C1,C2, . . . ,Cn} têm a mesma cor. Os cavalos em {C2, . . . ,Cn,Cn+1} têm a mesma cor Como estas coleções têm cavalos em comum, conclúımos que todos os cavalos em C têm a mesma cor (ou seja, o resultado também é válido para conjuntos com n + 1 cavalos). Logo, pelo Prinćıpio da Indução, em um conjunto com n cavalos, todos têm a mesma cor, para todo n ∈ N. (!!!) PROFMAT - SBM MA12 - Unidade 4, Aplicações do Prinćıpio de Indução Matemática slide 12/12 MA12 - Unidade 5 Progressões Aritméticas Paulo Cezar Pinto Carvalho PROFMAT - SBM 9 de Março de 2013 Sequências Numéricas Progressões Aritméticas são casos particulares de sequências numéricas. Uma sequência numérica é uma função x : N→ R. É comum denotar x(n) por xn e usar (xn) para representar a sequência. PROFMAT - SBM MA12 - Unidade 5, Progressões Aritméticas slide 2/16 Progressões Aritméticas Uma progressão aritmética é uma sequência na qual a diferença entre cada termo e o termo anterior é constante. Essa diferença constante é chamada de razão da progressão e representada pela letra r . Mais formalmente: (an) é uma progressão aritmética quando existe um número real r tal que an+1 = an + r , para todo n ∈ N. PROFMAT - SBM MA12 - Unidade 5, Progressões Aritméticas slide 3/16 Termo Geral Em uma progressão aritmética (an) para avançar um termo, basta somar a razão; para avançar dois termos, basta somar duas vezes a razão; e assim por diante; Por exemplo, a13 = a5 + 8r De modo geral, an = a1 + (n − 1)r , pois, ao passar de a1 para an, avançamos n − 1 termos. PROFMAT - SBM MA12 - Unidade 5, Progressões Aritméticas slide 4/16 Exemplo O cometa Halley visita a Terra a cada 76 anos. Sua última passagem por aqui foi em 1986. Quantas vezes ele visitou a Terra desde o nascimento de Cristo? Em que ano foi sua primeira passagem na era cristã? Os anos de passagem do cometa foram 1986, 1910, 1834,... e formam uma progressão aritmética de razão −76. O termo de ordem n dessa progressão é an = a1 + (n − 1)r = 1986− 76(n − 1) = 2062− 76n. Temos an > 0 quando n < 2062 76 = 27, 13 . . . . Portanto, os termos positivos dessa progressão são os 27 primeiros. Logo, ele nos visitou 27 vezes na era cristã e sua primeira passagem na era cristã foi no ano a27 = 2062− 76× 27 = 10. PROFMAT - SBM MA12 - Unidade 5, Progressões Aritméticas slide 5/16 Começando de a0 ou a1? O preço de um carro novo é de R$ 15 000,00 e diminui de R$1 000,00 a cada ano de uso. Qual será o preço com 4 anos de uso? Chamando o preço com n anos de uso de an, temos a0 = 15000 e queremos calcular a4. Como a desvalorização anual é constante, (an) é uma progressão aritmética. Logo, a4 = a0 + 4r = 15000 + 4× (−1000) = 11000, ou seja, o preço será de R$11 000,00. PROFMAT - SBM MA12 - Unidade 5, Progressões Aritméticas slide 6/16 Progressões aritméticas e funções afins Em uma progressão aritmética de razão não nula, o termo geral é dado por um polinômio do primeiro grauem n: an = a1 + (n − 1)r = r . n + (a1 − r). Reciprocamente, se em uma sequência o termo de ordem n for dado por um polinômio do primeiro grau em n ela será uma progressão aritmética de razão não nula. Com efeito, se xn = an + b, (xn) é uma progressão aritmética na qual r = a e a1 = a + b. PROFMAT - SBM MA12 - Unidade 5, Progressões Aritméticas slide 7/16 O gráfico de uma progressão aritmética Portanto, uma progressão aritmética pode ser vista como uma função afim, restrita ao doḿınio dos números naturais. Em consequência, o gráfico de uma progressão aritmética é um conjunto de pontos igualmente espaçados sobre uma reta. PROFMAT - SBM MA12 - Unidade 5, Progressões Aritméticas slide 8/16 Soma dos termos de uma progressão aritmética Sn = a1 + a2 + . . . + an−1 + an Sn = an + an−1 + . . . + a2 + a1 2Sn = (a1 + an) + (a1 + an) + . . . + (a1 + an) + (a1 + an) Sn = (a1 + an)n 2 . PROFMAT - SBM MA12 - Unidade 5, Progressões Aritméticas slide 9/16 Exemplos A soma dos n primeiros números inteiros e positivos é 1 + 2 + 3 + · · ·+ n = n(n + 1) 2 = n2 2 + n 2 . A soma dos n primeiros números ı́mpares é 1 + 3 + 5 + · · ·+ (2n − 1) = (1 + 2n − 1)n 2 = n2. Em ambos os casos, a expressão da soma é dada por um polinômio do segundo grau em n, sem termo independente, PROFMAT - SBM MA12 - Unidade 5, Progressões Aritméticas slide 10/16 Soma dos termos de PAs e funções quadráticas Sn = (a1 + an)n 2 = [a1 + a1 + (n − 1)r ]n 2 = r 2 n2 + ( a1 − r 2 ) n. O termo geral da sequência (Sn) das somas dos n primeiros termos de uma progressão artimética com r 6= 0 é dado por um polinômio do segundo grau sem termo independente. Reciprocamente, todo polinômio do segundo grau em n sem termo independente é o valor da soma dos n primeiros termos de alguma progressão aritmética com r 6= 0. PROFMAT - SBM MA12 - Unidade 5, Progressões Aritméticas slide 11/16 Progressões Aritméticas de Segunda Ordem O Operador ∆ (ou de diferença) para uma sequência é definido por: ∆an = an+1 − an Uma sequência (an) é uma progressão aritmética se e somente se (∆an) é uma sequência constante. Dizemos que uma sequência (an) é uma progressão aritmética de segunda ordem quando (∆an) é uma progressão aritmética não constante. A sequência (Sn) da soma dos n primeiros termos de uma progressão aritmética é uma progressão aritmética de segunda ordem. PROFMAT - SBM MA12 - Unidade 5, Progressões Aritméticas slide 12/16 Teorema Uma sequência é uma progressão aritmética de segunda ordem se e somente se seu termo geral é dado por um polinômio do segundo grau. Se an = an 2 + bn + c , então ∆an = a(n+1) 2+b(n+1)+c−an2−bn−c = 2an+(2a+b), que é um polinômio do primeiro grau. Logo, (∆an) é uma P.A. não constante e (an) é P.A. de segunda ordem. Se (an) é P.A. de segunda ordem, então (bn) = (∆an) é uma P.A. não constante. Mas an = a1 + (b1 + ... + bn−1). A soma em parênteses é a soma dos n − 1 primeiros termos da P.A. (bn); logo tanto esta soma quanto an são expressos por polinômios do segundo grau em n. PROFMAT - SBM MA12 - Unidade 5, Progressões Aritméticas slide 13/16 Revisitando a Pizza de Steiner Qual é o maior número de partes em que se pode dividir o plano com n cortes retos? Número de cortes (n) Número máximo de partes (pn) 1 2 2 4 3 7 4 11 No n-ésimo corte, n regiões são acrescentadas. Portanto, (∆pn) é uma P.A. e pn é uma P.A. de segunda ordem. A expressão de pn é da forma pn = an 2 + bn + c . Mas p(1) = a + b + c = 2 p(2) = 4a + 2b + c = 4 p(3) = 9a + 3b + c = 7 Resolvendo o sistema, encontramos a = 12 , b = 1 2 e c = 1 e pn = n2 + n + 2 2 PROFMAT - SBM MA12 - Unidade 5, Progressões Aritméticas slide 14/16 Progressões Aritméticas de Ordem Superior Definição Uma sequência (an) é progressão aritmética de ordem k quando ∆an é progressão aritmética de ordem k − 1. Observação: definição por recorrência Teorema: Uma sequência é uma progressão aritmética de ordem k se e somente se seu termo geral é um polinômio de grau k. Ver demonstração no livro-texto. PROFMAT - SBM MA12 - Unidade 5, Progressões Aritméticas slide 15/16 Uma aplicação Obter uma expressão para a soma Sn = 1 2 + 22 + . . . + n2 Como ∆Sn = (n + 1) 2 é um polinômio de segundo grau, ∆Sn é uma P.A. de segunda ordem. Portanto Sn é uma P.A. de terceira ordem e seu termo geral é da forma Sn = an 3 + bn2 + cn + d . Para calcular os valores de a, b, c e d , basta usar os valores de Sn para n = 1, 2, 3 e 4. a + b + c + d = 1 8a + 4b + 2c + d = 5 27a + 9b + 3c + d = 14 64a + 16b + 4c + d = 30 Resolvendo: a = 1 3 , b = 1 2 , c = 1 6 , d = 0. Então 12 + 22 + 32 + · · ·+n2 = 1 3 n3 + 1 2 n2 + 1 6 n = n(n + 1)(2n + 1) 6 . PROFMAT - SBM MA12 - Unidade 5, Progressões Aritméticas slide 16/16 MA12 - Unidade 6 Progressões Geométricas Paulo Cezar Pinto Carvalho PROFMAT - SBM 10 de Março de 2013 Progressões Geométricas Uma progressão geométrica é uma sequência na qual o quociente entre cada termo e o termo anterior é constante. Esse quociente constante é chamado de razão da progressão e representado pela letra q. Mais formalmente: (an) é uma progressão geométrica quando existe um número real q tal que an+1 = an · q, para todo n ∈ N. PROFMAT - SBM MA12 - Unidade 6, Progressões Geométricas slide 2/11 Termo Geral Em uma progressão geométrica (an) para avançar um termo, basta multiplicar pela razão; para avançar dois termos, basta multiplicar duas vezes pela razão; e assim por diante; Por exemplo, a13 = a5 · q8 De modo geral, an = a1q n−1, pois, ao passar de a1 para an, avançamos n − 1 termos. PROFMAT - SBM MA12 - Unidade 6, Progressões Geométricas slide 3/11 Começando de a0 ou a1? A população de um páıs é hoje igual a 100.000 habitantes e cresce 2% ao ano. Qual será a população desse páıs daqui a 10 anos? Em 10 peŕıodos, a população é multiplicada 10 vezes por 1,02 a10 = a0 · q10 = 100.000 · 1, 0210 = 121.899 habitantes. PROFMAT - SBM MA12 - Unidade 6, Progressões Geométricas slide 4/11 Exemplo Uma pessoa, começando com R$ 64,00, faz seis apostas consecutivas, em cada uma das quais arrisca perder ou ganhar a metade do que possui na ocasião. Se ela ganha três e perde três dessas apostas, pode-se afirmar que ela: A) Ganha dinheiro. B) Não ganha dinheiro nem perde dinheiro. C) Perde R$ 27,00. D) Perde R$ 37,00. E) Ganha ou perde dinheiro, dependendo da ordem em que ocorreram suas vitórias e derrotas V, V, D, V, D, D: 64 → 96 → 144 → 72 → 108 → 54 → 27 D, V, D, D, V, V: 64 → 32 → 48 → 24 → 12 → 18 → 27 O valor final é sempre R$ 27,00? PROFMAT - SBM MA12 - Unidade 6, Progressões Geométricas slide 5/11 A cada vitória, a quantia é multiplicada por 32 ; a cada derrota, é multiplicada por 12 . Após três vitórias e três derrotas, os R$ 64,00 são multiplicados três vezes por 32 e três vezes por 1 2 . Logo, ao final, independentemente da ordem das vitórias e derrotas, a pessoa terá 64 ( 3 2 )3(1 2 )3 = 27 reais; ou seja, ela perde 37 reais (alternativa D). PROFMAT - SBM MA12 - Unidade 6, Progressões Geométricas slide 6/11 Progressões geométricas e funções exponenciais Como em uma progressão geométrica an = a0q n, a função que associa a cada natural n o valor de an é simplesmente a restrição aos naturais da função exponencial a(x) = a0q x . O gráfico de uma progressão geométrica: PROFMAT - SBM MA12 - Unidade 6, Progressões Geométricas slide 7/11 Soma dos termos de uma progressão geométrica Sn = a1 + a2 + a3 + . . . + an−1 + an qSn = a2 + a3 + a4 + · · ·+ an + an+1 Sn − qSn = a1 − an+1 (1− q)Sn = a1(1− qn) Sn = a1 + a2 + . . . + an = a1 1− qn 1− q PROFMAT - SBM MA12 - Unidade 6, Progressões Geométricas slide 8/11 Mostre que o número 444 . . . 488 . . . 89, formado por n d́ıgitos iguais a 4, n − 1 d́ıgitos iguais a 8 e um d́ıgitoigual a 9, é um quadrado perfeito e determine sua raiz quadrada. 444 . . . 488 . . . 89 = 4 ( 102n−1 + . . . + 10n ) + 8 ( 10n−1 + . . . + 10 ) + 9 = 4 · 10n · 10 n − 1 10− 1 + 80 · 10 n−1 − 1 10− 1 + 9 = 4 · 102n + 4 · 10n + 1 9 = ( 2 · 10n + 1 3 )2 Logo 444 . . . 488 . . . 89 é um quadrado perfeito e sua raiz quadrada é 2 · 10n + 1 3 = 20 . . . 01 3 (n − 1 zeros) = 6 . . . 67 (n − 1 seis). PROFMAT - SBM MA12 - Unidade 6, Progressões Geométricas slide 9/11 Limite da soma dos termos de uma progressão geométrica Sn = a1 + a2 + . . . + an = a1 1− qn 1− q Quando |q| < 1, temos lim n→∞ qn = 0. Em consequência, lim n→∞ Sn = lim n→∞ a1 1− qn 1− q = a1 1− 0 1− q Logo: lim n→∞ Sn = a1 + a2 + . . . = a1 1− q . PROFMAT - SBM MA12 - Unidade 6, Progressões Geométricas slide 10/11 Exemplo Qual é o limite da soma 0, 3 + 0, 03 + 0, 003 + . . . quando o número de parcelas tende a infinito? 0, 3 + 0, 03 + 0, 003 + . . . = 0, 3 1− 0, 1 = 1 3 . Em outras palavras, a geratriz da d́ızima periódica 0, 33333 · · · é 1 3 . PROFMAT - SBM MA12 - Unidade 6, Progressões Geométricas slide 11/11 MA12 - Unidade 7 Recorrências Lineares de Primeira Ordem Paulo Cezar Pinto Carvalho PROFMAT - SBM 17 de Março de 2013 Sequências definidas por recorrência Sequências definidas por regras que permitem calcular qualquer termo em função dos anteriores (usualmente do antecessor imediato ou de uma quantidade pequena de antecessores imediatos). Uma progressão aritmética de primeiro termo a e razão r : x1 = a, xn+1 = xn + r , para n ≥ 1 A sequência de Fibonacci: x1 = 1, x2 = 1, xn+2 = xn + xn+1, para n ≥ 1. Equivalentemente, x1 = 1, x2 = 1, xn = xn−2 + xn−1, para n ≥ 3. Não basta dar a lei de recorrência; é preciso também fornecer o(s) primeiro(s) termo(s) PROFMAT - SBM MA12 - Unidade 7, Recorrências Lineares de Primeira Ordem slide 2/10 Exemplo Quantas são as sequências de 10 termos, pertencentes a {0, 1, 2}, que não têm dois termos consecutivos iguais a 0? Seja xn o número de sequências com n termos respeitando as condições do enunciado. Vamos contar separadamente as sequências, de acordo com seu termo inicial. O número dessas sequências começando por 1 é xn−1 . O número dessas sequências começando por 2 também é xn−1. O número dessas sequências começando por 0 é 2xn−2 Logo xn = 2xn−1 + 2xn−2, para n ≥ 3. Além disso, x1 = 3 Dáı, obtemos x3 = 2x2 + 2x1 = 22, x6 = 448, PROFMAT - SBM MA12 - Unidade 7, Recorrências Lineares de Primeira Ordem slide 3/10 Recorrências Lineares de Primeira Ordem Uma recorrência de primeira ordem expressa xn+1 em função de xn. Ela é dita linear quando essa função for do primeiro grau. As recorrências xn+1 = 2xn − n2 e xn+1 = nxn são lineares e a recorrência xn+1 = x 2 n não é linear. As duas últimas são ditas homogêneas, por não possuirem termo independente de xn. PROFMAT - SBM MA12 - Unidade 7, Recorrências Lineares de Primeira Ordem slide 4/10 Recorrências lineares homogêneas Resolver a recorrência xn+1 = nxn. x2 = 1x1 x3 = 2x2 x4 = 3x3 . . . . . . . . . xn = (n − 1)xn−1 Multiplicando: xn = (n − 1)!x1 Solução geral: xn = C · (n − 1)! PROFMAT - SBM MA12 - Unidade 7, Recorrências Lineares de Primeira Ordem slide 5/10 Recorrências lineares da forma xn+1 = xn + f (n) x2 = x1 + f (1) x3 = x2 + f (2) x4 = x3 + f (3) . . . . . . . . . xn = xn−1 + f (n − 1) Somando: xn = x1 + n−1∑ k=1 f (k). PROFMAT - SBM MA12 - Unidade 7, Recorrências Lineares de Primeira Ordem slide 6/10 Exemplo Resolver a recorrência xn+1 = xn + 2 n, x1 = 1. x2 = x1 + 2 x3 = x2 + 2 2 x4 = x3 + 2 3 . . . . . . . . . xn = xn−1 + 2 n−1 Somando: xn = x1 + (2 + 2 2 + 23 + · · ·+ 2n−1) = 1 + 2 + 22 + 23 + · · ·+ 2n−1 = 1 2n − 1 2− 1 = 2n − 1. PROFMAT - SBM MA12 - Unidade 7, Recorrências Lineares de Primeira Ordem slide 7/10 Recorrências lineares não homogêneas em geral Se an é uma solução não-nula da recorrência xn+1 = g(n)xn, então a substituição xn = anyn transforma a recorrência xn+1 = g(n)xn + h(n) em yn+1 = yn + h(n) g(n) · an A substituição xn = anyn transforma xn+1 = g(n)xn + h(n) em an+1yn+1 = g(n)anyn + h(n). Mas, an+1 = g(n)an, pois an é solução de xn+1 = g(n)xn. Portanto, a equação se transforma em g(n)anyn+1 = g(n)anyn + h(n), Ou seja, em yn+1 = yn + h(n) g(n) · an . PROFMAT - SBM MA12 - Unidade 7, Recorrências Lineares de Primeira Ordem slide 8/10 Exemplo Resolver xn+1 = 2xn + 1, x1 = 2 Uma solução não-nula de xn+1 = 2xn é, por exemplo, xn = 2 n−1. Fazendo a substituição xn = 2 n−1yn, obtemos 2nyn+1 = 2 nyn + 1, ou seja, yn+1 = yn + 2 −n. Dáı: y2 = y1 + 2 −1 y3 = y2 + 2 −2 . . . . . . . . . yn = yn−1 + 2 −(n−1). Somando: yn = y1 + 2 −1 + 2−2 + · · ·+ 2−(n−1) = y1 + 1− 2−(n−1). PROFMAT - SBM MA12 - Unidade 7, Recorrências Lineares de Primeira Ordem slide 9/10 A recorrência original é xn+1 = 2xn + 1, x1 = 2. Fizemos a substituição xn = 2 n−1yn e obtivemos a solução yn = y1 + 1− 2−(n−1) para a nova recorrência. Dáı, xn = 2 n−1yn = 2 n−1 (y1 + 1− 2−(n−1)) = 2n−1y1 + 2n−1 − 1 = (1 + y1)2 n−1 − 1 Finalmente, de x1 = 2 e de xn = 2 n−1yn, temos 2 = 2 0y1. Logo, y1 = 2 e a solução da recorrência é xn = 3 · 2n−1 − 1, para n ≥ 1 PROFMAT - SBM MA12 - Unidade 7, Recorrências Lineares de Primeira Ordem slide 10/10 MA12 - Unidade 8 Recorrências Lineares de Segunda Ordem Paulo Cezar Pinto Carvalho PROFMAT - SBM 17 de Março de 2013 Recorrências lineares de segunda ordem homogêneas com coeficientes constantes São recorrências da forma xn+2 + pxn+1 + qxn = 0, com q 6= 0 (se q = 0, a recorrência é, na verdade, de primeira ordem) A equação caracteŕıstica da recorrência é: r2 + pr + q = 0 Veremos a seguir que as ráızes da equação caracteŕıstica desempenham um papel fundamental na expressão da solução geral para a recorrência. Como q 6= 0, essas ráızes são necessariamente não nulas. PROFMAT - SBM MA12 - Unidade 8, Recorrências Lineares de Segunda Ordem slide 2/14 Ráızes da equação caracteŕıstica e soluções da recorrência Se r é tal que r2 + pr + q = 0 , então xn = r n é solução da recorrência xn+2 + pxn+1 + qxn = 0. Substituindo xn = r n na recorrência: xn+2 + pxn+1 + qxn = r n+2 + prn+1 + qrn = rn(r2 + pr + q) = rn · 0 = 0. PROFMAT - SBM MA12 - Unidade 8, Recorrências Lineares de Segunda Ordem slide 3/14 Consequência: Se r1 e r2 são ráızes distintas de r2 + pr + q = 0, então xn = C1r n 1 + C2r n 2 é solução da recorrência xn+2 + pxn+1 + qxn = 0, quaisquer que sejam os valor das constantes C1 e C2. Sejam yn = r n 1 , zn = r n 2 e xn = C1yn + C2zn. xn+2 + pxn+1 + qxn = (C1yn+2 + C2zn+2) + p(C1yn+1 + C2zn+1) + q(C1yn + C2zn) = C1(yn+2 + pyn+1 + qyn) + C2(zn+2 + pzn+1 + qzn) = = C1 · 0 + C2 · 0 = 0, já que yn e zn são soluções da recorrência. (De modo geral, se yn e zn são soluções de uma recorrência linear homogênea, qualquer combinação linear de yn e zn também é solução da recorrência.) PROFMAT - SBM MA12 - Unidade 8, Recorrências Lineares de Segunda Ordem slide 4/14 Resolvendo a recorrência: caso r1 6= r2 Se as ráızes de r2 + pr + q = 0 (q 6= 0) são r1 e r2, com r1 6= r2, então todas as soluções da recorrência xn+2 + pxn+1 + qxn = 0 são da forma an = C1r n 1 + C2r n 2 , C1 e C2 constantes. Seja (xn) uma solução qualquer de xn+2 + pxn+1 + qxn = 0. É sempre posśıvel escolher constantes C1 e C2 tais que: C1r1 + C2r2 = x1 C1r 2 1 + C2r 2 2 = x2 (o sistema sempre tem solução única). Vamos provar que xn = C1r n 1 + C2r n 2 para todo n natural. PROFMAT - SBM MA12 - Unidade 8, Recorrências Lineares de Segunda Ordem slide 5/14 A afirmativa vale para n = 1 e n = 2, já que C1 e C2 foram escolhidos de modo que isto ocorra. Suponhamos válida para naturais n e n + 1. Temos xn+2 + pxn+1 + qxn = 0. Logo xn+2 = −p(C1rn+11 + C2r n+1 2 )− q(C1rn1 + C2rn2 ) = −C1rn1(pr1 + q)− C2rn2 (pr2 + q) Somando e subtraindo C1r n+2 2 + C2r n+2 2 : xn+2 = −C1rn1 (r21 + pr1 + q)−C2rn2 (r22 + pr2 + q) + C1r n+2 2 + C2r n+2 2 Mas as expressões entre parênteses se anulam, levando a xn+2 = C1r n+2 2 + C2r n+2 2 , o que completa a prova por indução. PROFMAT - SBM MA12 - Unidade 8, Recorrências Lineares de Segunda Ordem slide 6/14 Exemplo Determinar as soluções da recorrência xn+2 + 3xn+1 − 4xn = 0. A equação caracteŕıstica r2 + 3r − 4 = 0, tem ráızes 1 e −4. As soluções da recorrência são as sequências da forma xn = C11 n + C2(−4)n, isto é, xn = C1 + C2(−4)n, onde C1 e C2 são constantes arbitrárias. PROFMAT - SBM MA12 - Unidade 8, Recorrências Lineares de Segunda Ordem slide 7/14 A sequência de Fibonacci F0 = F1 = 1,Fn+2 = Fn+1 + Fn, para n ≥ 0. A equação caracteŕıstica é r2 − r − 1 = 0, que tem ráızes r1 = 1 + √ 5 2 e r2 = 1− √ 5 2 . Logo: Fn = C1 ( 1 + √ 5 2 )n + C2 ( 1− √ 5 2 )n . Os valores de C1 e C2 são obtidos usando F0 = F1 = 1: C1 + C2 = 1 C1 1+ √ 5 2 + C2 1− √ 5 2 = 1 PROFMAT - SBM MA12 - Unidade 8, Recorrências Lineares de Segunda Ordem slide 8/14 Resolvendo o sistema, encontramos: C1 = √ 5 + 1 2 √ 5 e C2 = √ 5− 1 2 √ 5 Logo: Fn = √ 5 + 1 2 √ 5 ( 1 + √ 5 2 )n + √ 5− 1 2 √ 5 ( 1− √ 5 2 )n = 1√ 5 ( 1 + √ 5 2 )n+1 − 1√ 5 ( 1− √ 5 2 )n+1 . PROFMAT - SBM MA12 - Unidade 8, Recorrências Lineares de Segunda Ordem slide 9/14 O caso r1 = r2 Se as ráızes de r2 + pr + q = 0 são iguais (r1 = r2 = r) então yn = nr n é solução da recorrência xn+2 + pxn+1 + qxn = 0. Como zn = r n também é solução, xn = C1r n + C2nr n é solução da recorrência, quaisquer que sejam as constantes C1 e C2. Substituindo na recorrência: yn+2 + pyn+1 + qyn = (n + 2)r n+2 + p(n + 1)rn+1 + qnrn = nrn(r2 + pr1 + q) + r n+1(2r + p). O primeiro parênteses é igual a zero (r é raiz da equação caracteŕıstica); como as ráızes da equação caracteŕıstica são iguais, temos r = −p2 . Logo, 2r + p = 0 e o segundo parênteses também é igual a zero. Logo, yn = nr n e, de modo mais geral, xn = C1r n + C2nr n, é solução da recorrência. PROFMAT - SBM MA12 - Unidade 8, Recorrências Lineares de Segunda Ordem slide 10/14 Resolvendo a recorrência: caso r1 = r2 Se as ráızes de r2 + pr + q = 0 são iguais, r1 = r2 = r , então todas as soluções da recorrência xn+2 + pxn+1 + qxn = 0 são da forma C1r n + C2nr n, C1 e C2 constantes. A prova é análoga ao caso em que r1 6= r2. primeiro, observamos que podemos escolher as constantes C1 e C2 de modo que C1r + C2r = x1 C1r 2 + 2C2r 2 = x2 , (o sistema tem solução única para todo r 6= 0). depois, verificamos por indução que xn = C1r n + C2nr n, para todo n ≥ 1. PROFMAT - SBM MA12 - Unidade 8, Recorrências Lineares de Segunda Ordem slide 11/14 Exemplo Resolver a recorrência xn+2 − 4xn+1 + 4xn = 0. A equação caracteŕıstica é r2 − 4r + 4 = 0. As ráızes são r1 = r2 = 2. A solução da recorrência é xn = C12 n + C2n2 n. PROFMAT - SBM MA12 - Unidade 8, Recorrências Lineares de Segunda Ordem slide 12/14 E se a recorrência não for homogênea? Suponhamos que an seja uma solução da recorrência xn+2 + pxn+1 + qxn = f (n). Toda solução da recorrência é da forma an + yn, onde yn é uma solução da recorrência homogênea xn+2 + pxn+1 + qxn = 0. (Logo, para encontrar a solução geral de uma recorrência não homogênea, ”basta”encontrar uma solução particular e somá-la à solução geral da recorrência homogênea.) Seja xn uma solução da recorrência. Temos: xn+2 + pxn+1 + qxn = f (n) an+2 + pan+1 + qan = f (n) Subtraindo: (xn+2 − an+2) + p(xn+1 − an+1) + q(xn − an) = 0 Logo, yn = xn − an é uma solução da recorrência homogênea, o que equivale a dizer que xn = an + yn, onde yn é solução da recorrência homogênea. PROFMAT - SBM MA12 - Unidade 8, Recorrências Lineares de Segunda Ordem slide 13/14 Exemplo Considere a recorrência xn+2 − 5xn+1 + 6xn = 2. Encontre uma solução particular constante para a recorrência. Encontre a solução geral da recorrência. Ache a solução da recorrência em que x1 = 0 e x2 = 2. Para que an = C seja solução, deve-se ter C − 5C + 6C = 2, ou seja, C = 1 A equação caracteŕıstica da recorrência homogênea é r2 − 5r + 6 = 0, cujas ráızes são r1 = 3 e r2 = 2. A solução geral da recorrência homogênea é yn = C1 · 3n + C2 · 2n e a solução geral da recorrência original é xn = yn + an, isto é: xn = C1 · 3n + C2 · 2n + 1 Para que x1 = 0 e x2 = 2, deve-se ter{ 3C1 + 2C2 + 1 = 0 9C1 + 4C2 + 1 = 2 Resolvendo o sistema, encontramos C1 = 1 e C2 = −2, que leva à solução: xn = 3 n − 2.2n + 1 PROFMAT - SBM MA12 - Unidade 8, Recorrências Lineares de Segunda Ordem slide 14/14 MA12 - Unidade 9 Matemática Financeira Paulo Cezar Pinto Carvalho PROFMAT - SBM 31 de Março de 2013 Conceitos Básicos Principal (P): capital investido Juro (J): remuneração do capital Montante (M = P + J): principal acrescido do juro Taxa de juros (i = J P ): razão entre juro e principal (referido à duração do investimento) PROFMAT - SBM MA12 - Unidade 9, Matemática Financeira slide 2/14 Juros Compostos Regime de investimento em que o capital é reinvestido por sucessivos peŕıodos, acrescido dos juros. (que sempre incidem sobre o capital acumulado). Exemplo: Principal de R$ 10000,00, investidos por 3 meses à taxa de 2% ao mês. Ao final do 1o mês: M = 10000 + 0, 02 · 10000 = 10200 Ao final do 2o mês: M = 10200 + 0, 02 · 10200 = 10404 Ao final do 3o mês: M = 10404 + 0, 02 · 10404 = 10612, 08 PROFMAT - SBM MA12 - Unidade 9, Matemática Financeira slide 3/14 Teorema No regime de juros compostos de taxa i , um principal C0 transforma-se, depois de n peŕıodos de tempo, em um montante Cn = C0(1 + i) n. No exemplo anterior, o montante ao final de 3 meses é: M = 10000 · (1 + 0, 02)3 = 10612, 08 PROFMAT - SBM MA12 - Unidade 9, Matemática Financeira slide 4/14 Juros compostos × juros simples Juros simples: M = C · (1 + n · i) Juros compostos: M = C · (1 + i)n Muito raramente, o modelo de juros simples é realista, já que os juros estão dispońıveis para reinvestimento. PROFMAT - SBM MA12 - Unidade 9, Matemática Financeira slide 5/14 O dinheiro no tempo Valor acumulado após n peŕıodos: Cn = C0(1 + i) n. C0 é o valor atual do capital. Cn é o valor futuro do capital Para deslocar uma quantia para o futuro: multiplicar por 1 + i em cada peŕıodo. Para deslocar uma quantia para o passado: dividir por 1 + i em cada peŕıodo. PROFMAT - SBM MA12 - Unidade 9, Matemática Financeira slide 6/14 Comparando fluxos de caixa Um fluxo de caixa é uma sequência de pagamentos e recebimentos ao longo do tempo. Para comparar fluxos de caixa é essencial reduzi-los a uma mesma data, movimentando, se necessário, as quantias ao longo do tempo. PROFMAT - SBM MA12 - Unidade 9, Matemática Financeira slide 7/14 Exemplo Pedro tomou um empréstimo de 300 reais, a juros de 15% ao mês. Dois meses após, Pedro pagou 150 reais e, um mês após esse pagamento, Pedro liquidou seu débito. Qual o valor desse último pagamento? 1) Representar os pagamentos ao longo do tempo: 2) Escolher uma época para igualar os pagamentos: 0, por exemplo. 3) Igualar os pagamentos nesta data: 300 = 150 (1 + 0, 15)2 + P (1 + 0, 15)3 . O último pagamento foi P = R$ 283,76. PROFMAT - SBM MA12 - Unidade 9, Matemática Financeira slide 8/14 Exemplo Pedro tem duas opções de pagamento na compra de um televisor: i) três prestações mensais de R$ 160,00 cada; ii) sete prestações mensais de R$ 70,00 cada. Em ambos os casos, a primeira prestação é paga no ato da compra. Se o dinheiro vale 2% ao mês para Pedro, qual a melhor opção? PROFMAT - SBM MA12 - Unidade 9, Matemática Financeira slide 9/14 Solução Os esquemas de pagamento: Calculando os valores na época 2: a = 160(1 + 0, 02)2 + 160(1 + 0, 02)+ 160 = 489, 66 b = 70(1 + 0, 02)2 + 70(1 + 0, 02) + 70 + 70 1 + 0, 02 + 70 (1 + 0, 02)2 + 70 (1 + 0, 02)3 + 70 (1 + 0, 02)4 = 480, 77. Pedro deve preferir o pagamento em sete prestações. PROFMAT - SBM MA12 - Unidade 9, Matemática Financeira slide 10/14 Uma loja oferece duas opções de pagamento: i) à vista, com 30% de desconto. ii) em duas prestações mensais iguais, sem desconto, a primeira prestação sendo paga no ato da compra. Qual a taxa mensal dos juros embutidos nas vendas a prazo? Esquemas de pagamento: Igualando os valores na época 0: 70 = 50 + 50 1 + i . Dáı, i = 1, 5 = 150% PROFMAT - SBM MA12 - Unidade 9, Matemática Financeira slide 11/14 A Fórmula das Taxas Equivalentes Se a taxa de juros relativamente a um determinado peŕıodo de tempo é igual a i , a taxa de juros relativamente a n peŕıodos de tempo é I tal que 1 + I = (1 + i)n. Exemplo: A taxa anual de juros equivalente a 12% ao mês é I tal que 1 + I = (1 + 0, 12)12Dáı,I≈ 2, 90 = 290% ao ano. PROFMAT - SBM MA12 - Unidade 9, Matemática Financeira slide 12/14 Taxas equivalentes e taxas proporcionais Uma taxa mensal de 2% ao mês não resulta em uma taxa anual de 24% ao ano, e sim de 1, 0212 − 1 ≈ 1, 268 − 1 = 26, 8%. Há, no entanto, o (mau) hábito de se referir a esta taxa como sendo de ”24% ao ano, capitalizados mensalmente”. A taxa de 24% ao ano é a taxa proporcional, enquanto a de 26, 8% ao ano é a taxa efetiva. PROFMAT - SBM MA12 - Unidade 9, Matemática Financeira slide 13/14 Exemplo Um capital é a juros de 6% ao ano com capitalização mensal. Qual a taxa anual de juros à qual está investido o capital? A taxa de 6% ao ano é a taxa proporcional, que corresponde a uma taxa mensal de i = 612 = 0, 5% ao mês. A taxa efetiva anual é I tal que 1 + I = 1, 00512, o que fornece I = 0, 0617. Logo, a taxa efetiva anual é de 6, 17%. PROFMAT - SBM MA12 - Unidade 9, Matemática Financeira slide 14/14 MA12 - Unidade 10 Matemática Financeira - continuação Paulo Cezar Pinto Carvalho PROFMAT - SBM 31 de Março de 2013 Séries de pagamentos Uma série uniforme de pagamentos é uma sequência de pagamentos iguais e igualmente espaçados ao longo do tempo. Teorema: O valor de uma série uniforme de n pagamentos iguais a P, um tempo antes do primeiro pagamento, é, sendo i a taxa de juros, igual a A = P 1 − (1 + i)−n i . O valor da série na época 0 é A = P 1 + i + P (1 + i)2 + P (1 + i)3 + · · · + P (1 + i)n = P 1 + i 1 − ( 1 1+i )n 1 − 11+i = P 1 − (1 + i)−n i . PROFMAT - SBM MA12 - Unidade 10, Matemática Financeira - continuação slide 2/13 Exemplo Um bem, cujo preço à vista é R$ 120,00, é vendido em 6 prestações mensais iguais, a primeira paga no ato da compra. Se os juros são de 10% ao mês, determine o valor das prestações. Igualando os valores na época −1: 120 1 + 0, 1 = P 1 − (1 + 0, 1)−6 0, 1 P ≈ 25, 05. PROFMAT - SBM MA12 - Unidade 10, Matemática Financeira - continuação slide 3/13 Exemplo Helena tem duas alternativas para obter uma copiadora: a) Comprá-la por 150. Nesse caso, já que a vida econômica da copiadora é de 5 anos, Helena venderá a copiadora após 5 anos. O valor residual da copiadora após 5 anos é de 20. As despesas de manutenção são de responsabilidade de Helena e são de 5 por ano, nos dois primeiros anos, e de 8 por ano, nos anos seguintes. b) Alugá-la por 5 anos, com o locador se responsabilizando pelas despesas de manutenção. Se o dinheiro vale 7% ao ano, qual é o valor justo do aluguel? PROFMAT - SBM MA12 - Unidade 10, Matemática Financeira - continuação slide 4/13 Solução O fluxo de caixa da primeira alternativa: O da segunda alternativa: Igualando os valores na época 0: −150− 5 1, 07 − 5 1, 072 − 8 1, 073 − 8 1, 074 + 12 1, 075 = P 1 − 1, 07−5 0, 07 . Dáı, P = 39, 78. PROFMAT - SBM MA12 - Unidade 10, Matemática Financeira - continuação slide 5/13 Perpetuidades Teorema: O valor de uma perpetuidade de termos iguais a P, um tempo antes do primeiro pagamento, é, sendo i a taxa de juros, igual a P i . O valor da série perpétua é: A = lim n→∞ P 1 − (1 + i)−n i = P i . PROFMAT - SBM MA12 - Unidade 10, Matemática Financeira - continuação slide 6/13 Exemplo Se a taxa de juros é de 1% ao mês, quanto deve ser economizado mensalmente durante 20 anos para assegurar uma perpetuidade de R$ 1000,00? O esquema de pagamentos e recebimentos é: O valor economizado, na época 240, deve ser igual a 1000 0, 01 = 100.000. PROFMAT - SBM MA12 - Unidade 10, Matemática Financeira - continuação slide 7/13 Na data 0, o valor economizado é P 1 − (1, 01)−240 0, 01 Levando-se este valor para a época 240, obtém-se P 1 − (1, 01)−240 0, 01 · (1, 01)240 = P (1, 01) 240 − 1 0, 01 = 494, 63P Logo, devemos ter 494, 63P = 100.000 e o valor mensal a ser economizado deve ser igual a R$ 202,17. PROFMAT - SBM MA12 - Unidade 10, Matemática Financeira - continuação slide 8/13 Sistemas de amortização Ao se pagar em parcelas um débito, cada pagamento Pk tem dupla finalidade: uma parte (Jk) quita os juros devidos. o restante (Ak) amortiza parte da d́ıvida; Planilha de amortização k Pk Ak Jk Dk 0 − − − D0 . . . . . . . . . . . . . . . k − 1 Pk−1 Ak−1 Jk−1 Dk−1 k Pk Ak Jk Dk . . . . . . . . . . . . . . . Relações: Pk = Jk + Ak Jk = i · Dk−1 Dk = Dk−1 − Ak PROFMAT - SBM MA12 - Unidade 10, Matemática Financeira - continuação slide 9/13 Sistema de Amortização Constante (SAC) No sistema de amortização constante (SAC), a parcela de amortização Ak em cada pagamento é constante. Em consequência: Ak = D0 n , Dk = n − k n D0 , Jk = iDk−1, Pk = Ak + Jk . PROFMAT - SBM MA12 - Unidade 10, Matemática Financeira - continuação slide 10/13 Exemplo Uma d́ıvida de 100 é paga, com juros de 15% ao mês, em 5 meses, pelo SAC. Faça a planilha de amortização. Como as amortizações são iguais, cada amortização será de 15 da d́ıvida inicial. k Pk Ak Jk Dk 0 − − − 100 1 35 20 15 80 2 32 20 12 60 3 29 20 9 40 4 26 20 6 20 5 23 20 3 − PROFMAT - SBM MA12 - Unidade 10, Matemática Financeira - continuação slide 11/13 Sistema Francês de Amortização (Tabela Price) O sistema francês de amortização é caracterizado por pagamentos Pk iguais. Em consequência: Pk = D0 i 1 − (1 + i)−n , Dk = D0 1 − (1 + i)−(n−k) 1 − (1 + i)−n , Jk = iDk−1 Ak = Pk − Jk . PROFMAT - SBM MA12 - Unidade 10, Matemática Financeira - continuação slide 12/13 Exemplo Uma d́ıvida de 150 é paga, em 4 meses, pelo sistema francês, com juros de 8% ao mês. Calcule o valor da prestação e faça a planilha de amortização. O valor da prestação é P = D0 i 1 − (1 + n)−n = 150 0, 08 1 − 1, 08−4 = 45, 29. . A planilha de amortização é: k Pk Ak Jk Dk 0 − − − 150, 00 1 45, 29 33, 29 12, 00 116, 71 2 45, 29 35, 95 9, 34 80, 76 3 45, 29 38, 83 6, 46 41, 93 4 45, 29 41, 93 3, 35 0 PROFMAT - SBM MA12 - Unidade 10, Matemática Financeira - continuação slide 13/13 MA12 - Unidade 11 Combinatória Paulo Cezar Pinto Carvalho PROFMAT - SBM 29 de Abril de 2013 Prinćıpio Fundamental da Contagem Problemas de contagem são resolvidos explorando o significado das operações aritméticas de adição, subtração, multiplicação e divisão, com destaque para o papel da multiplicação. Prinćıpio Multiplicativo (ou Prinćıpio Fundamental da Contagem): Se há x modos de tomar uma decisão D1 e, tomada a decisão D1, há y modos de tomar a decisão D2, então o número de modos de tomar sucessivamente as decisões D1 e D2 é xy . PROFMAT - SBM MA12 - Unidade 11, Combinatória slide 2/8 Exemplo Uma bandeira é formada por 7 listras que devem ser coloridas usando apenas as cores verde, azul e cinza. Se cada listra deve ter apenas uma cor e não se pode usar cores iguais em listras adjacentes, de quantos modos se pode colorir a bandeira? Colorir a bandeira equivale a escolher a cor de cada listra. Há 3 modos de escolhera cor da primeira listra; A partir dáı, 2 modos de escolher a cor de cada uma das outras 6 listras. A resposta é 3 × 26 = 192. PROFMAT - SBM MA12 - Unidade 11, Combinatória slide 3/8 Exemplo Quantos são os números de três d́ıgitos distintos? Formar o número equivale a escolher cada um de seus d́ıgitos. O primeiro d́ıgito pode ser escolhido de 9 modos, pois ele não pode ser igual a 0. O segundo d́ıgito pode ser escolhido de 9 modos, pois não pode ser igual ao primeiro d́ıgito. O terceiro d́ıgito pode ser escolhido de 8 modos, pois não pode ser igual nem ao primeiro nem ao segundo d́ıgito. A resposta é 9 × 9 × 8 = 648. PROFMAT - SBM MA12 - Unidade 11, Combinatória slide 4/8 A estratégia 1) Postura. Colocar-se no papel da pessoa que deve fazer a ação solicitada pelo problema e ver que decisões devemos tomar. 2) Divisão. Sempre que posśıvel, dividir as decisões a serem tomadas em decisões mais simples. 3) Não adiar dificuldades. Se uma das decisões a serem tomadas for mais restrita que as demais, essa é a decisão que deve ser tomada em primeiro lugar. PROFMAT - SBM MA12 - Unidade 11, Combinatória slide 5/8 Violando a terceira regra Quantos são os números de três d́ıgitos distintos? A escolha mais restrita é a do d́ıgito das centenas, porque ele não pode ser 0. O que ocorre se ignoramos este fato e decidimos começar pelo d́ıgito das unidades? O d́ıgito das unidades pode ser escolhido de 10 modos. O das dezenas pode ser escolhido de 9 modos ( não pode ser igual ao das unidades). O das centenas pode ser escolhido de ... depende! (podem ser 7 ou 8 possibilidades, dependendo do 0 ter ou não ter sido usado nas dezenas ou unidades). PROFMAT - SBM MA12 - Unidade 11, Combinatória slide 6/8 Nem sempre basta usar o Prinćıpio Fundamental Quantos são os números pares de três d́ıgitos distintos? Começando escolhendo d́ıgito das unidades, que é o mais restrito: há 5 possibilidades (0, 2, 4, 6 ou 8). A seguir, escolhemos o d́ıgito das centenas. O número de possibilidades para esta escolha ... depende. Se 0 for o d́ıgito das unidades, há 9 possibilidades para o das centenas (só não pode ser 0). Se 0 não for o d́ıgito das unidades, há 8 possibilidades para o das centenas (não pode ser 0 nem o algarismo das unidades). Solução: Dividir em casos, contados separadamente, e somar os resultados. PROFMAT - SBM MA12 - Unidade 11, Combinatória slide 7/8 Dividindo em casos e somando Quantos são os números pares de três d́ıgitos distintos? Para os números que terminam em 0 Para o d́ıgito das unidades, há apenas 1 possibilidade. Para o das centenas, há 9 possibilidades (só não pode ser 0). Para o das dezenas, há 8 possibilidades (não pode ser os dois já usados). Logo, há 1 × 9 × 8 = 72 números terminados em 0. Para os números que não terminam em 0 Para o d́ıgito das unidades há 4 possibilidades. Para o das centenas, há 8 possibilidades (não pode ser 0 nem o das unidades). Para o das dezenas, há 8 possibilidades (não pode ser os dois já usados). Logo, há 4 × 8 × 8 = 256 números terminados em 0. Portanto, há 72 + 256 = 328 números pares de três algarismos distintos. PROFMAT - SBM MA12 - Unidade 11, Combinatória slide 8/8 MA12 - Unidade 12 Permutações e Combinações Paulo Cezar Pinto Carvalho PROFMAT - SBM 28 de Abril de 2013 Permutações Simples De quantos modos podemos ordenar em fila n objetos distintos? A escolha do objeto que ocupará o primeiro lugar pode ser feita de n modos; A escolha do objeto que ocupará o segundo lugar pode ser feita de n − 1 modos; . . . A escolha do objeto que ocupará o último lugar pode ser feita de 1 modo. O número total de possibilidades (cada uma das quais é chamada de uma permutação simples dos n objetos) é Pn = n(n − 1)(n − 2) · · · 1 = n!. PROFMAT - SBM MA12 - Unidade 12, Permutações e Combinações slide 2/13 Exemplo Quantos são os anagramas da palavra “CALOR”? Quantos começam com consoantes? Cada anagrama corresponde a uma permutação dessas 5 letras. O número de anagramas é P5 = 5! = 120. Para formar um anagrama começado por consoante: A consoante pode ser escolhida de 3 modos; As demais letras podem ser colocadas em qualquer ordem; logo, há P4 = 4! = 24 possibilidades de ordenação. Logo, há 3× 24 = 72 anagramas começados por consoante. PROFMAT - SBM MA12 - Unidade 12, Permutações e Combinações slide 3/13 Exemplo De quantos modos podemos arrumar em fila 5 livros diferentes de Matemática, 3 livros diferentes de Estat́ıstica e 2 livros diferentes de F́ısica, de modo que livros de uma mesma matéria permaneçam juntos? Podemos escolher a ordem das matérias de 3! modos. Feito isso, há 5! modos de colocar os livros de Matemática nos lugares que lhe foram destinados, 3! modos para os de Estat́ıstica e 2! modos para os de F́ısica. O número total de possibilidades é 3!5!3!2! = 6× 120× 6× 2 = 8 640 PROFMAT - SBM MA12 - Unidade 12, Permutações e Combinações slide 4/13 Permutações de elementos nem todos distintos Quantos são os anagramas da palavra “BOTAFOGO”? Se as letras fossem diferentes a resposta seria 8!. Como as três letras O são iguais, quando as trocamos entre si obtemos o mesmo anagrama e não um anagrama distinto. Isso faz com que na nossa contagem de 8! tenhamos contado o mesmo anagrama 3! vezes. O número de anagramas é 8! 3! = 6 720. PROFMAT - SBM MA12 - Unidade 12, Permutações e Combinações slide 5/13 Generalizando O número de permutações de n objetos, dos quais α são iguais a A, β são iguais a B, γ são iguais a C , etc, é Pα,β,γ,...n = n! α!β!γ! . . . . PROFMAT - SBM MA12 - Unidade 12, Permutações e Combinações slide 6/13 Combinações Simples De quantos modos podemos selecionar p objetos distintos entre n objetos distintos dados? Equivalentemente, quantos são os subconjuntos com p elementos de um conjunto com n elementos? Observação: cada seleção de p objetos (ou seja, cada subconjunto de p elementos) é chamada de uma combinação simples de classe p dos n objetos. PROFMAT - SBM MA12 - Unidade 12, Permutações e Combinações slide 7/13 Combinações Simples De quantos modos podemos selecionar p objetos distintos entre n objetos distintos dados? Equivalentemente, quantos são os subconjuntos com p elementos de um conjunto com n elementos? Começamos escolhendo, em ordem, p elementos, o que pode ser feito de n.(n − 1) . . . (n − p + 1) modos. Deste modo, cada subconjunto com p elementos é contado p! vezes, já que ele aparece em cada ordem posśıvel. O número de combinações simples de classe p de n objetos é: Cpn = n.(n − 1) . . . (n − p + 1) p! = n! p!(n − p)! . PROFMAT - SBM MA12 - Unidade 12, Permutações e Combinações slide 8/13 Exemplo Com 5 homens e 4 mulheres, quantas comissões de 5 pessoas, com exatamente 3 homens, podem ser formadas? Para formar a comissão devemos escolher 3 dos homens e 2 das mulheres. Logo, há C 35 · C 24 = 10× 6 = 60 comissões. PROFMAT - SBM MA12 - Unidade 12, Permutações e Combinações slide 9/13 Exemplo Com 5 homens e 4 mulheres, quantas comissões de 5 pessoas, com pelo menos 3 homens, podem ser formadas? Há comissões com: 3 homens e 2 mulheres, 4 homens e 1 mulher, 5 homens. A resposta é C 35 · C 24 + C 45 · C 14 + C 55 = 10× 6 + 5× 4 + 1 = 81. Um erro comum: Começo escolhendo 3 homens, para garantir pelo menos três homens (C 35 modos). A seguir, escolho mais 2 pessoas (C 26 modos). Logo, há C 35 .C 2 6 = 10.15 = 150 comissões (!). PROFMAT - SBM MA12 - Unidade 12, Permutações e Combinações slide 10/13 Permutações Circulares De quantos modos 5 crianças podem formar uma roda? A resposta não é 5! = 120 rodas, porque as rodas ABCDE e EACBD, por exemplo, são na verdade a mesma roda. Como cada roda pode aparecer em 5 posições, a resposta é 120/5 = 24. De modo geral, o número de permutações circulares de n elementos é n! n = (n − 1)!. PROFMAT - SBMMA12 - Unidade 12, Permutações e Combinações slide 11/13 Combinações completas (ou com repetição) Quantas são as soluções inteiras e não-negativas da equação x1 + x2 + · · ·+ xn = p? Cada solução da equação coresponde a uma forma de escolher p elementos dentre 1, 2, . . . n, mas permitindo repetições. O número de soluções é representado por CRpn . Cada solução da equação pode ser representada por uma fila de p sinais + e n − 1 sinais |, que separam as incógnitas. Reciprocamente, cada fila desta forma corresponde a uma solução. Por exemplo: + + +|+ ||+ corresponde à solução (3,1,0,1) da equação x1 + x2 + x3 + x4 = 5. Para contar a quantidade de tais filas, basta escolher p dentre os n + p − 1 lugares para colocar os sinais +. Logo, CRpn = C p n+p−1. PROFMAT - SBM MA12 - Unidade 12, Permutações e Combinações slide 12/13 Exemplo De quantos modos podemos comprar 3 sorvetes em uma sorveteria que os oferece em 6 sabores distintos? Chamando de xk o número de sorvetes do k-ésimo sabor que vamos comprar, devemos determinar valores inteiros e não-negativos para xk , k = 1, 2, 3, 4, 5, 6, tais que x1 + x2 + · · ·+ x6 = 3. O número de possibilidades é CR36 = C 3 8 = 56 modos. PROFMAT - SBM MA12 - Unidade 12, Permutações e Combinações slide 13/13 MA12 - Unidade 13 Triângulo de Pascal e Binômio de Newton Paulo Cezar Pinto Carvalho PROFMAT - SBM 4 de Maio de 2013 Triângulo de Tartaglia-Pascal C 00 C 01 C 1 1 C 02 C 1 2 C 2 2 C 03 C 1 3 C 2 3 C 3 3 C 04 C 1 4 C 2 4 C 3 4 C 4 4 C 05 C 1 5 C 2 5 C 3 5 C 4 5 C 5 5 . . . . . . . . . . . . . . . . . . . . . 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 . . . . . . . . . . . . . . . . . . . . . PROFMAT - SBM MA12 - Unidade 13, Triângulo de Pascal e Binômio de Newton slide 2/3 Triângulo de Tartaglia-Pascal Alternativamente: C00 C01 C 1 1 C02 C 1 2 C 2 2 C03 C 1 3 C 2 3 C 2 3 C04 C 1 4 C 2 4 C 3 4 C 4 4 C05 C 1 5 C 2 5 C 3 5 C 4 5 C 5 5 . . . . . . . . . . . . . . . . . . . . . 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 . . . . . . . . . . . . . . . . . . . . . PROFMAT - SBM MA12 - Unidade 13, Triângulo de Pascal e Binômio de Newton slide 3/3 Relação de Stifel Cpn + C p+1 n = C p+1 n+1 . Prova: Contar de dois modos diferentes os subconjuntos com p + 1 elementos de {1, 2, . . . , n, n + 1}: diretamente; contando separadamente os subconjuntos incluindo ou excluindo n + 1. PROFMAT - SBM MA12 - Unidade 13, Triângulo de Pascal e Binômio de Newton slide 4/3 Teorema das linhas C 0n + C 1 n + C 2 n + . . . + C n n = 2 n Prova: Contar de dois modos diferentes os subconjuntos de {1, 2, . . . , n}: diretamente; contando separadamente os subconjuntos de cada cardinalidade. PROFMAT - SBM MA12 - Unidade 13, Triângulo de Pascal e Binômio de Newton slide 5/3 Combinações complementares Cpn = C n−p n (termos de uma mesma linha equidistantes dos extremos são iguais). Prova: escolher um subconjunto com p elementos equivale a escolher seu complementar. PROFMAT - SBM MA12 - Unidade 13, Triângulo de Pascal e Binômio de Newton slide 6/3 Binômio de Newton (x + a)n = n∑ p=0 Cpn a pxn−p = C 0n a 0xn + C 1n a 1xn−1 + C 2n a 2xn−2 + · · ·+ Cnn anx0. Prova: Considere o produto (x + a)n = (x + a)(x + a) . . . (x + a) Para formar um termo igual a apxn−p, é preciso tomar p fatores iguais a a e n − p fatores iguais a x , o que pode ser feito de C pn modos. PROFMAT - SBM MA12 - Unidade 13, Triângulo de Pascal e Binômio de Newton slide 7/3 Exemplo Determine o coeficiente de x3 no desenvolvimento de( x4 − 1 x )7 . O termo genérico do desenvolvimento é Cp7 ( −1 x )p (x4)7−p = Cp7 (−1) px28−5p. O termo em x3 é obtido quando 28− 5p = 3, ou seja, se p = 5. O termo procurado é C 57 (−1)5x3 = −21x3 . O coeficiente é −21. PROFMAT - SBM MA12 - Unidade 13, Triângulo de Pascal e Binômio de Newton slide 8/3 Exemplo Mostre que C 0n − C 1n + C 2n + . . . + (−1)nCnn = 0 (ou seja, a soma das combinações de taxa par de n elementos é igual à soma das combinações de taxa ı́mpar). Basta formar o desenvolvimento de (1− 1)n = ∑n p=0 C p n (−1)p1n−p. Note que, ao formar o desenvolvimento de (1 + 1)n, redescobrimos o Teorema das Linhas: C 0n + C 1 n + C 2 n + . . . + C n n = 2 n PROFMAT - SBM MA12 - Unidade 13, Triângulo de Pascal e Binômio de Newton slide 9/3 Exemplo Determine o termo máximo do desenvolvimento de( 3 4 + 1 4 )30 . Se uma pessoa responde ao acaso um teste com 30 questões com 4 alternativas cada, qual é o número mais provável de questões certas? A probabilidade de acertar p questões é igual ao termo de ordem p do desenvolvimento: tp = C p 30 ( 1 4 )p(3 4 )(30−p) = Cp30 330−p 430 . Vamos descobrir para que valores de p os termos crescem. Para isso, devemos estudar o comportamento de tp − tp−1. PROFMAT - SBM MA12 - Unidade 13, Triângulo de Pascal e Binômio de Newton slide 10/3 Continuação tp − tp−1 = Cp30 330−p 430 − Cp−130 331−p 430 = 30!330−p p!(30− p)!430 − 30!3 31−p (p − 1)!(31− p)!430 = 30!330−p p!(31− p)!430 ((31− p)− 3p) = 30!330−p p!(31− p)!430 (31− 4p) tp > tp−1 ⇔ 31− 4p > 0⇔ p < 314 = 7, 75⇔ p ≤ 7 O maior termo é t7 = C 7 30 323 430 (ou seja, o número mais provável de respostas corretas é 7). PROFMAT - SBM MA12 - Unidade 13, Triângulo de Pascal e Binômio de Newton slide 11/3 MA12 - Unidade 17 Probabilidade Paulo Cezar Pinto Carvalho PROFMAT - SBM 17 de Maio de 2013 Teoria da Probabilidade Teoria da Probabilidade: modelo matemático para incerteza. Objeto de estudo: experimentos aleatórios. Componentes de um modelo probabiĺıstico: Espaço amostral (S): conjunto de todos os resultados posśıveis de um experimento aleatório. Eventos : os subconjuntos do espaço amostral S . Função de Probabilidade: uma função que associa a cada evento A sua probabilidade P(A), satisfazendo: P(A) ≥ 0, para todo evento A. P(S) = 1 (o evento certo). P(A ∪ B) = P(A) + P(B), se A e B são disjuntos (ou mutuamente excludentes). Para que um modelo probabiĺıstico seja útil, P(A) deve representar o grau de confiança em que o evento A ocorra. PROFMAT - SBM MA12 - Unidade 17, Probabilidade slide 2/10 Propriedades da Função de Probabilidade i) P(A) = 1− P(A). ii) P(∅) = 0. iii) 0 ≤ P(A) ≤ 1. iv) P(A− B) = P(A)− P(A ∩ B). v) P(A ∪ B) = P(A) + P(B)− P(A ∩ B). vi) Se A ⊂ B então P(A) 6 P(B). PROFMAT - SBM MA12 - Unidade 17, Probabilidade slide 3/10 Exemplo Qual é o modelo probabiĺıstico adequado para o lançamento de um dado? Qual é a probabilidade de que saia um resultado par? O espaço amostral é S = {1, 2, 3, 4, 5, 6}. Se o dado é um cubo geometricamente perfeito e feito com material homogêneo (um dado equilibrado ou honesto), não há razão para acreditar que uma face saia mais frequentemente que qualquer outra. O modelo razoável é o equiprovável, que atribui probabilidades iguais aos eventos correspondentes à ocorrência de cada face (neste caso, iguais a 16). O evento ”sair resultado par”corresponde ao subconjunto A = {2, 4, 6} de S . Sua probabilidade é P(A) = P({2}) + P({4}) + P({6}) = 16 + 1 6 + 1 6 = 1 2 . PROFMAT - SBM MA12 - Unidade 17, Probabilidade slide 4/10 Modelos Equiprováveis Modelo equiprovável: atribui probabilidade 1n a cada evento unitário de um espaço amostral S = {a1, a2, . . . , an}. Em consequência, a probabilidade de um evento A = {a1, a2, . . . , ap} é P(A) = P({a1}) + . . . + P({ap}) = p · 1n = p n . Portanto: P(A) = n(A) n(S) = Número de casos favoráveis Número de casos posśıveis (nos problemas mais interessantes, técnicas de Análise Combinatória são usadas para calcular o numerador e o denominador). Atenção: o uso de modelos equiprováveis só se justifica quando algum tipo de simetria permite concluir que os resultados posśıveis têm a mesma chance de ocorrer. dados, moedas, cartas, bolas iguais em urnas, etc. PROFMAT - SBM MA12 - Unidade 17, Probabilidadeslide 5/10 Exemplo Duas bolas são retiradas seguidamente e sem reposição de uma urna com 3 bolas brancas e 5 pretas, todas idênticas, a menos da cor. Qual é a probabilidade de que a primeira seja branca e a segunda preta? Há quatro possibilidades para a cor das bolas: BB, BP, PB e PP. Dos quatro casos posśıveis, apenas um é favorável. Logo, a probabilidade é 14 . A solução acima está ERRADA! Não há qualquer razão para admitirmos, por exemplo, que a probabilidade de tirar duas bolas brancas seja a mesma que a de tirar duas bolas pretas, já que há mais bolas pretas do que brancas na urna. PROFMAT - SBM MA12 - Unidade 17, Probabilidade slide 6/10 Exemplo Duas bolas são retiradas seguidamente e sem reposição de uma urna com 3 bolas brancas e 5 pretas, todas idênticas, a menos da cor. Qual é a probabilidade de que a primeira seja branca e a segunda preta? O espaço amostral adequado é o que considera que há oito bolas b1, . . . , b8 na urna e considera todos os posśıveis pares (bi , bj) de bolas distintas retiradas. Como todas as bolas são idênticas, todos os pares posśıveis têm a mesma chance de ocorrer (um modelo equiprovável!). Número de casos posśıveis: A primeira bola pode ser qualquer uma das 8. A segunda pode ser qualquer uma das outras 7. O número de casos posśıveis é 8× 7 = 56. Número de casos favoráveis: A primeira bola pode ser qualquer uma das 3 bolas brancas. A segunda pode ser qualquer uma das 5 bolas pretas. O número de casos favoráveis é 3× 5 = 15. A probabilidade é 1556 . PROFMAT - SBM MA12 - Unidade 17, Probabilidade slide 7/10 Exemplo Em um grupo de r pessoas, qual é a probabilidade de haver pelo menos duas pessoas que façam aniversário no mesmo dia? O número de casos posśıveis para os aniversários das r pessoas é 365r . O número de casos favoráveis a que todas aniversariem em dias diferentes é 365× 364× · · · × (366− r). A probabilidade de não haver pelo menos duas pessoas que façam aniversário no mesmo dia é 365× 364× · · · × (366− r) 365r A probabilidade de haver pelo menos duas pessoas que tenham o mesmo dia de aniversário é 1− 365× 364× · · · × (366− r) 365r . PROFMAT - SBM MA12 - Unidade 17, Probabilidade slide 8/10 Continuação Alguns valores da probabilidade de haver coincidência de aniversários: r Probabilidade 5 0, 03 10 0, 12 15 0, 25 20 0, 41 23 0, 51 25 0, 57 30 0, 71 40 0, 89 45 0, 94 50 0, 97 A partir de 23 pessoas, é mais provável que haja coincidência de aniversários do que não haja! PROFMAT - SBM MA12 - Unidade 17, Probabilidade slide 9/10 E se um modelo equiprovável não for adequado? Um dado tem a forma de um bloco retangular com as dimensões da figura. Qual é a probabilidade de sair a face 1? Como não há simetria perfeita, não é correto usar um modelo equiprovável. A simetria restante na figura permite escrever: P({1}) = P({6}) = p P({2}) = P({3}) = P({4}) = P({5}) = 1−2p4 O valor de p pode ser estimado a partir das frequências de ocorrência das diversas faces (é o papel da Estat́ıstica). PROFMAT - SBM MA12 - Unidade 17, Probabilidade slide 10/10 MA12 - Unidade 18 Probabilidade Condicional Paulo Cezar Pinto Carvalho PROFMAT - SBM 17 de Maio de 2013 Exemplo Um dado honesto é lançado duas vezes. a) Qual é a probabilidade de sair 1 no 1o lançamento? b) Qual é a probabilidade que que tenha sáıdo 1 no 1o lançamento, sabendo que a soma dos resultados foi 5? a) O espaço amostral é S = {(1, 1), . . . , (6, 6)}; há 36 casos posśıveis. O evento “1 no 1o lançamento” é A = {(1, 1), . . . , (1, 6)}; há 6 casos favoráveis. A probabilidade de sair 1 no 1o lançamento é 636 = 1 6 . b) Como a soma foi 5, podemos reduzir o espaço amostral a B = “a soma é 5” = {(1, 4), (2, 3), (3, 2), (4, 1)}; há 4 casos posśıveis, todos igualmente prováveis. São favoráveis os casos que também estão em A, ou seja, os elementos de A ∩ B = {(1, 4)}; portanto, há apenas 1 caso favorável. Logo, a probabilidade desejada é P(A|B) = n(A∩B)n(B) = 1 4 . Note que P(A|B) = n(A∩B)/n(S)n(B)/n(S) = P(A∩B) P(B) PROFMAT - SBM MA12 - Unidade 18, Probabilidade Condicional slide 2/14 Probabilidade Condicional Dados dois eventos A e B, com P(B) 6= 0, a probabilidade condicional de A na certeza de B (ou simplesmente, a probabilidade de A dado B) é o número P(A|B) = P(A ∩ B) P(B) . A ideia: redistribuir proporcionalmente os valores de probabilidade, de modo a atribuir a B probabilidade igual a 1. PROFMAT - SBM MA12 - Unidade 18, Probabilidade Condicional slide 3/14 Exemplo A tabela abaixo dá a distribuição dos alunos de uma escola, por sexo e por carreira pretendida. Feminino Masculino Total Cient́ıfica 12% 33% 45% Humańıstica 40% 15% 55% Total 52% 48% 100% Um aluno da escola é escolhido ao acaso. Sejam F , M, C e H os eventos em que o aluno selecionado é do sexo feminino, do sexo masculino, pretende carreira cient́ıfica e pretende carreira humańıstica, respectivamente. Calcule P(F |C ) e P(H|M). P(F |C ) = P(F∩C)P(C) = 0,12 0,45 = 4 15 ≈ 0, 27. P(H|M) = P(H∩M)P(M) = 0,15 0,48 = 5 16 ≈ 0, 31. PROFMAT - SBM MA12 - Unidade 18, Probabilidade Condicional slide 4/14 Independência Da definição de probabilidade condicional: P(A ∩ B) = P(B)P(A|B) = P(A)P(B|A). Esta expressão é útil para calcular a probabilidade da interseção de dois eventos, principalmente em experimentos realizados em etapas. Quando P(A ∩ B) = P(A)P(B), os eventos A e B são independentes. Equivale a dizer que: P(A|B) = P(A) e P(B|A) = P(B), (desde que P(A) 6= 0 e P(B) 6= 0). PROFMAT - SBM MA12 - Unidade 18, Probabilidade Condicional slide 5/14 Exemplo Uma moeda tem probabilidade 0,4 de dar cara. Se ela for lançada 5 vezes, qual é a probabilidade de que saiam exatamente duas caras? Os eventos “sair cara no i-ésimo lançamento” (i = 1, . . . , 5) são independentes. A probabilidade de que saia uma dada sequência com 2 caras(c) e 3 coroas(k) (por exemplo, cckkk) é igual ao produto das probabilidades dos eventos correspondentes a cada lançamento; logo, é igual a 0, 42 × 0, 63. Como há C 25 sequências deste tipo, a probabilidade de observarmos exatamente duas caras é C 25 × 0, 42 × 0, 63 = 0, 3456. A probabilidade de se observarem k sucessos em n realizações independentes de um experimento com probabilidade p de sucesso é C kn p k(1− p)n−k (modelo binomial). PROFMAT - SBM MA12 - Unidade 18, Probabilidade Condicional slide 6/14 Exemplo Uma urna contém 4 bolas brancas e 6 bolas pretas. Sacam-se, sucessivamente e sem reposição, duas bolas dessa urna. a) Qual é a probabilidade de ambas serem brancas? b) Qual é a probabilidade de que a segunda bola seja branca? c) Qual é a probabilidade de que a primeira bola seja branca, sabendo que a segunda é branca? a) Sejam B1 = {a primeira bola é branca} e B2 = {a segunda bola é branca}. A probabilidade pedida é: P(B1 ∩ B2) = P(B1) · P(B2|B1) = 410 · 3 9 = 2 15 . PROFMAT - SBM MA12 - Unidade 18, Probabilidade Condicional slide 7/14 Exemplo Uma urna contém 4 bolas brancas e 6 bolas pretas. Sacam-se, sucessivamente e sem reposição, duas bolas dessa urna. a) Qual é a probabilidade de ambas serem brancas? b) Qual é a probabilidade de que a segunda bola seja branca? c) Qual é a probabilidade de que a primeira bola seja branca, sabendo que a segunda é branca? b) Há duas possiblidades: A primeira é branca (B1) e a segunda é branca (B2) ou A primeira é preta (P1) e a segunda é branca (B2) Logo: P(B2) = P((B1 ∩ B2) ∪ (P1 ∩ B2)) = P(B1 ∩ B2) + P(P1 ∩ B2) = P(B1).P(B2|B1) + P(P1).P(B2|P1) = 4 10 . 3 9 + 6 10 . 4 9 = 36 90 = 2 5 . PROFMAT - SBM MA12 - Unidade 18, Probabilidade Condicional slide 8/14 Exemplo Uma urna contém 4 bolas brancas e 6 bolas pretas. Sacam-se, sucessivamente e sem reposição, duas bolas dessa urna. a) Qual é a probabilidade de ambas serem brancas? b) Qual é a probabilidade de que a segunda bola seja branca? c) Qual é a probabilidade
Compartilhar