Fundamentos Matemáticos para Computação - Indução (Libras)

[Música] Olá alunas e alunos do curso de fundamentos matemáticos para computação nesta vídeo aula eu vou estar falando de indução matemática custar apresentando o primeiro princípio da indução e o segundo princípio da indução matemática eu gosto sempre de usar esse exemplo de subir numa escada infinita Suponha que eu tenho que verificar a propriedade de subir um degrau dentro desse domínio aí de escadas infinita então eu verifico maior eu consigo alcançar o primeiro degrau tá legal consigo Então eu posso supor que eu seja capaz de chegar a um degrau a qualquer mas se eu consigo chegar

a um degrau qualquer então será que eu consigo passar para o próximo então eu vou lá e verifico se eu consigo passar para o próximo degrau sim Opa então nessa escada infinita eu consigo de um degrau puro para o outro ia percorrendo toda a escada basicamente essa ideia do princípio da indução você parte de um passo básico e verifica um passo intuitivo que comprova a capacidade de que você tem de percorrer de manter aquela propriedade inválida ainda que dentro de uma coleção de valores infinitos Bom pelo primeiro princípio da indução Então eu tenho que verificar

que a propriedade é válida para um n = 1 e para todo cá no domínio de inteiros positivos se a propriedade for válida para cá então eu verifico que ela válida por seguinte cara mais um nesse caso comprovando isso eu posso dizer que ela é verdadeira para todo n nesse domínio de inteiros positivos Vamos considerar aqui uma propriedade de que a quantidade de indivíduos duplica de uma geração para outra se isso tá acontecendo eu posso assumir que eu vou ter dois descendentes depois quatro depois 8 certo e que essa relação de descendência então na geração

n me leva a crer que eu vou ter dois elevado a 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 queremos então nós estamos assumindo que vamos ter dois elevado a n descendentes como proposição e como hipótese de que a alma duplicação de uma geração para outra esse contexto eu posso considerar então a hipótese de que duplica de uma geração para outra estratégia de dois elevado a mtcendentes E aí tem como passo base a verificação de que para n = 1 eu vou

ter uma duplicação de descendente perfeito foi o que a gente viu naquele gráfico naquela agora eu assumo verdadeiro para todo o Card E aí eu vou tentar prova R para cá mais um como então para ele colocar eu assumo que aquela relação matemática que eu estou supondo é verdadeira ou seja que na geração caia eu vou ter dois elevado AK nós descendente vamos agora provar para n = k + 1 só que para provar para n = +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 + 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 tô assumindo que eu tenha dois elevado a cada descendentes logo eu vou ter dois elevado a k + 1 na geração k + 1 porque prova a relação que eu estava estabelecendo de na geração k + 1 tendo dois elevado a k + 1 descendentes agora um outro contexto de demonstração vamos supor esse somatório aqui certo e eu quero provar então Considerando o domínios inteiros positivos para ele

igual a um ou seja se eu tenho um termo no somatório essa fórmula vai ser válida bom para um termo somatório do lado esquerdo eu vou ter um para fórmula do lado direito bater então eu teria que ter um ao quadrado que a quantidade de elementos que eu tenho aqui o que bate temos a igualdade verificada agora vamos supor para n = k nesse caso eu considero que essa relação é válida para n = k e vou provar para colocar mais um Isso significa que eu acredito que até o cais um elemento quando eu acrescentar

o k + 1 vai ter essa forma eu vou ter a relação do lado direito ca+1 ao quadrado bom eu vou ter Igual a k + 1 ao quadrado bom nesse caso então novamente eu vou assumir a minha hipótese de indução Ou seja eu sei que até o termocar mais um até o caesmo termo né essa relação se resume a cal ao quadrado então eu posso pegar esse termo que substituir por K ao quadrado dessa 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 cal ao quadrado + 2K + 1 que nada mais é do que ficar mais um ao quadrado Então dessa forma o meu lado esquerdo é igual ao lado direito e a relação é válida para cá mais um logo vai ser válida para ele outra outro tipo de demonstração Suponha que eu tenha dois n maior que n nesse caso para n = 1 eu vou fazendo a multiplicação 2 vezes 1 maior que 1 isso de fato se verifica dois é maior que um a soma válida para ele igual a k Então

eu tenho que dois k é maior que k ou hipótese de indução agora para provar para ele colocar mais um que que eu faço eu quero provar que duas vezes ficar mais um é maior que cai mais um duas vezes k + 1 = 2K + 2 pela hipótese de indução 2K é maior que k 2 k é maior então eu tenho uma igualdade aqui quebro para uma desigualdade porque dois k é maior que cai e mantém o 2 só que k + 2 é maior que k + 1 porque 2 é maior que um

