A indução matemática é uma técnica de prova que mostra que uma proposição P(n) é verdadeira para todo n em um domínio (geralmente os números inteiros positivos). Ela exige normalmente dois passos:
Ilustrando com a subida de uma escada infinita: se você verifica que consegue alcançar o primeiro degrau (passo base) e que, estando em qualquer degrau, você consegue chegar ao degrau seguinte, então pode concluir que você consegue alcançar todos os degraus.
Observação: há também o que chamamos de Indução forte (ou indução com hipótese forte), na qual, para provar P(n+1), supomos que P(i) é verdadeira para todos i entre a base e n, não apenas para i = n. Esse tipo é especialmente útil quando o passo depende de vários passos anteriores.
Exemplo A – Duplicação de uma geração: considere uma população que duplica a cada geração. Se a geração 1 tem 2 indivíduos, então a geração n tem 2^n indivíduos.
Exemplo B – Propriedade algébrica com números inteiros positivos: considere a propriedade P(n): “n^2 ≥ n para n ≥ 1”.
Exemplo 1 – 2^n − 1 ser múltiplo de 3: prova por indução de que 2^n − 1 é múltiplo de 3 para n adequado.
Exemplo 2 – Desenrolar uma moeda de 3 e 5 centavos: para quantias ≥ 8 centavos, qualquer valor pode ser obtido como uma combinação de 3 e 5 centravos. Em indução forte, verifica-se as bases 8, 9 e 10, e usa-se o passo: se n ≥ 11, então n − 3 ≥ 8, logo a propriedade se mantém ao adicionar 3 centavos.
Exemplos adicionais mencionados incluem demonstrações com 2N > N (para N ≥ 1), bem como outras variações que aparecem na seção 2 do material base.
Resposta correta: C) Provar a base para um n inicial e que, se P(n) vale, então P(n+1) também vale.
Explicação: No Primeiro Princípio (indução simples), mostramos que o enunciado é verdadeiro para um valor base (geralmente n0) e que, assumindo que vale para n, ele vale para n+1. Assim, a propriedade é verdadeira para todos os n no domínio.
Resposta correta: B) Indução simples assume P(n) -> P(n+1); Indução forte assume P(i) vale para todos i ≤ k para provar P(k+1).
Resposta correta: C) n = 2
Explicação: para demonstrar que 2^n − 1 é múltiplo de 3, a base útil indicada no texto é n = 2, já que 2^2 − 1 = 3, múltiplo de 3. Em indução, a base deve assegurar o início da cadeia de verdades.
Resposta correta: C) A base precisa cobrir 8, 9 e 10; para n ≥ 11, subtrair 3 e reduzir para 8–10, mantendo a propriedade.
Explicação: com indução forte, ao ter bases para 8, 9 e 10, para qualquer n ≥ 11 é possível subtrair 3 e retornar a um caso já confirmado (8, 9 ou 10), garantindo que a decomposição com moedas de 3 e 5 centavos exista.
Olá, a Lunes e a Lunes do curso de Fundamentos Matemáticos para a convitação.
Nesta videoaula, eu vou estar falando de In do Sal Matemática.
Vou estar apresentando o primeiro princípio do In do Sal, e o segundo princípio do In do Sal Matemática.
Eu gosto de usar esse exemplo de subir uma escada infinita.
Suponha que eu tenho que verificar a propriedade de subir um degrau dentro desse domínio e de escadas infinita.
Então, eu verifico, bom, eu consigo alcançar o primeiro degrau, legal, consigo.
Então, eu posso supor que seja capaz de chegar a um degrau com qualquer.
Mas se eu consigo chegar a um degrau com qualquer, então, será que eu consigo passar por próximo.
Então, eu vou lá e verifico se eu consigo passar por próximo degrau.
Sim, opa, então, nesta escada infinita, eu consigo de um degrau puro para o outro e repercorrendo toda a escada.
Basicamente, essa ideia do princípio do In do Sal, você parte de um passo básico e verifico um passo intuitivo que comprova a capacidade de que você tenha de percorrer, de manter aquela propriedade evalida ainda aqui dentro de uma coleção de valores infinitos.
Bom, pelo primeiro princípio da In do Sal, então, eu tenho que verificar a propriedade evalida para um enbó 1 e para todo o carro, no domínio de inteiro dispositivo, você propriedade for valida para cá, então, eu verifico que ela valida para o seguinte, caro mais 1.
Nesse caso, comprovando isso, eu posso dizer que ela é verdadeira para todo o N nesse domínio de inteiro dispositivo.
Vamos considerar aqui uma propriedade de que é a quantidade de indivíduos duplica de uma geração para outra.
Mas se isso está acontecendo, eu posso assumir que eu vou ter dois descendentes, depois 4, 8, certo? E que essa relação de descendência, então, na geração N, me leva a acredar que eu vou ter dois elevados à N indivíduos, mas como que eu provo isso sabendo apenas da propriedade de que duplica de uma geração para outra? Bom, nós teremos, então, nós estamos assuindo que vamos ter dois elevados à N descendentes como proposição, e como hipótese de que há uma duplicação de uma geração para outra.
Então, eu posso considerar então a hipótese de que duplica de uma geração para outra é esta tese de dois elevados à N indivíduos.
E aí tem, como passo base, a verificação de que para a N igual a 1 eu vou ter uma duplicação de descendentes.
Perfeito, foi o que a gente viu naquele gravo.
Naquela ávela, agora eu sou verdadeiro para todo o K, e aí eu vou tentar provar para K mais 1.
Como? Então para N igual a K, eu assumo que aquela relação matemática é ver que eu estou supondo é ver a dada.
Ou seja, que na geração K eu vou ter dois elevados a K, novos descendentes.
Vamos agora provar para N igual a K mais 1, só que para provar para N igual a K mais 1, a única certeza que eu tenho é a hipótese de indução, e a propriedade de que duplica.
Eu sei que na geração K mais 1 eu vou ter duas vezes o que eu tinha na geração anterior.
Só que na geração anterior, por hipótese de indução, eu estou assumindo que eu tenho a 2 elevado a K descendentes.
No óbvio, eu vou ter 2 elevado a K mais 1 na geração K mais 1, o que prova a relação que eu estava estabelecendo de na geração K mais 1, tem a 2 elevado a K mais 1 descendentes.
Agora, um outro contexto de demonstração.
Vamos supor essa matória aqui, certo? E eu quero provar, então, considerando domínios inteiros positivos, que para N igual a 1, ou seja, se eu tenho 1 termo no seu matório, essa forma vai ser válida.
Bom, para um termo no seu matório, do lado esquerdo, eu vou ter 1 para a formula do lado direito de bater.
Então, eu teria que ter 1 quadrado, que é a quantidade de elementos que eu tenho aqui.
O que bate? Temos a igualdade verificada.
Agora, vamos supor para N igual a K.
Nesse caso, eu considero que essa relação é válida para N igual a K, e vou provar para N igual a K mais 1.
Isso significa que eu acredito que até o caísmo elemento, quando eu acrescentar o K mais 1, dessa forma, eu vou ter a relação do lado direito K mais 1 quadrado.
Bom, eu vou ter igual a K mais 1 quadrado.
Bom, nesse caso, então, novamente, eu vou assumir a mi hipótese de indução, ou seja, eu sei que até o termo K mais 1, até o caísmo termo, essa relação se resume a calco cadrada.
Então, eu posso pegar esse termo que substituí por calco cadrão.
Nessa forma, eu vou fazer conta com esse termo aqui para verificar a igualdade.
Esse termo aqui, eu posso expandir, chegando nessa expressão, que se resume a calco cadrado, nós 2k mais 1, que nada mais é do que K mais 1 quadrado.
Então, dessa forma, o meu lado esquerdo é igual ao lado direito, e a relação é válida para K mais 1.
Logo, vai ser válida para N.
Outra, outro tipo de demonstração.
Suponho que eu tenho a 2N maior que N.
Por isso, nesse caso, para N igual 1, eu vou fazer a multiplicação 2 vezes 1, maior que 1.
Isso, de fato, se verifica 2, a maior que 1.
Asono válida para N igual a K.
Então, eu tenho que 2k é maior que K por hipótese de indução.
Agora, para provar para N igual a K mais 1, o que eu faço? Eu quero provar que 2 vezes K mais 1 é maior que K mais 1.
Bom, 2 vezes K mais 1 é igual a 2k mais 2.
Que hipótese de indução 2k é maior que K? 2k é maior que K.
Então, eu tenho uma igualdade aqui quebra para o mais desigualdade, porque 2k é maior que K mantém o 2.
Só que K mais 2 é maior que K mais 1, porque 2 é maior que 1.
Só o fato.
Então, eu tenho que 2 vezes K mais 1 é maior que K mais 1.
Provei para K mais 1 a proposição estaválida por indução.
Agora, eu quero provar para inteiro os positivos que 2²n-1 é divisível por 3.
Nós limos que para provar que 1²-1 é divisível por 3, mas na coisa que a gente está provando é um múltiplo de 3.
Então, vamos supor que seja igual a 3a, onde é a 1 inteiro positivo.
Nesse caso, para N igual a 1, eu vou verificar que eu tenho 2², que é 4 menos 1 3.
3 é divisível por 3.
Perfeito.
Lá, suba, é basico verificado.
Agora, suba, para N igual a K.
Nesse caso, eu vou considerar que essa relação se estabelece, que 2²-1 é um múltiplo de 3.
Tranquilo.
Agora, o meu trabalho é provar para K mais 1.
Para fazer essa demonstração, eu vou começar, expone, reescrevendo essa expressão para K mais 1, que é 2²-1.
E agora, eu vou fazer uma manipulação matemática para poder usar hipótese de indução.
Não o que eu faço? Eu multiplico aqui, o expoente, eu vou ter 2²-2.
Perfeito.
Separamos um expoente, tenho 2k vezes 2².
Por que você quis fazer essa separação? Porque está aparecendo aqui, 2²-2k, que é o que eu tenho aqui.
Mas eu ainda precisaria de 1 menos 1 para 2.
3a.
Então, esse termo aqui, ele vira 4 vezes 2²-1.
O jeito bem simples, deu agora, usar hipótese de indução, é lembrar o seguinte, se isso é verdadeiro, isso é uma igualdade, se eu passar o menos 1 para outro lado, isso aqui continua avar.
E aí eu tenho que 2²-2k é igual a 3a mais 1.
Então, eu posso substituir 2²k, sumir com essa potência e ter 3a mais 1 no lugar.
Dessa forma, eu chego em 12a mais 4 menos 1, que é 12a mais 3, olha 3 aparecendo.
Coloco 3 em evidência, e tem que esse termo é um núltiplo de 3.
Provando o que eu queria, fazendo a manipulação simples da hipótese, é uma manipulação simples da hipótese de indução, que é transformar desse jeito para esse jeito que continua a válida, eu posso substituir, eliminando a potência, e chegando ao múltiplo de 3, do jeito que eu precisava para provar, que era divisível, também quando n igual a k mais 1.
Bom, outro caso aqui, onde temos que prestar atenção, não só no domínio dos inteiros positivos, mas n maior que 3.
Nesse caso, para n igual a 4, o passo base se verifique.
Então, o meu passo base começa n igual a 4.
Perfeito.
Na minha hipótese de indução, então, é calco-adrado, o maior que 3k.
Suponho vale provar para n igual a k mais 1, ou seja, k mais 1 ao quadrado, o maior que 3 vezes k mais 1.
Como eu vou provar isso? K mais 1 ao quadrado, eu posso estonde desse jeito.
Calco-adrado, quadrado do primeiro, mais 2, de 1 por segundo, mais quadrado do segundo.
Tranquilo.
E pela hipótese de indução, eu tenho que calco-adrado, é maior que 3k.
E aí, a gente sempre tem essa tendência, eu sempre coloco esse passo, que é o que? A gente já vamos somar isso aqui, 5k.
Então, eu tenho que k mais 1 é maior que 5k mais 1.
Só que isso não me diz muito, o que eu quero provar é que k mais 1 ao quadrado é maior que 3 vezes k mais 1.
Eu estou colocando k mais 1 no bagunho.
Como é que eu vou chegar nesse k mais 1? Bom, então, eu separo esse 5k de novo, 3k.
Já cheguei no 3k.
E aqui eu tenho 2k mais 1.
Só que aí lembrem-se, vamos prestar atenção no 2.
O n tem que ser maior que 3.
Ou seja, com certeza esse 2k mais 1 é maior que supõe a 3.
2 vezes 3 mais 1, 7.
Esse termo aqui, com certeza, é maior que 7.
Se ele é maior que 7, ele é maior que 3.
Se ele é maior que 3, eu posso trocar essa relação aqui como 3k mais 3, porque esse termo é maior que 7 e consequentemente é maior que 3.
E colocando 3 em evidência, eu chego em k mais 1 ao quadrado, maior que 3k mais 1.
Provando o que eu queria por imissão.
Mais um caso aqui, é bem que o meu domínio é n maior que 1.
Então, meu passo base é n igual a 2.
O que eu faço? Verifica a propriedade, ela é válida por passo base.
Agora, eu assumo pra n igual a k, ou seja, 2k mais 1 menor que 3k, e pode exigir no som.
Vamos provar pra k mais 1.
Então, estou escrevendo aqui a expressão pra k mais 1.
2 vezes k mais 1, mais 1, menor que 3, e k mais 1.
Eu quero provar isso.
Então, o que eu faço? Começo com meu lado esquerdo aqui, para chegar no lado direito.
2 vezes k mais 1, mais 1, dá 2, k mais 3.
A gente se é resolvendo, e aí a gente tem que começar a pensar.
Primeiro, sempre, usual.
A gente está usando aqui, aí pode exigir no som.
Tentando usar e pode exigir no som.
Então, eu sei que 2k mais 1 é menor que 3k.
Opa, mas eu sou meio tudo aqui.
Eu posso separar.
Isso aqui, ainda é igual a 2k mais 1, mais 2.
E esse 2k mais 1 é menor que 3k.
Certo? Ah, mas eu queria 3k mais 3.
Só que 2 é menor que 3.
Então, 3k mais 2 é menor que 3k mais 3.
Coloco 3 em evidência xilo que 2 vezes k mais 1, mais 1 é menor que 3k mais 1.
Provando o que eu queria.
Segundo o princípio do som, o princípio do som forte, ele considera o passo básico, mas ele é sônica, no passo do tivo, a propriedade é valedá para todos os valores entre 1 e k.
E, uma vez, sendo valedas para esses valores, nós podemos provar aquela valedá para o k mais 1.
Descaso garantindo a valedade da propósição para todo n.
Vamos considerar um exemplo que, onde nós temos n estesos e queremos provar que para n estesos teremos n menos 1 s.
Então, no caso de n igual 1, teremos 0 s, n igual a 3 s, 2 s, n igual a 2 com a s.
Dessa forma, como a gente viu na figura anterior para n igual 1, teremos n estesos s.
Pelo segundo princípio da indução, nós podemos provar, cantar, provar o seguinte.
Nós vamos assumir que para n igual a k estesos, temos que qualquer quantidade r de estesos com r entre 1 e k atende para a propriedade de t, r menos 1 s.
Com isso está bem lecido.
Nós vamos supor que temos uma cerca com k mais 1 s.
Vamos remover uma sessão dessa cerca.
Não, não, não.
Se a gente remorva uma sessão dessa cerca, nós vamos separando ela em 2.
De tal forma que a soma dos estesos, 10 círcas com r, n e r 2 s, o j vai ser k mais 1 estesos.
Perfeito.
Bom, estuposo.
Por indo só forte, nós vamos ter que a primeira cerca vai ter r-1 s³, já que ela tinha r-1 estesos, e r-2 menos 1 s³, já que tinha r-2 estesos a segunda cerca.
Pô, é? Bom, dessa forma, nós podemos então sumar r-1 menos 1 mais r-2 menos 1, e ter um total de r-1 mais r-2 menos 2 s³, porém lembramos que r-1 mais r-2 corresponde a k mais 1 estesos, o que nos leva a k menos 1 s³.
Considerando as 2 círcas que foram separadas pela remoção de uma sessão.
Se eu volto com essa sessão, nós vamos ter a nossa serca com k mais 1 estesos tendo k sessões.
Provamos, assim, usando o segundo princípio da indução.
Um outro exemplo é provar que qualquer quantia de celo que maior ou igual a 8 centavos pode ser obtido usando apenas cero de 3 e 500 altos.
Mas o seguinte, então, quando a gente considera o passo básico, aí nós temos o n igual a 8, que é a menor quantidade possível 8 centavos, que facilmente é representado como 3 mais 5.
3 celo de 3 centavos e outros celo de 5 centavos.
Tranquilo.
Suponha agora que, para a n igual a r, a propriedade se verifica para quantias de celo entre 8 e k centavos.
Bom, nesse caso, nós podemos representar essa probabilidade dessa propriedade, como sendo 3 a mais 5 b para qualquer r, um dia a e b são inteiros, para qualquer r entre 8 e k.
Bom, note que para 9 centavos, a propriedade também se verifica, 3 vezes 3 mais 5 vezes 0, nós vamos ter 3 celo de 3 centavos e não precisamos de nenhum de 5.
E no caso de 10, nós centavos nós resolvemos com 2 celo de 5 centavos.
Com isso estabelecido, é bem que eu provei a nossa quantidade mínima era 8.
Eu provei então para 9 e para 10, porque agora a gente vai provar para cá mais 1 valores, onde esse cá mais 1 pode ser maior ou igual a 11 centavos.
Só que para fazer essa prova, eu vou retirar 3 centavos.
Então se eu tivesse na situação com 11 centavos, eu já aprovei para 10 para 9 para 8, de 11 menos 3, de 18 centavos.
Então, eu estou considerando qualquer n igual a k mais 1 maior ou igual a 11 centavos, porque já verificamos para 9 para 10 e para 8.
Então, nesse caso, o que nós vamos ter? Para n menos 3, eu vou ter k mais 1 menos 3, que me leva a k mais 2.
Ou seja, eu caio dentro daquele conjunto de valores para os quais, ainda só forte, me garante a validade da propriedade.
Isso significa que para k menos 2 centavos, eu vou ter 3 a mais 5 b, onde a i b, são as contias de celos de 3 e 5 centavos.
Eu consigo ter isso pela hipótese de indução.
Quando eu retormo com os 3 centavos, eu passo a ter, eu somo do 3 centavos aqui e aqui, eu passo a ter, nesse caso, que 3 a mais 3 vezes a mais 1 mais 5 b, que me leva a mais 1, continua sendo 1 ter.
Então, eu tenho 3 vezes uma quantidade inteira de celos, mais 5 centavos, vezes uma quantidade inteira de celos de 5 centavos.
E aqui, do meu lado esquerdo, eu tenho o meu k mais 1, que é representado dessa forma.
Então, eu não sei que, quando eu removo os 3 centavos, eu tenho que tomar cuidado com os casos intermediados, que eram 9 e 8, que o 9 é 10, que não tinha provado.
Mas uma vez que o krain me sumbe conjunto de valores, fazendo essa reenmoção de 3 centavos, eu não escolhi o 3 a toa, foi porque ele está aqui, no tipo de celos de 3 centavos, o que eu faço? Eu proveni então, por 2, por 9, por 10, e uma vez caindo em 8 para menos, eu sei que a propriedade é válida.
Sendo a propriedade é válida, eu posso, agora, retornar esses 3 centavos que me levam por k mais 1, e também me permitem verificar que, eu consigo escrever a quantidade de k mais 1 centavos em função de celos de 3 e 5 centavos.
Bom, eu espero que vocês tenham entendido todo esse conteúdo está baseado na seção 2.
2 do nosso material base, recomendo que vocês leiam, tá? E nos vemos na próxima aula.
Muito obrigado.