Inducao Matematica - Matematica Discreta - Apresentacao Power Point

Inducao Matematica QXD0008 Matematica Discreta Prof Lucas Ismaily ismailybfufcbr Universidade Federal do Ceara 1º semestre2024 Topicos desta aula Nesta apresentacao O que e a Inducao Matematica Por que a Inducao Matematica e um metodo de demonstracao valido Como usar a Inducao Matematica 2 Referˆencias para esta aula Secao 41 do livro Matematica Discreta e suas Aplicacoes Autor Kenneth H Rosen Sexta Edicao Secao 51 do livro Discrete Mathematics and Its Applications Author Kenneth H Rosen Seventh Edition English version 3 Introdução Que tipo de teoremas podemos provar usando Inducao Matematica Inducao matematica pode ser usada para provar enunciados que afirmam que uma determinada funcao proposicional Pn e verdadeira para todos os naturais ou inteiros positivos nPn Lembrese em logica uma funcao proposicional Pn e uma afirmacao expressa de uma forma que assumiria o valor de verdadeiro ou falso exceto que dentro da sentenca existe uma variavel n que nao esta definida o que deixa o valorverdade da afirmacao indeterminado 5 Que tipo de teoremas podemos provar usando Inducao Matematica Inducao matematica pode ser usada para provar enunciados que afirmam que uma determinada funcao proposicional Pn e verdadeira para todos os naturais ou inteiros positivos nPn Lembrese em logica uma funcao proposicional Pn e uma afirmacao expressa de uma forma que assumiria o valor de verdadeiro ou falso exceto que dentro da sentenca existe uma variavel n que nao esta definida o que deixa o valorverdade da afirmacao indeterminado 5 Motivacao Queremos provar que para todo inteiro positivo n 1 2 n nn 1 2 Seja Pn o predicado 1 2 n nn1 2 Observamos que P1 P2 e P3 valem P1 1 111 2 P2 1 2 3 23 2 P3 1 2 3 6 34 2 Conjetura n Z Pn 6 Motivacao Queremos provar que para todo inteiro positivo n 1 2 n nn 1 2 Seja Pn o predicado 1 2 n nn1 2 Observamos que P1 P2 e P3 valem P1 1 111 2 P2 1 2 3 23 2 P3 1 2 3 6 34 2 Conjetura n Z Pn 6 Motivacao Queremos provar que para todo inteiro positivo n 1 2 n nn 1 2 Seja Pn o predicado 1 2 n nn1 2 Observamos que P1 P2 e P3 valem P1 1 111 2 P2 1 2 3 23 2 P3 1 2 3 6 34 2 Conjetura n Z Pn 6 Motivacao Queremos provar que para todo inteiro positivo n 1 2 n nn 1 2 Seja Pn o predicado 1 2 n nn1 2 Observamos que P1 P2 e P3 valem P1 1 111 2 P2 1 2 3 23 2 P3 1 2 3 6 34 2 Conjetura n Z Pn 6 Provando P4 usando P3 Pn e o predicado 1 2 n nn1 2 Queremos provar P4 ou seja 1 2 3 4 45 2 Note que o somatorio 1 2 3 4 contem o somatorio 1 2 3 do predicado P3 Se por um momento supormos que P3 e verdadeiro podemos substituir 1 2 3 pelo valor 34 2 no somatorio 1 2 3 4 1 2 3 4 3 4 2 4 3 4 2 4 2 4 3 2 2 4 5 2 Agora podemos construir uma prova para P4 usando o fato de que P3 e verdadeiro slide anterior e que P3 P4 e verdadeiro Modus Ponens P3 P3 P4 P4 7 Provando P4 usando P3 Pn e o predicado 1 2 n nn1 2 Queremos provar P4 ou seja 1 2 3 4 45 2 Note que o somatorio 1 2 3 4 contem o somatorio 1 2 3 do predicado P3 Se por um momento supormos que P3 e verdadeiro podemos substituir 1 2 3 pelo valor 34 2 no somatorio 1 2 3 4 1 2 3 4 3 4 2 4 3 4 2 4 2 4 3 2 2 4 5 2 Agora podemos construir uma prova para P4 usando o fato de que P3 e verdadeiro slide anterior e que P3 P4 e verdadeiro Modus Ponens P3 P3 P4 P4 7 Provando P4 usando P3 Pn e o predicado 1 2 n nn1 2 Queremos provar P4 ou seja 1 2 3 4 45 2 Note que o somatorio 1 2 3 4 contem o somatorio 1 2 3 do predicado P3 Se por um momento supormos que P3 e verdadeiro podemos substituir 1 2 3 pelo valor 34 2 no somatorio 1 2 3 4 1 2 3 4 3 4 2 4 3 4 2 4 2 4 3 2 2 4 5 2 Agora podemos construir uma prova para P4 usando o fato de que P3 e verdadeiro slide anterior e que P3 P4 e verdadeiro Modus Ponens P3 P3 P4 P4 7 Provando P4 usando P3 Pn e o predicado 1 2 n nn1 2 Queremos provar P4 ou seja 1 2 3 4 45 2 Note que o somatorio 1 2 3 4 contem o somatorio 1 2 3 do predicado P3 Se por um momento supormos que P3 e verdadeiro podemos substituir 1 2 3 pelo valor 34 2 no somatorio 1 2 3 4 1 2 3 4 3 4 2 4 3 4 2 4 2 4 3 2 2 4 5 2 Agora podemos construir uma prova para P4 usando o fato de que P3 e verdadeiro slide anterior e que P3 P4 e verdadeiro Modus Ponens P3 P3 P4 P4 7 Provando P4 usando P3 Pn e o predicado 1 2 n nn1 2 Queremos provar P4 ou seja 1 2 3 4 45 2 Note que o somatorio 1 2 3 4 contem o somatorio 1 2 3 do predicado P3 Se por um momento supormos que P3 e verdadeiro podemos substituir 1 2 3 pelo valor 34 2 no somatorio 1 2 3 4 1 2 3 4 3 4 2 4 3 4 2 4 2 4 3 2 2 4 5 2 Agora podemos construir uma prova para P4 usando o fato de que P3 e verdadeiro slide anterior e que P3 P4 e verdadeiro Modus Ponens P3 P3 P4 P4 7 Provando P4 usando P3 Pn e o predicado 1 2 n nn1 2 Queremos provar P4 ou seja 1 2 3 4 45 2 Note que o somatorio 1 2 3 4 contem o somatorio 1 2 3 do predicado P3 Se por um momento supormos que P3 e verdadeiro podemos substituir 1 2 3 pelo valor 34 2 no somatorio 1 2 3 4 1 2 3 4 3 4 2 4 3 4 2 4 2 4 3 2 2 4 5 2 Agora podemos construir uma prova para P4 usando o fato de que P3 e verdadeiro slide anterior e que P3 P4 e verdadeiro Modus Ponens P3 P3 P4 P4 7 Provando P4 usando P3 Pn e o predicado 1 2 n nn1 2 Queremos provar P4 ou seja 1 2 3 4 45 2 Note que o somatorio 1 2 3 4 contem o somatorio 1 2 3 do predicado P3 Se por um momento supormos que P3 e verdadeiro podemos substituir 1 2 3 pelo valor 34 2 no somatorio 1 2 3 4 1 2 3 4 3 4 2 4 3 4 2 4 2 4 3 2 2 4 5 2 Agora podemos construir uma prova para P4 usando o fato de que P3 e verdadeiro slide anterior e que P3 P4 e verdadeiro Modus Ponens P3 P3 P4 P4 7 Provando P4 usando P3 Pn e o predicado 1 2 n nn1 2 Queremos provar P4 ou seja 1 2 3 4 45 2 Note que o somatorio 1 2 3 4 contem o somatorio 1 2 3 do predicado P3 Se por um momento supormos que P3 e verdadeiro podemos substituir 1 2 3 pelo valor 34 2 no somatorio 1 2 3 4 1 2 3 4 3 4 2 4 3 4 2 4 2 4 3 2 2 4 5 2 Agora podemos construir uma prova para P4 usando o fato de que P3 e verdadeiro slide anterior e que P3 P4 e verdadeiro Modus Ponens P3 P3 P4 P4 7 Provando P4 usando P3 Pn e o predicado 1 2 n nn1 2 Queremos provar P4 ou seja 1 2 3 4 45 2 Note que o somatorio 1 2 3 4 contem o somatorio 1 2 3 do predicado P3 Se por um momento supormos que P3 e verdadeiro podemos substituir 1 2 3 pelo valor 34 2 no somatorio 1 2 3 4 1 2 3 4 3 4 2 4 3 4 2 4 2 4 3 2 2 4 5 2 Agora podemos construir uma prova para P4 usando o fato de que P3 e verdadeiro slide anterior e que P3 P4 e verdadeiro Modus Ponens P3 P3 P4 P4 7 Provando Pn Suponha que P1 e verdadeiro Alem disso suponha que k 1 Pk Pk 1 E possıvel provar Pn para outros valores de n maiores que 1 1 P1 premissa 2 P1 P2 premissa 3 P2 passos 1 2 modus ponens 4 P2 P3 premissa 5 P3 passos 3 4 modus ponens Podemos construir uma prova de Pn para todo valor de n 1 Isso nos leva ao Princıpio da Inducao Matematica 8 Provando Pn Suponha que P1 e verdadeiro Alem disso suponha que k 1 Pk Pk 1 E possıvel provar Pn para outros valores de n maiores que 1 1 P1 premissa 2 P1 P2 premissa 3 P2 passos 1 2 modus ponens 4 P2 P3 premissa 5 P3 passos 3 4 modus ponens Podemos construir uma prova de Pn para todo valor de n 1 Isso nos leva ao Princıpio da Inducao Matematica 8 Provando Pn Suponha que P1 e verdadeiro Alem disso suponha que k 1 Pk Pk 1 E possıvel provar Pn para outros valores de n maiores que 1 1 P1 premissa 2 P1 P2 premissa 3 P2 passos 1 2 modus ponens 4 P2 P3 premissa 5 P3 passos 3 4 modus ponens Podemos construir uma prova de Pn para todo valor de n 1 Isso nos leva ao Princıpio da Inducao Matematica 8 Provando Pn Suponha que P1 e verdadeiro Alem disso suponha que k 1 Pk Pk 1 E possıvel provar Pn para outros valores de n maiores que 1 1 P1 premissa 2 P1 P2 premissa 3 P2 passos 1 2 modus ponens 4 P2 P3 premissa 5 P3 passos 3 4 modus ponens Podemos construir uma prova de Pn para todo valor de n 1 Isso nos leva ao Princıpio da Inducao Matematica 8 Provando Pn Suponha que P1 e verdadeiro Alem disso suponha que k 1 Pk Pk 1 E possıvel provar Pn para outros valores de n maiores que 1 1 P1 premissa 2 P1 P2 premissa 3 P2 passos 1 2 modus ponens 4 P2 P3 premissa 5 P3 passos 3 4 modus ponens Podemos construir uma prova de Pn para todo valor de n 1 Isso nos leva ao Princıpio da Inducao Matematica 8 Provando Pn Suponha que P1 e verdadeiro Alem disso suponha que k 1 Pk Pk 1 E possıvel provar Pn para outros valores de n maiores que 1 1 P1 premissa 2 P1 P2 premissa 3 P2 passos 1 2 modus ponens 4 P2 P3 premissa 5 P3 passos 3 4 modus ponens Podemos construir uma prova de Pn para todo valor de n 1 Isso nos leva ao Princıpio da Inducao Matematica 8 Provando Pn Suponha que P1 e verdadeiro Alem disso suponha que k 1 Pk Pk 1 E possıvel provar Pn para outros valores de n maiores que 1 1 P1 premissa 2 P1 P2 premissa 3 P2 passos 1 2 modus ponens 4 P2 P3 premissa 5 P3 passos 3 4 modus ponens Podemos construir uma prova de Pn para todo valor de n 1 Isso nos leva ao Princıpio da Inducao Matematica 8 Princıpio da Inducao Matematica 9 Princıpio da Inducao Matematica PIM Tecnica de demonstracao usada para provar teoremas de generalizacao da forma xPx onde Px expressa uma propriedade dos elementos x N Princıpio da inducao matematica Para todo numero natural n seja Pn uma proposicao Se 1 P0 e verdadeiro e 2 k N Pk Pk 1 e verdadeiro entao n N Pn e verdadeiro Escrito como regra de inferˆencia P0 kPk Pk 1 nPn 10 Princıpio da Inducao Matematica PIM Tecnica de demonstracao usada para provar teoremas de generalizacao da forma xPx onde Px expressa uma propriedade dos elementos x N Princıpio da inducao matematica Para todo numero natural n seja Pn uma proposicao Se 1 P0 e verdadeiro e 2 k N Pk Pk 1 e verdadeiro entao n N Pn e verdadeiro Escrito como regra de inferˆencia P0 kPk Pk 1 nPn 10 Princıpio da Inducao Matematica PIM Tecnica de demonstracao usada para provar teoremas de generalizacao da forma xPx onde Px expressa uma propriedade dos elementos x N Princıpio da inducao matematica Para todo numero natural n seja Pn uma proposicao Se 1 P0 e verdadeiro e 2 k N Pk Pk 1 e verdadeiro entao n N Pn e verdadeiro Escrito como regra de inferˆencia P0 kPk Pk 1 nPn 10 Princıpio da Inducao Matematica PIM Princıpio da inducao matematica Para todo numero natural n seja Pn uma proposicao Se 1 P0 e verdadeiro e 2 k N Pk Pk 1 e verdadeiro entao n N Pn e verdadeiro Uma demonstracao usando o Prıncıpio da Inducao Matematica e chamada de prova indutiva ou prova por inducao A verificacao da verdade de P0 em uma prova indutiva e chamado de caso base ou base da inducao A prova de que k N Pk Pk 1 e verdadeiro e chamada de passo indutivo ou passo da inducao a proposicao Pk e chamada Hipotese de inducao 11 Princıpio da Inducao Matematica PIM Entao para demonstrar uma afirmacao nPn usando o PIM vocˆe pode seguir este roteiro Base da Inducao Suponha que n 0 Prove que P0 e verdade Passo da Inducao Para k natural qualquer Instanciacao prove que Pk Pk 1 1 Suponha Pk verdadeira Hipotese de Inducao 2 Comece a analisar o cenario em que n k 1 de acordo com a natureza de Pn buscando uma oportunidade de aplicar a hipotese 3 Aplique a hipotese e organize sua conclusao 4 Conclua Pk 1 12 Princıpio da Inducao Matematica PIM Entao para demonstrar uma afirmacao nPn usando o PIM vocˆe pode seguir este roteiro Base da Inducao Suponha que n 0 Prove que P0 e verdade Passo da Inducao Para k natural qualquer Instanciacao prove que Pk Pk 1 1 Suponha Pk verdadeira Hipotese de Inducao 2 Comece a analisar o cenario em que n k 1 de acordo com a natureza de Pn buscando uma oportunidade de aplicar a hipotese 3 Aplique a hipotese e organize sua conclusao 4 Conclua Pk 1 12 Princıpio da Inducao Matematica PIM Observacao No passo da inducao nao assumimos que Pk e verdadeiro para todo inteiro k ou seja nao supomos o que deverıamos provar No passo da inducao e mostrado que se for assumido que Pk e verdadeiro entao Pk 1 tambem e verdadeiro Assim na prova do condicional Pk Pk 1 devemos usar obrigatoriamente a funcao proposicional Pk hipotese que estamos supondo ser verdadeira Sabendo que P0 e verdadeiro e que P0 P1 e verdadeiro podemos agora aplicar modus ponens para obter P1 13 Princıpio da Inducao Matematica PIM Observacao No passo da inducao nao assumimos que Pk e verdadeiro para todo inteiro k ou seja nao supomos o que deverıamos provar No passo da inducao e mostrado que se for assumido que Pk e verdadeiro entao Pk 1 tambem e verdadeiro Assim na prova do condicional Pk Pk 1 devemos usar obrigatoriamente a funcao proposicional Pk hipotese que estamos supondo ser verdadeira Sabendo que P0 e verdadeiro e que P0 P1 e verdadeiro podemos agora aplicar modus ponens para obter P1 13 Princıpio da Inducao Matematica PIM Observacao No passo da inducao nao assumimos que Pk e verdadeiro para todo inteiro k ou seja nao supomos o que deverıamos provar No passo da inducao e mostrado que se for assumido que Pk e verdadeiro entao Pk 1 tambem e verdadeiro Assim na prova do condicional Pk Pk 1 devemos usar obrigatoriamente a funcao proposicional Pk hipotese que estamos supondo ser verdadeira Sabendo que P0 e verdadeiro e que P0 P1 e verdadeiro podemos agora aplicar modus ponens para obter P1 13 Efeito domino Imagine uma fila infinita de dominos numerados 1 2 3 Suponha que sao validas as seguintes proposicoes para esta fila 1 a primeira peca e derrubada na direcao das demais 2 qualquer peca k esta suficientemente proxima da seguinte na fila a peca k 1 de modo que ao ser derrubada faz com que a sua vizinha tambem seja derrubada Como estas duas proposicoes sao verdadeiras concluımos que todos os dominos na fila sao derrubados 14 Efeito domino Imagine uma fila infinita de dominos numerados 1 2 3 Suponha que sao validas as seguintes proposicoes para esta fila 1 a primeira peca e derrubada na direcao das demais 2 qualquer peca k esta suficientemente proxima da seguinte na fila a peca k 1 de modo que ao ser derrubada faz com que a sua vizinha tambem seja derrubada Como estas duas proposicoes sao verdadeiras concluımos que todos os dominos na fila sao derrubados 14 Efeito domino Imagine uma fila infinita de dominos numerados 1 2 3 Suponha que sao validas as seguintes proposicoes para esta fila 1 a primeira peca e derrubada na direcao das demais 2 qualquer peca k esta suficientemente proxima da seguinte na fila a peca k 1 de modo que ao ser derrubada faz com que a sua vizinha tambem seja derrubada Como estas duas proposicoes sao verdadeiras concluımos que todos os dominos na fila sao derrubados 14 Inducao Matematica Exemplo Teorema Para todo n natural n2 n e par Demonstracao Seja n um natural e Pn n2 n e par uma propriedade Vamos provar por inducao em n que Pn e verdadeira para todo natural n Base Suponha que n 0 Neste caso devemos verificar se 02 0 e par Temos que 02 0 0 0 0 que e par Portanto a propriedade realmente vale quando n 0 Passo da Inducao Seja k um natural qualquer devemos mostrar que se k2 k e par entao k 12 k 1 e par Por prova direta suponha que k2 k e par HI Analisando o caso em que n k 1 temos que k 12 k 1 k2 2k 1 k 1 k2 k 2k Pela HI k2 k e par Logo existe j Z tal que k2 k 2j Ou seja k 12 k 1 2j 2k 2j k Como j k sao inteiros k 12 k 1 e par 15 Inducao Matematica Exemplo Teorema Para todo n natural n2 n e par Demonstracao Seja n um natural e Pn n2 n e par uma propriedade Vamos provar por inducao em n que Pn e verdadeira para todo natural n Base Suponha que n 0 Neste caso devemos verificar se 02 0 e par Temos que 02 0 0 0 0 que e par Portanto a propriedade realmente vale quando n 0 Passo da Inducao Seja k um natural qualquer devemos mostrar que se k2 k e par entao k 12 k 1 e par Por prova direta suponha que k2 k e par HI Analisando o caso em que n k 1 temos que k 12 k 1 k2 2k 1 k 1 k2 k 2k Pela HI k2 k e par Logo existe j Z tal que k2 k 2j Ou seja k 12 k 1 2j 2k 2j k Como j k sao inteiros k 12 k 1 e par 15 Inducao Matematica Exemplo Teorema Para todo n natural n2 n e par Demonstracao Seja n um natural e Pn n2 n e par uma propriedade Vamos provar por inducao em n que Pn e verdadeira para todo natural n Base Suponha que n 0 Neste caso devemos verificar se 02 0 e par Temos que 02 0 0 0 0 que e par Portanto a propriedade realmente vale quando n 0 Passo da Inducao Seja k um natural qualquer devemos mostrar que se k2 k e par entao k 12 k 1 e par Por prova direta suponha que k2 k e par HI Analisando o caso em que n k 1 temos que k 12 k 1 k2 2k 1 k 1 k2 k 2k Pela HI k2 k e par Logo existe j Z tal que k2 k 2j Ou seja k 12 k 1 2j 2k 2j k Como j k sao inteiros k 12 k 1 e par 15 Inducao Matematica Exemplo Teorema Para todo n natural n2 n e par Demonstracao Seja n um natural e Pn n2 n e par uma propriedade Vamos provar por inducao em n que Pn e verdadeira para todo natural n Base Suponha que n 0 Neste caso devemos verificar se 02 0 e par Temos que 02 0 0 0 0 que e par Portanto a propriedade realmente vale quando n 0 Passo da Inducao Seja k um natural qualquer devemos mostrar que se k2 k e par entao k 12 k 1 e par Por prova direta suponha que k2 k e par HI Analisando o caso em que n k 1 temos que k 12 k 1 k2 2k 1 k 1 k2 k 2k Pela HI k2 k e par Logo existe j Z tal que k2 k 2j Ou seja k 12 k 1 2j 2k 2j k Como j k sao inteiros k 12 k 1 e par 15 Inducao Matematica Exemplo Teorema Para todo n natural n2 n e par Demonstracao Seja n um natural e Pn n2 n e par uma propriedade Vamos provar por inducao em n que Pn e verdadeira para todo natural n Base Suponha que n 0 Neste caso devemos verificar se 02 0 e par Temos que 02 0 0 0 0 que e par Portanto a propriedade realmente vale quando n 0 Passo da Inducao Seja k um natural qualquer devemos mostrar que se k2 k e par entao k 12 k 1 e par Por prova direta suponha que k2 k e par HI Analisando o caso em que n k 1 temos que k 12 k 1 k2 2k 1 k 1 k2 k 2k Pela HI k2 k e par Logo existe j Z tal que k2 k 2j Ou seja k 12 k 1 2j 2k 2j k Como j k sao inteiros k 12 k 1 e par 15 Inducao Matematica Exemplo Teorema Para todo n natural n2 n e par Demonstracao Seja n um natural e Pn n2 n e par uma propriedade Vamos provar por inducao em n que Pn e verdadeira para todo natural n Base Suponha que n 0 Neste caso devemos verificar se 02 0 e par Temos que 02 0 0 0 0 que e par Portanto a propriedade realmente vale quando n 0 Passo da Inducao Seja k um natural qualquer devemos mostrar que se k2 k e par entao k 12 k 1 e par Por prova direta suponha que k2 k e par HI Analisando o caso em que n k 1 temos que k 12 k 1 k2 2k 1 k 1 k2 k 2k Pela HI k2 k e par Logo existe j Z tal que k2 k 2j Ou seja k 12 k 1 2j 2k 2j k Como j k sao inteiros k 12 k 1 e par 15 Inducao Matematica Exemplo Teorema Para todo n natural n2 n e par Demonstracao Seja n um natural e Pn n2 n e par uma propriedade Vamos provar por inducao em n que Pn e verdadeira para todo natural n Base Suponha que n 0 Neste caso devemos verificar se 02 0 e par Temos que 02 0 0 0 0 que e par Portanto a propriedade realmente vale quando n 0 Passo da Inducao Seja k um natural qualquer devemos mostrar que se k2 k e par entao k 12 k 1 e par Por prova direta suponha que k2 k e par HI Analisando o caso em que n k 1 temos que k 12 k 1 k2 2k 1 k 1 k2 k 2k Pela HI k2 k e par Logo existe j Z tal que k2 k 2j Ou seja k 12 k 1 2j 2k 2j k Como j k sao inteiros k 12 k 1 e par 15 Inducao Matematica Exemplo Teorema Para todo n natural n2 n e par Demonstracao Seja n um natural e Pn n2 n e par uma propriedade Vamos provar por inducao em n que Pn e verdadeira para todo natural n Base Suponha que n 0 Neste caso devemos verificar se 02 0 e par Temos que 02 0 0 0 0 que e par Portanto a propriedade realmente vale quando n 0 Passo da Inducao Seja k um natural qualquer devemos mostrar que se k2 k e par entao k 12 k 1 e par Por prova direta suponha que k2 k e par HI Analisando o caso em que n k 1 temos que k 12 k 1 k2 2k 1 k 1 k2 k 2k Pela HI k2 k e par Logo existe j Z tal que k2 k 2j Ou seja k 12 k 1 2j 2k 2j k Como j k sao inteiros k 12 k 1 e par 15 Por que o Princıpio da Inducao Matematica e valido 16 Axioma Princıpio da Boa Ordenacao Princıpio da Boa Ordenacao Todo subconjunto nao vazio de N contem um elemento mınimo Exemplos 2 4 6 8 10 2 3 5 7 11 13 17 0 4 4 9 16 25 36 49 Vamos usar esse axioma para provar que o Princıpio da Inducao Matematica PIM e verdadeiro 17 Axioma Princıpio da Boa Ordenacao Princıpio da Boa Ordenacao Todo subconjunto nao vazio de N contem um elemento mınimo Exemplos 2 4 6 8 10 2 3 5 7 11 13 17 0 4 4 9 16 25 36 49 Vamos usar esse axioma para provar que o Princıpio da Inducao Matematica PIM e verdadeiro 17 Axioma Princıpio da Boa Ordenacao Princıpio da Boa Ordenacao Todo subconjunto nao vazio de N contem um elemento mınimo Exemplos 2 4 6 8 10 2 3 5 7 11 13 17 0 4 4 9 16 25 36 49 Vamos usar esse axioma para provar que o Princıpio da Inducao Matematica PIM e verdadeiro 17 Demonstração do PIM Teorema Para cada natural n seja Pn uma proposição Se 1 P0 é verdadeiro e 2 k ℕ Pk Pk 1 é verdadeiro então n ℕ Pn é verdadeiro Demonstração do PIM Teorema Para cada natural n seja Pn uma proposição Se 1 P0 é verdadeiro e 2 k ℕ Pk Pk 1 é verdadeiro então n ℕ Pn é verdadeiro Escrevendo mais simbolicamente P0 kPk Pk 1 nPn Estratégia Vamos provar por contradição Logo supomos que A é verdadeiro e que B é falso e então tentamos alcançar uma contradição Demonstracao do PIM Teorema Para cada natural n seja Pn uma proposicao Se 1 P0 e verdadeiro e 2 k N Pk Pk 1 e verdadeiro entao n N Pn e verdadeiro Demonstracao Suponha por absurdo que as condicoes 1 e 2 sao satisfeitas mas existe algum natural n para o qual Pn e falsa Seja S n N Pn e falsa Como S e um subconjunto nao vazio de N pelo Princıpio da Boa Ordenacao temos que S contem um menor elemento s Como P0 e verdadeiro 0 S Entao s 1 e s 1 N Portanto s 1 S e entao Ps 1 e verdadeira Pela condicao 2 Ps tambem e verdadeira e assim s S Isso contudo contradiz nossa suposicao de que s S 19 Demonstracao do PIM Teorema Para cada natural n seja Pn uma proposicao Se 1 P0 e verdadeiro e 2 k N Pk Pk 1 e verdadeiro entao n N Pn e verdadeiro Demonstracao Suponha por absurdo que as condicoes 1 e 2 sao satisfeitas mas existe algum natural n para o qual Pn e falsa Seja S n N Pn e falsa Como S e um subconjunto nao vazio de N pelo Princıpio da Boa Ordenacao temos que S contem um menor elemento s Como P0 e verdadeiro 0 S Entao s 1 e s 1 N Portanto s 1 S e entao Ps 1 e verdadeira Pela condicao 2 Ps tambem e verdadeira e assim s S Isso contudo contradiz nossa suposicao de que s S 19 Demonstracao do PIM Teorema Para cada natural n seja Pn uma proposicao Se 1 P0 e verdadeiro e 2 k N Pk Pk 1 e verdadeiro entao n N Pn e verdadeiro Demonstracao Suponha por absurdo que as condicoes 1 e 2 sao satisfeitas mas existe algum natural n para o qual Pn e falsa Seja S n N Pn e falsa Como S e um subconjunto nao vazio de N pelo Princıpio da Boa Ordenacao temos que S contem um menor elemento s Como P0 e verdadeiro 0 S Entao s 1 e s 1 N Portanto s 1 S e entao Ps 1 e verdadeira Pela condicao 2 Ps tambem e verdadeira e assim s S Isso contudo contradiz nossa suposicao de que s S 19 Demonstracao do PIM Teorema Para cada natural n seja Pn uma proposicao Se 1 P0 e verdadeiro e 2 k N Pk Pk 1 e verdadeiro entao n N Pn e verdadeiro Demonstracao Suponha por absurdo que as condicoes 1 e 2 sao satisfeitas mas existe algum natural n para o qual Pn e falsa Seja S n N Pn e falsa Como S e um subconjunto nao vazio de N pelo Princıpio da Boa Ordenacao temos que S contem um menor elemento s Como P0 e verdadeiro 0 S Entao s 1 e s 1 N Portanto s 1 S e entao Ps 1 e verdadeira Pela condicao 2 Ps tambem e verdadeira e assim s S Isso contudo contradiz nossa suposicao de que s S 19 Demonstracao do PIM Teorema Para cada natural n seja Pn uma proposicao Se 1 P0 e verdadeiro e 2 k N Pk Pk 1 e verdadeiro entao n N Pn e verdadeiro Demonstracao Suponha por absurdo que as condicoes 1 e 2 sao satisfeitas mas existe algum natural n para o qual Pn e falsa Seja S n N Pn e falsa Como S e um subconjunto nao vazio de N pelo Princıpio da Boa Ordenacao temos que S contem um menor elemento s Como P0 e verdadeiro 0 S Entao s 1 e s 1 N Portanto s 1 S e entao Ps 1 e verdadeira Pela condicao 2 Ps tambem e verdadeira e assim s S Isso contudo contradiz nossa suposicao de que s S 19 Demonstracao do PIM Teorema Para cada natural n seja Pn uma proposicao Se 1 P0 e verdadeiro e 2 k N Pk Pk 1 e verdadeiro entao n N Pn e verdadeiro Demonstracao Suponha por absurdo que as condicoes 1 e 2 sao satisfeitas mas existe algum natural n para o qual Pn e falsa Seja S n N Pn e falsa Como S e um subconjunto nao vazio de N pelo Princıpio da Boa Ordenacao temos que S contem um menor elemento s Como P0 e verdadeiro 0 S Entao s 1 e s 1 N Portanto s 1 S e entao Ps 1 e verdadeira Pela condicao 2 Ps tambem e verdadeira e assim s S Isso contudo contradiz nossa suposicao de que s S 19 Mais exemplos de demonstracoes usando Inducao Matematica 20 Inducao Matematica Exemplos Teorema 20 21 22 2n 2n1 1 para todo natural n Demonstracao Seja Pn 20 21 22 2n 2n1 1 para um inteiro n Vamos provar por inducao em n que Pn e verdadeira para todo natural n Base Suponha que n 0 Note que P0 e verdadeira pois 20 1 21 1 201 1 Isso completa o caso base da inducao 21 Inducao Matematica Exemplos Teorema 20 21 22 2n 2n1 1 para todo natural n Demonstracao Seja Pn 20 21 22 2n 2n1 1 para um inteiro n Vamos provar por inducao em n que Pn e verdadeira para todo natural n Base Suponha que n 0 Note que P0 e verdadeira pois 20 1 21 1 201 1 Isso completa o caso base da inducao 21 Inducao Matematica Exemplos Teorema 20 21 22 2n 2n1 1 para todo natural n Demonstracao Seja Pn 20 21 22 2n 2n1 1 para um inteiro n Vamos provar por inducao em n que Pn e verdadeira para todo natural n Base Suponha que n 0 Note que P0 e verdadeira pois 20 1 21 1 201 1 Isso completa o caso base da inducao 21 Inducao Matematica Exemplos Teorema 20 21 22 2n 2n1 1 para todo natural n Demonstracao Seja Pn 20 21 22 2n 2n1 1 para um inteiro n Vamos provar por inducao em n que Pn e verdadeira para todo natural n Base Suponha que n 0 Note que P0 e verdadeira pois 20 1 21 1 201 1 Isso completa o caso base da inducao 21 Inducao Matematica Exemplos Teorema 20 21 22 2n 2n1 1 para todo natural n Continuacao da Demonstracao Passo da Inducao Seja k um numero natural qualquer vamos mostrar que Pk Pk 1 SE 20 21 2k 2k1 1 ENTAO 20 21 2k 2k1 2k11 1 Por prova direta suponha que 20 21 2k 2k1 1 HI Devemos mostrar que 20 21 2k 2k1 2k11 1 22 Inducao Matematica Exemplos Teorema 20 21 22 2n 2n1 1 para todo natural n Continuacao da Demonstracao Passo da Inducao Seja k um numero natural qualquer vamos mostrar que Pk Pk 1 SE 20 21 2k 2k1 1 ENTAO 20 21 2k 2k1 2k11 1 Por prova direta suponha que 20 21 2k 2k1 1 HI Devemos mostrar que 20 21 2k 2k1 2k11 1 22 Inducao Matematica Exemplos Teorema 20 21 22 2n 2n1 1 para todo natural n Continuacao da Demonstracao Passo da Inducao Seja k um numero natural qualquer vamos mostrar que Pk Pk 1 SE 20 21 2k 2k1 1 ENTAO 20 21 2k 2k1 2k11 1 Por prova direta suponha que 20 21 2k 2k1 1 HI Devemos mostrar que 20 21 2k 2k1 2k11 1 22 Indução Matemática Exemplos Teorema 20 21 22 2n 2n1 1 para todo natural n Continuação da Demonstração Passo da Indução Seja k um número natural qualquer vamos mostrar que Pk Pk 1 SE 20 21 2k 2k1 1 ENTÃO 20 21 2k 2k1 2k11 1 Por prova direta suponha que 20 21 2k 2k1 1 HI Devemos mostrar que 20 21 2k 2k1 2k11 1 Oportunidade de usar a HI Usando a HI podemos substituir a expressão destacada Assim temos que 20 21 2k 2k1 2k1 1 2k1 Inducao Matematica Exemplos Teorema 20 21 22 2n 2n1 1 para todo natural n Continuacao da Demonstracao 20 21 2k 2k1 2k1 1 2k1 2 2k1 1 2k11 1 2k11 1 A ultima equacao mostra que Pk 1 e verdadeira sob a hipotese de que Pk e verdadeira Isso completa a prova por inducao Portanto para todo numero natural n temos que 20 21 22 2n 2n1 1 24 Inducao Matematica Exemplos Teorema 20 21 22 2n 2n1 1 para todo natural n Continuacao da Demonstracao 20 21 2k 2k1 2k1 1 2k1 2 2k1 1 2k11 1 2k11 1 A ultima equacao mostra que Pk 1 e verdadeira sob a hipotese de que Pk e verdadeira Isso completa a prova por inducao Portanto para todo numero natural n temos que 20 21 22 2n 2n1 1 24 Observacoes sobre Inducao Problema Muitas vezes queremos mostrar que uma propriedade Pn vale para inteiros n b b 1 b 2 tal que b e um inteiro diferente de zero Inducao tambem permite provar propriedades sobre elementos do conjunto b b 1 b 2 pois este conjunto respeita o princıpio da boa ordenacao A fim de usar inducao matematica para provar que Pn e verdadeira para n b b 1 b 2 onde b e um inteiro diferente de 1 Mostramos que Pb e verdadeira na Base e No passo indutivo mostramos que o condicional Pk Pk 1 e verdadeiro para k b b 1 b 2 Note que b pode ser negativo zero ou positivo 25 Observacoes sobre Inducao Problema Muitas vezes queremos mostrar que uma propriedade Pn vale para inteiros n b b 1 b 2 tal que b e um inteiro diferente de zero Inducao tambem permite provar propriedades sobre elementos do conjunto b b 1 b 2 pois este conjunto respeita o princıpio da boa ordenacao A fim de usar inducao matematica para provar que Pn e verdadeira para n b b 1 b 2 onde b e um inteiro diferente de 1 Mostramos que Pb e verdadeira na Base e No passo indutivo mostramos que o condicional Pk Pk 1 e verdadeiro para k b b 1 b 2 Note que b pode ser negativo zero ou positivo 25 Inducao Matematica Exemplos Teorema Para todo inteiro positivo 1 2 n nn1 2 Demonstracao Seja Pn a propriedade 1 2 n nn1 2 Vamos provar por inducao no inteiro positivo n que Pn e verdadeira para todo n Base Suponha que n 1 Neste caso devemos verificar se 1 111 2 Temos que 111 2 12 2 2 2 1 Portanto a propriedade Pn vale quando n 1 26 Inducao Matematica Exemplos Teorema Para todo inteiro positivo 1 2 n nn1 2 Demonstracao Seja Pn a propriedade 1 2 n nn1 2 Vamos provar por inducao no inteiro positivo n que Pn e verdadeira para todo n Base Suponha que n 1 Neste caso devemos verificar se 1 111 2 Temos que 111 2 12 2 2 2 1 Portanto a propriedade Pn vale quando n 1 26 Inducao Matematica Exemplos Teorema Para todo inteiro positivo 1 2 n nn1 2 Demonstracao Seja Pn a propriedade 1 2 n nn1 2 Vamos provar por inducao no inteiro positivo n que Pn e verdadeira para todo n Base Suponha que n 1 Neste caso devemos verificar se 1 111 2 Temos que 111 2 12 2 2 2 1 Portanto a propriedade Pn vale quando n 1 26 Inducao Matematica Exemplos Teorema Para todo inteiro positivo 1 2 n nn1 2 Demonstracao Seja Pn a propriedade 1 2 n nn1 2 Vamos provar por inducao no inteiro positivo n que Pn e verdadeira para todo n Base Suponha que n 1 Neste caso devemos verificar se 1 111 2 Temos que 111 2 12 2 2 2 1 Portanto a propriedade Pn vale quando n 1 26 Inducao Matematica Exemplos Teorema Para todo inteiro positivo 1 2 n nn1 2 Continuacao da Demonstracao Passo Indutivo Seja k Z Vamos mostrar que SE 1 2 k kk1 2 ENTAO 1 2 k k1 k1k11 2 k1k2 2 Por prova direta suponha que Pk 1 2 k kk1 2 HI Devemos mostrar que Pk 1 1 2 k k1 k1k2 2 27 Indução Matemática Exemplos Teorema Para todo inteiro positivo 1 2 n nn12 Continuação da Demonstração Passo Indutivo Seja k Z Vamos mostrar que SE 1 2 k kk12 ENTÃO 1 2 k k1 k1k112 k1k22 Por prova direta suponha que Pk 1 2 k kk12 HI Devemos mostrar que Pk 1 1 2 k k1 k1k22 Oportunidade de usar a HI Usando a HI podemos substituir a expressão destacada Assim temos que 1 2 k k 1 kk 12 k 1 Inducao Matematica Exemplos Teorema Para todo inteiro positivo 1 2 n nn1 2 Continuacao da Demonstracao 1 2 k k 1 kk 1 2 k 1 kk 1 2k 1 2 k 1k 2 2 A ultima equacao mostra que Pk 1 e verdadeira sob a hipotese de que Pk e verdadeira Isso completa a prova por inducao 28 Somando os primeiros n inteiros ımpares positivos 1 1 1 3 4 1 3 5 9 1 3 5 7 16 1 3 5 7 9 25 Conjetura A soma dos n primeiros inteiros ımpares positivos e n2 O que e equivalente a dizer Conjetura 1 3 5 2n 1 n2 para todo inteiro n 1 29 Somando os primeiros n inteiros ımpares positivos 1 1 1 3 4 1 3 5 9 1 3 5 7 16 1 3 5 7 9 25 Conjetura A soma dos n primeiros inteiros ımpares positivos e n2 O que e equivalente a dizer Conjetura 1 3 5 2n 1 n2 para todo inteiro n 1 29 Somando os primeiros n inteiros ımpares positivos 1 1 1 3 4 1 3 5 9 1 3 5 7 16 1 3 5 7 9 25 Conjetura A soma dos n primeiros inteiros ımpares positivos e n2 O que e equivalente a dizer Conjetura 1 3 5 2n 1 n2 para todo inteiro n 1 29 Somando os primeiros n inteiros ımpares positivos Teorema 1 3 5 2n 1 n2 para todo inteiro n 1 Demonstracao Seja Pn 1 3 5 2n 1 n2 Vamos provar por inducao em n que Pn e verdadeira para todo inteiro n 1 Base Suponha que n 1 Neste caso devemos verificar que 1 12 Temos que 1 1 1 12 Portanto P1 e verdadeira 30 Somando os primeiros n inteiros ımpares positivos Teorema 1 3 5 2n 1 n2 para todo inteiro n 1 Demonstracao Seja Pn 1 3 5 2n 1 n2 Vamos provar por inducao em n que Pn e verdadeira para todo inteiro n 1 Base Suponha que n 1 Neste caso devemos verificar que 1 12 Temos que 1 1 1 12 Portanto P1 e verdadeira 30 Somando os primeiros n inteiros ımpares positivos Teorema 1 3 5 2n 1 n2 para todo inteiro n 1 Demonstracao Seja Pn 1 3 5 2n 1 n2 Vamos provar por inducao em n que Pn e verdadeira para todo inteiro n 1 Base Suponha que n 1 Neste caso devemos verificar que 1 12 Temos que 1 1 1 12 Portanto P1 e verdadeira 30 Somando os primeiros n inteiros ımpares positivos Teorema 1 3 5 2n 1 n2 para todo inteiro n 1 Continuacao da Demonstracao Passo da Inducao Seja k um inteiro positivo qualquer Vamos mostrar que Pk Pk 1 SE 1 3 5 2k 1 k2 ENTAO 1 3 5 2k 1 2k 1 1 k 12 Por prova direta suponha que 1 3 5 2k 1 k2 HI 31 Somando os primeiros n inteiros ımpares positivos Teorema 1 3 5 2n 1 n2 para todo inteiro n 1 Continuacao da Demonstracao Passo da Inducao Seja k um inteiro positivo qualquer Vamos mostrar que Pk Pk 1 SE 1 3 5 2k 1 k2 ENTAO 1 3 5 2k 1 2k 1 1 k 12 Por prova direta suponha que 1 3 5 2k 1 k2 HI Devemos mostrar que 1 3 5 2k 1 2k 1 k 12 31 Somando os primeiros n inteiros ímpares positivos Teorema 1 3 5 2n 1 n2 para todo inteiro n 1 Continuação da Demonstração Passo da Indução Seja k um inteiro positivo qualquer Vamos mostrar que Pk Pk 1 SE 1 3 5 2k 1 k2 ENTÃO 1 3 5 2k 1 2k 1 1 k 12 Por prova direta suponha que 1 3 5 2k 1 k2 HI Devemos mostrar que 1 3 5 2k 1 2k 1 k 12 Oportunidade de usar a HI Somando os primeiros n inteiros ímpares positivos Teorema 1 35 2n1 n² para todo inteiro n 1 Continuação da Demonstração Devemos mostrar que 1 3 5 2k1 2k 1 k 1² Oportunidade de usar a HI Somando os primeiros n inteiros ímpares positivos Teorema 1 35 2n1 n² para todo inteiro n 1 Continuação da Demonstração Devemos mostrar que 1 3 5 2k1 2k 1 k 1² Oportunidade de usar a HI Usando a HI podemos substituir a expressão destacada 1 3 5 2k 1 2k 1 1 3 2k1 2k 1 HI k² 2k 1 k² 2k 1 k 1² Somando os primeiros n inteiros ímpares positivos Teorema 1 35 2n1 n² para todo inteiro n 1 Continuação da Demonstração Devemos mostrar que 1 3 5 2k1 2k 1 k 1² Oportunidade de usar a HI Usando a HI podemos substituir a expressão destacada 1 3 5 2k 1 2k 1 1 3 2k1 2k 1 HI k² 2k 1 k² 2k 1 k 1² Isso mostra que Pk1 segue de Pk Isso completa a prova por indução Diretrizes para prova por inducao 33 Direrizes para o uso de Inducao Busque sempre seguir estes passos Expresse o enunciado a ser provado no formato para todo n b Pn Escreva Base e mostre que Pb e verdadeiro Escreva Passo indutivo Enuncie e identifique claramente a hipotese de inducao na forma Seja k um elemento qualquer do domınio com k b suponha que Pk vale Reforce o que precisa ser provado a partir da hipotese ou seja diga que precisa provar Pk 1 no contexto do teorema Prove que Pk 1 e verdadeira utilizando a hipotese de inducao Certifiquese de que sua prova vale para todo valor n b inclusive para valores pequenos de n como n b Identifique claramente a conclusao do passo de inducao dizendo por exemplo Isso completa o passo indutivo Por fim enuncie que Pn vale para todo inteiro n com n b 34 Direrizes para o uso de Inducao Busque sempre seguir estes passos Expresse o enunciado a ser provado no formato para todo n b Pn Escreva Base e mostre que Pb e verdadeiro Escreva Passo indutivo Enuncie e identifique claramente a hipotese de inducao na forma Seja k um elemento qualquer do domınio com k b suponha que Pk vale Reforce o que precisa ser provado a partir da hipotese ou seja diga que precisa provar Pk 1 no contexto do teorema Prove que Pk 1 e verdadeira utilizando a hipotese de inducao Certifiquese de que sua prova vale para todo valor n b inclusive para valores pequenos de n como n b Identifique claramente a conclusao do passo de inducao dizendo por exemplo Isso completa o passo indutivo Por fim enuncie que Pn vale para todo inteiro n com n b 34 Direrizes para o uso de Inducao Busque sempre seguir estes passos Expresse o enunciado a ser provado no formato para todo n b Pn Escreva Base e mostre que Pb e verdadeiro Escreva Passo indutivo Enuncie e identifique claramente a hipotese de inducao na forma Seja k um elemento qualquer do domınio com k b suponha que Pk vale Reforce o que precisa ser provado a partir da hipotese ou seja diga que precisa provar Pk 1 no contexto do teorema Prove que Pk 1 e verdadeira utilizando a hipotese de inducao Certifiquese de que sua prova vale para todo valor n b inclusive para valores pequenos de n como n b Identifique claramente a conclusao do passo de inducao dizendo por exemplo Isso completa o passo indutivo Por fim enuncie que Pn vale para todo inteiro n com n b 34 Direrizes para o uso de Inducao Busque sempre seguir estes passos Expresse o enunciado a ser provado no formato para todo n b Pn Escreva Base e mostre que Pb e verdadeiro Escreva Passo indutivo Enuncie e identifique claramente a hipotese de inducao na forma Seja k um elemento qualquer do domınio com k b suponha que Pk vale Reforce o que precisa ser provado a partir da hipotese ou seja diga que precisa provar Pk 1 no contexto do teorema Prove que Pk 1 e verdadeira utilizando a hipotese de inducao Certifiquese de que sua prova vale para todo valor n b inclusive para valores pequenos de n como n b Identifique claramente a conclusao do passo de inducao dizendo por exemplo Isso completa o passo indutivo Por fim enuncie que Pn vale para todo inteiro n com n b 34 Direrizes para o uso de Inducao Busque sempre seguir estes passos Expresse o enunciado a ser provado no formato para todo n b Pn Escreva Base e mostre que Pb e verdadeiro Escreva Passo indutivo Enuncie e identifique claramente a hipotese de inducao na forma Seja k um elemento qualquer do domınio com k b suponha que Pk vale Reforce o que precisa ser provado a partir da hipotese ou seja diga que precisa provar Pk 1 no contexto do teorema Prove que Pk 1 e verdadeira utilizando a hipotese de inducao Certifiquese de que sua prova vale para todo valor n b inclusive para valores pequenos de n como n b Identifique claramente a conclusao do passo de inducao dizendo por exemplo Isso completa o passo indutivo Por fim enuncie que Pn vale para todo inteiro n com n b 34 Direrizes para o uso de Inducao Busque sempre seguir estes passos Expresse o enunciado a ser provado no formato para todo n b Pn Escreva Base e mostre que Pb e verdadeiro Escreva Passo indutivo Enuncie e identifique claramente a hipotese de inducao na forma Seja k um elemento qualquer do domınio com k b suponha que Pk vale Reforce o que precisa ser provado a partir da hipotese ou seja diga que precisa provar Pk 1 no contexto do teorema Prove que Pk 1 e verdadeira utilizando a hipotese de inducao Certifiquese de que sua prova vale para todo valor n b inclusive para valores pequenos de n como n b Identifique claramente a conclusao do passo de inducao dizendo por exemplo Isso completa o passo indutivo Por fim enuncie que Pn vale para todo inteiro n com n b 34 Observacoes A tecnica de Inducao Matematica e tambem chamada de Primeiro Princıpio de Inducao e Inducao Fraca em outras fontes O livro tem muitos exemplos de provas por inducao A leitura destes exemplos favorecera a compreensao dos conceitos 35 FIM