só fato então eu tenho que duas vezes ficar mais um é maior que k+1 provei para cá mais um a proposição de estar válida por indução agora eu vou provar que eu quero provar para inteiros positivos que dois elevado a 2n - 1 é divisível por 3 né Nós vimos que para provar que o número é divisível 3 mesma coisa que a gente tá provando que ele é um múltiplo de três Então vamos supor que isso aqui seja 3 A onde há um inteiro positivo nesse caso para n = 1 eu vou verificar que eu

tenho dois elevado ao quadrado que é 4 - 1 3 3 é divisível por 3 perfeito passa o básico verificado agora suponha para n = k nesse caso eu vou considerar que essa relação se estabelece que dois elevador chegar -1 é um múltiplo de 3 tranquilo agora o meu trabalho é provar para cá mais um para fazer essa demonstração eu vou começar escrevendo essa expressão para cá mais um que é 2 elevado a 2 k + 1 - 1 e agora eu vou fazer uma manipulação matemática para poder usar hipótese de indução então o que

que eu faço multiplico aqui o expoente vou ter dois elevado a 2K + 2 perfeito separamos expoente tenho dois k x 2 ao quadrado por que que eu quis fazer essa separação porque tá aparecendo aqui dois elevado a 2K que é o que eu tenho aqui mas eu ainda precisaria do menos um para deduzir três a correto Então esse tema aqui ele vira quatro desses dois elevado a k - 1 um jeito bem simples deu agora usar hipótese de indução é eu lembrar o seguinte se isso aqui é verdadeiro Isso aqui é uma igualdade se

eu passar o menos um para o outro lado isso aqui continua vai e aí eu tenho que dois elevado a 2 k é igual a 3 a mais um então eu posso substituir o dois elevado 2K sumir com essa potência e ter três a mais um no lugar dessa forma eu chego em 12 a mais quatro menos um que é 12 a mais três Olha o 3 aparecendo coloca três em evidência e tem que esse termo é um múltiplo de 3 provando 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 aqui continua 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 = k + 1 bom outro caso aqui onde temos que prestar atenção não só no domínio dos inteiros positivos mas n e maior que 3 nesse caso para N = 4 o passo base se verifica então meu passo básico perfeito na minha hipótese de indução então é carro quadrado maior que 3 k Suponho válido provar para n = k

+ 1 ou seja k + 1 ao quadrado maior que três vezes ficar mais um como que eu vou provar isso cara mais um ao quadrado eu posso expandir desse jeito calma quadrado quadrado do primeiro mas os primeiros segundo mais quadrado do segundo tranquilo pela hipótese de indução eu tenho k² é maior que 3K E aí a gente sempre tem essa tendência sempre coloco Esse passo que é o que a gente ah vamos somar isso aqui 5k Então eu tenho que ficar mais um é maior que 5k + 1 só que isso não me diz

muito o que eu quero provar e ficar mais um ao quadrado é maior que três vezes k + 1 tô colocando k + 1 no lugar como é que eu vou chegar nesse canais bom então eu separo esses cinco k de novo 3K já cheguei no 3K e aqui eu tenho dois k + 1 só que aí lembre-se vamos prestar atenção no domingo o n tem que ser maior do que três ou seja com certeza esse dois ficar mais um é maior que suponha três duas vezes três mais um sete esse termo aqui com certeza

é maior que 7 se ele é maior que 7 ele é maior que três e se ele é maior que 3 eu posso trocar essa relação aqui como 3K + 3 porque esse termo é maior que 7 e consequentemente maior que três e colocando três em evidência eu chego em casa mais um ao quadrado maior que três canais um Provando o que eu queria por indução mais um caso aqui reparem que o meu domínio é n maior que 1 então eu passo base é n = 2 que que eu faço Verifica a propriedade ela é

válida por passo base agora eu assumo para n = k ou seja 2K + 1 menor que 3 km e hipótese de indução Vamos provar para cá mais um então tô escrevendo aqui a expressão para cá mais um duas vezes cá mais um mais um menor que três que eu quero provar isso Então o que eu faço começo com meu lado esquerdo aqui para chegar no lado direito duas vezes ficar mais um mais um dá dois k + 3 a gente sai resolvendo E aí a gente tem que começar a pensar primeiro sempre usual a

gente tá usando aqui a hipótese de indução tentando usar hipótese de indução então eu sei que dois k mais um é menor que 3K Opa mas eu somei tudo aqui eu posso separar isso aqui ainda é igual a 2K + 1 + 2 e esse dois ficar mais um é menor que três k certo ah mas eu queria três k mais três só que dois é menor que 3 então 3K + 2 é menor que 3K + 3 coloco 3 em evidência chego que duas vezes k + 1 + 1 é menor que 3K +

1 provando que eu queria o segundo princípio da indução é o princípio da indução forte ele considera o passo básico mas ele assume no Passo indutivo a propriedade é válida para todos os valores entre um e k e uma vez sendo válidas para esses valores nós podemos provar que ela é válida para o k + 1 desse caso garantindo a validade da proposição para todo ele não Vamos considerar um exemplo aqui onde nós temos n esteios e que queremos provar que para esse termos teremos em menos um exceções então no caso de n = 1

Stay teremos 0 sessões em = 3 extenso duas sessões n = 2 uma sessão bom nessa forma como a gente viu na figura anterior para n = 1 Esteio teremos essas sessões Ok pelo segundo princípio da indução nós podemos provar cantar provar o seguinte nós vamos assumir para n = stays temos que qualquer quantidade é de esteios com R entre 1 e k atende a propriedade de terra menos um acessórios beleza com isso estabelecido nós vamos supor que temos uma cerca com k + t e vamos remover uma sessão dessa cerca não é um Stay

é uma sessão não se a gente remove uma sessão dessa cerca nós vamos estar separando ela em duas certo de tal forma que a soma dos esteios né das cercas com R no R2 Esteio vai ser capaz Perfeito nós vamos ter que a primeira cerca vai ter R -1 exceções já que ela tinha R1 States e R2 menos uma sessões já que tinha r26 a segunda cerca bom dessa forma nós podemos então somar R1 menos R1 -1 + R2 - 1 e t um total de R1 mais r2-2 sessões porém lembramos que R1 + R2

corresponde a k+1 Esteio o que nos leva a k - 1 sessões considerando as duas cercas que foram separadas pela remoção de uma sessão se eu volto com essa sessão nós vamos ter a nossa cerca com k + 1 States tendo cá sessões provamos assim usando o segundo princípio da indução um outro exemplo é provar que qualquer quantia de Sela que maior ou igual a 8 centavos pode ser obtido usando apenas sermos de 3 e 5 centavos fazer o seguinte então quando a gente considera o passo básico aí nós temos um n = 8 que

é a menor quantidade possível 8 centavos que facilmente é representado como três mas cinco terceiro três um selo de três centavos e outros selo de cinco centavos tranquilo suponha agora que para ele igual a r a propriedade se verifica né para continhas de selo entre 8 e cá sentados nesse caso nós podemos representar essa validade dessa propriedade né como sendo 3a + 5b para qualquer R onde A e B são inteiros né para qualquer R entre 8 e k Note que para nove centavos a propriedade também se verifica ela é três vezes três mais cinco

vezes zero nós vamos ter três selos de três centavos e não precisamos de nenhum de 5 e no caso de 10 nós centavos nós resolvemos com dois selos de cinco centavos tudo bem com isso estabelecido é Repare 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 um valores onde esse k + 1 pode ser maior ou igual a 11 centavos só que para fazer essa prova eu vou retirar três centavos então se eu tivesse na situação com 11

centavos eu já provei para 10 para 9 para 8 de 11 menos três seriam oito centavos mas então eu tô considerando qualquer n = k + 1 maior ou igual a 11 centavos porque já verificamos para 9 para 10 e para oito Então nesse caso o que que nós vamos ter para n - 3 eu vou ter k + 1 - 3 que me leva a k + 2 ou seja eu caio dentro daquele conjunto de valores para os quais ainda são fortes me garante a validade da propriedade isso significa então que para cá menos

dois centavos eu vou ter três a mais 5b né onde A e B são as quantias de selos de 3 e 5 centavos eu consigo ter isso pela hipótese de indução quando eu retorno com os três centavos eu passo a ter eu só mando três centavos aqui e aqui eu passo a ter nesse caso aqui três três vezes a mais um mais cinco B que me leva a mais um continua sendo um inteiro Então eu tenho três vezes uma quantidade inteira de Selos mais cinco centavos vezes uma quantidade inteira de selos de cinco centavos e

aqui do meu lado esquerdo eu tenho o meu k + 1 que é representado dessa forma então Observe que quando eu removo os três centavos eu tenho que tomar cuidado com os casos intermediários que eram 9 ou 8 que o 9 10 quando tinha provado mas uma vez que eu cai no subconjunto de valores fazendo essa remoção de três centavos eu não escolhi o três à toa né Foi porque ele tá que um tipo de selo de três centavos o que que eu faço eu provei então dois para o 9 por 10 e uma vez

caindo né em 8 para menos eu sei que a propriedade é válida sendo a propriedade é válida eu posso agora retornar esses três centavos que me levam procar mais um e também me permitem verificar que eu consigo escrever a quantidade de cá mais um centavos em função de selos de três e cinco centavos bom eu espero que vocês tenham entendido todo esse conteúdo tá baseado na sessão 2.2 do nosso material base recomendo que vocês Leiam tá e nos vemos na próxima aula muito obrigado [Música]