Principio da Inducao Forte - Matematica Discreta UFC

Princıpio da Inducao Forte QXD0008 Matematica Discreta Prof Lucas Ismaily ismailybfufcbr Universidade Federal do Ceara 1º semestre2024 Topicos desta aula Nesta apresentacao Princıpio da Inducao Forte Strong Induction ou Inducao Completa Exemplos de Aplicacao prova do Algoritmo da Divicao Prova do Teorema Fundamental da Aritmetica etc Exemplos de erros comuns em provas por inducao matematica 2 Referˆencias para esta aula Secoes 52Strong Induction and WellOrdering do livro Discrete Mathematics and Its Applications Author Kenneth H Rosen Seventh Edition English version Secao 42 do livro Matematica Discreta e suas Aplicacoes Autor Kenneth H Rosen Sexta Edicao 3 Introdução Motivacao Anteriormente estudamos o Princıpio da Inducao Matematica Princıpio da Inducao Matematica Seja Pn uma proposicao sobre um numero natural n Se 1 P0 e verdadeiro e 2 k N Pk Pk 1 e verdadeiro entao n N Pn e verdadeiro Em diferentes momentos pode ser conveniente trabalhar com outras formulacoes do Princıpio da Inducao Matematica Uma formulacao especialmente importante para Computacao e o Princıpio da Inducao Forte 5 Princıpio da Inducao Forte Princıpio da Inducao Forte Para todo numero natural n seja Pn uma proposicao Se 1 P0 e verdadeiro e 2 k N P0 P1 Pk Pk 1 e verdadeiro entao n N Pn e verdadeiro Escrito como regra de inferˆencia P0 kP0 P1 Pk Pk 1 nPn 6 Princıpio da Inducao Forte Princıpio da Inducao Forte Para todo numero natural n seja Pn uma proposicao Se 1 P0 e verdadeiro e 2 k N P0 P1 Pk Pk 1 e verdadeiro entao n N Pn e verdadeiro Escrito como regra de inferˆencia P0 kP0 P1 Pk Pk 1 nPn 6 Inducao Forte Observacoes Pelo Princıpio da Inducao Forte a fim de provar que uma funcao proposicional Pn e verdadeira para todo natural n devemos provar dois casos 1 Caso Base mostrar que a proposicao P0 e verdadeira 2 Passo Indutivo mostrar que a seguinte afirmacao condicional e verdadeira para todo natural k P0 P1 Pk Pk 1 Note que na Inducao Forte a Hipotese de Inducao HI e a suposicao de que Pj e verdadeira para todo j 0 1 2 k Ou seja a HI consiste em todas as k afirmacoes P0 P1 Pk Logo podemos usar qualquer uma dessas k afirmacoes ou qualquer quantidade delas para provar que Pk 1 e verdadeira 7 Inducao Forte Observacoes 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 Solucao A Inducao Forte tambem permite provar propriedades sobre elementos do conjunto b b 1 b 2 pois este conjunto respeita o princıpio da boa ordenacao Princıpio da Inducao Forte Para provar que uma propriedade Pn e verdadeira para todo inteiro n b onde b Z Mostramos que Pb e verdadeira Caso Base e No passo indutivo mostramos que o condicional Pb Pb 1 Pk Pk 1 e verdadeiro para todo k b Note que b pode ser negativo zero ou positivo 8 Inducao Forte Observacoes 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 Solucao A Inducao Forte tambem permite provar propriedades sobre elementos do conjunto b b 1 b 2 pois este conjunto respeita o princıpio da boa ordenacao Princıpio da Inducao Forte Para provar que uma propriedade Pn e verdadeira para todo inteiro n b onde b Z Mostramos que Pb e verdadeira Caso Base e No passo indutivo mostramos que o condicional Pb Pb 1 Pk Pk 1 e verdadeiro para todo k b Note que b pode ser negativo zero ou positivo 8 Exemplo de Aplicacao do Princıpio da Inducao Forte Jogo das cartas 9 Jogo das cartas Considere um jogo em que dois jogadores alternamse para remover qualquer numero positivo de cartas que eles pegam a partir de dois montes de cartas de baralho O jogador que tirar a ultima carta ganha o jogo Se as duas pilhas tiverem o mesmo numero de cartas inicialmente podemos garantir que algum dos jogadores sempre ganha o jogo 10 Jogo das cartas Teorema Se duas pilhas de cartas contˆem o mesmo numero de cartas inicialmente entao o segundo jogador do Jogo das Cartas sempre ganha o jogo Demonstracao Seja n o numero de cartas em cada pilha Vamos usar a inducao forte para demonstrar Pn a proposicao que afirma que o segundo jogador vence quando houver inicialmente n cartas em cada pilha de cartas Caso Base n 1 Neste caso o primeiro jogador tem apenas uma escolha remover uma carta de uma pilha deixando uma pilha com apenas uma carta que o segundo jogador pode retirar para vencer o jogo Isso completa o caso base 11 Jogo das cartas Continuacao da Demonstracao Hipotese de Inducao Para todo j tal que 1 j k suponha que o segundo jogador sempre ganha quando houver j cartas em cada uma das pilhas no ınicio do jogo Passo Indutivo Precisamos mostrar que Pk 1 e verdadeira ou seja que o segundo jogador vence quando ha inicialmente k 1 cartas em cada pilha considerando a HI de que Pj e verdadeira para j 1 2 k Entao suponha que haja k 1 cartas em cada uma das pilhas no inıcio do jogo Dividimos o restante da prova em dois casos Na primeira rodada ou o primeiro jogador remove todas as k 1 cartas de uma das pilhas ou ele remove somente r cartas onde 1 r k Caso 1 O primeiro jogador remove todas as k 1 cartas de umas das pilhas na primeira jogada Neste caso o segundo jogador vence removendo todas as cartas restantes 12 Jogo das cartas Continuacao da Demonstracao Continuacao do Passo Indutivo Caso 2 O primeiro jogador remove r cartas 1 r k de umas das pilhas na primeira jogada Neste caso o primeiro jogador deixa k 1 r cartas em uma das pilhas Entao o segundo jogador remove tambem r cartas da outra pilha que estava intacta Ao fazer isso o segundo jogador cria a situacao em que ha duas pilhas cada uma com k 1 r cartas Como 1 k 1 r k o segundo jogador sempre vence pela hipotese de inducao Isso completa a prova do passo indutivo 13 Exemplo de Aplicacao do Princıpio da Inducao Forte Prova do Teorema Fundamental da Aritmetica 14 Prova do Teorema Fundamental da Aritmetica Teorema Fundamental da Aritmetica TFA Todo inteiro n 1 pode ser escrito de maneira unica como um primo ou como o produto de dois ou mais numeros primos escritos em ordem crescente Este e um enunciado de unicidade Logo a prova deste teorema e dividida em duas partes Existˆencia todo inteiro n 1 pode ser escrito como um primo ou como o produto de dois ou mais numeros primos Unicidade suponha que p1 p2 pk e q1 q2 qm sao numeros primos p1 p2 pk q1 q2 qm e p1p2 pk q1q2 qm Vamos provar somente a existˆencia A unicidade fica como exercıcio 15 Prova de Existˆencia do TFA Teorema 1 Todo inteiro n 1 pode ser escrito como um primo ou como o produto de dois ou mais numeros primos Demonstracao Seja Pn a proposicao de que n pode ser escrito como um primo ou como o produto de dois ou mais primos Vamos provar por inducao forte em n que Pn vale para todo inteiro n 1 Caso Base n 2 Note que P2 e verdadeiro porque 2 e um numero primo e pode ser escrito como ele mesmo Isso conclui o caso base 16 Prova de Existˆencia do TFA Teorema 1 Todo inteiro n 1 pode ser escrito como um primo ou como o produto de dois ou mais numeros primos Demonstracao Seja Pn a proposicao de que n pode ser escrito como um primo ou como o produto de dois ou mais primos Vamos provar por inducao forte em n que Pn vale para todo inteiro n 1 Caso Base n 2 Note que P2 e verdadeiro porque 2 e um numero primo e pode ser escrito como ele mesmo Isso conclui o caso base 16 Prova de Existˆencia do TFA Teorema 1 Todo inteiro n 1 pode ser escrito como um primo ou como o produto de dois ou mais numeros primos Demonstracao Seja Pn a proposicao de que n pode ser escrito como um primo ou como o produto de dois ou mais primos Vamos provar por inducao forte em n que Pn vale para todo inteiro n 1 Caso Base n 2 Note que P2 e verdadeiro porque 2 e um numero primo e pode ser escrito como ele mesmo Isso conclui o caso base 16 Prova de Existˆencia do TFA Continuacao da Demonstracao Passo indutivo Seja k 2 um inteiro arbitrario Vamos provar que P2 P3 Pk Pk 1 Hipotese de Inducao Suponha que Pj e verdadeira para todos os inteiros j com 2 j k Ou seja para todo j 2 3 k j pode ser escrito como um primo ou como o produto de dois ou mais numeros primos A fim de completar o passo indutivo vamos mostrar que k 1 pode ser escrito como um primo ou como o produto de dois ou mais numeros primos Existem dois casos a considerar Caso 1 k 1 e primo Caso 2 k 1 e composto 17 Prova de Existˆencia do TFA Continuacao da Demonstracao Passo indutivo Seja k 2 um inteiro arbitrario Vamos provar que P2 P3 Pk Pk 1 Hipotese de Inducao Suponha que Pj e verdadeira para todos os inteiros j com 2 j k Ou seja para todo j 2 3 k j pode ser escrito como um primo ou como o produto de dois ou mais numeros primos A fim de completar o passo indutivo vamos mostrar que k 1 pode ser escrito como um primo ou como o produto de dois ou mais numeros primos Existem dois casos a considerar Caso 1 k 1 e primo Caso 2 k 1 e composto 17 Prova de Existˆencia do TFA Continuacao da Demonstracao Passo indutivo Seja k 2 um inteiro arbitrario Vamos provar que P2 P3 Pk Pk 1 Hipotese de Inducao Suponha que Pj e verdadeira para todos os inteiros j com 2 j k Ou seja para todo j 2 3 k j pode ser escrito como um primo ou como o produto de dois ou mais numeros primos A fim de completar o passo indutivo vamos mostrar que k 1 pode ser escrito como um primo ou como o produto de dois ou mais numeros primos Existem dois casos a considerar Caso 1 k 1 e primo Caso 2 k 1 e composto 17 Prova de Existˆencia do TFA Continuacao da Demonstracao Passo indutivo Seja k 2 um inteiro arbitrario Vamos provar que P2 P3 Pk Pk 1 Hipotese de Inducao Suponha que Pj e verdadeira para todos os inteiros j com 2 j k Ou seja para todo j 2 3 k j pode ser escrito como um primo ou como o produto de dois ou mais numeros primos A fim de completar o passo indutivo vamos mostrar que k 1 pode ser escrito como um primo ou como o produto de dois ou mais numeros primos Existem dois casos a considerar Caso 1 k 1 e primo Caso 2 k 1 e composto 17 Prova de Existˆencia do TFA Continuacao da Demonstracao Caso 1 k 1 e primo Neste caso k 1 pode ser escrito como ele mesmo ja que e primo Caso 2 k 1 e composto Neste caso k 1 pode ser escrito como o produto de dois inteiros positivos a e b tais que 2 a b k 1 Como 2 a k e 2 b k podemos aplicar a hipotese de inducao a fim de escrever a e b como um primo ou como o produto de dois ou mais primos Assim se k 1 e composto podemos escrevˆelo como o produto de dois ou mais primos que sao os primos contidos na fatoracao de a e na fatoracao de b Isso conclui a prova do passo indutivo Como tanto o caso base quanto o passo indutivo foram provados o resultado segue 18 Prova de Existˆencia do TFA Continuacao da Demonstracao Caso 1 k 1 e primo Neste caso k 1 pode ser escrito como ele mesmo ja que e primo Caso 2 k 1 e composto Neste caso k 1 pode ser escrito como o produto de dois inteiros positivos a e b tais que 2 a b k 1 Como 2 a k e 2 b k podemos aplicar a hipotese de inducao a fim de escrever a e b como um primo ou como o produto de dois ou mais primos Assim se k 1 e composto podemos escrevˆelo como o produto de dois ou mais primos que sao os primos contidos na fatoracao de a e na fatoracao de b Isso conclui a prova do passo indutivo Como tanto o caso base quanto o passo indutivo foram provados o resultado segue 18 Prova de Existˆencia do TFA Continuacao da Demonstracao Caso 1 k 1 e primo Neste caso k 1 pode ser escrito como ele mesmo ja que e primo Caso 2 k 1 e composto Neste caso k 1 pode ser escrito como o produto de dois inteiros positivos a e b tais que 2 a b k 1 Como 2 a k e 2 b k podemos aplicar a hipotese de inducao a fim de escrever a e b como um primo ou como o produto de dois ou mais primos Assim se k 1 e composto podemos escrevˆelo como o produto de dois ou mais primos que sao os primos contidos na fatoracao de a e na fatoracao de b Isso conclui a prova do passo indutivo Como tanto o caso base quanto o passo indutivo foram provados o resultado segue 18 Prova de Existˆencia do TFA Continuacao da Demonstracao Caso 1 k 1 e primo Neste caso k 1 pode ser escrito como ele mesmo ja que e primo Caso 2 k 1 e composto Neste caso k 1 pode ser escrito como o produto de dois inteiros positivos a e b tais que 2 a b k 1 Como 2 a k e 2 b k podemos aplicar a hipotese de inducao a fim de escrever a e b como um primo ou como o produto de dois ou mais primos Assim se k 1 e composto podemos escrevˆelo como o produto de dois ou mais primos que sao os primos contidos na fatoracao de a e na fatoracao de b Isso conclui a prova do passo indutivo Como tanto o caso base quanto o passo indutivo foram provados o resultado segue 18 Prova de Existˆencia do TFA Continuacao da Demonstracao Caso 1 k 1 e primo Neste caso k 1 pode ser escrito como ele mesmo ja que e primo Caso 2 k 1 e composto Neste caso k 1 pode ser escrito como o produto de dois inteiros positivos a e b tais que 2 a b k 1 Como 2 a k e 2 b k podemos aplicar a hipotese de inducao a fim de escrever a e b como um primo ou como o produto de dois ou mais primos Assim se k 1 e composto podemos escrevˆelo como o produto de dois ou mais primos que sao os primos contidos na fatoracao de a e na fatoracao de b Isso conclui a prova do passo indutivo Como tanto o caso base quanto o passo indutivo foram provados o resultado segue 18 Exemplo de Aplicacao do Princıpio da Inducao Forte Prova do Teorema do Algoritmo da Divisao 19 Prova do Teorema do Algoritmo da Divisao Para inteiros nao negativos Teorema Algoritmo da Divisao Sejam n m N Se m 0 entao existem numeros naturais q e r tais que n qmr e 0 r m Demonstracao Seja m 0 um natural qualquer Seja Pn a proposicao de que existem naturais q e r tais que n qm r e 0 r m Vamos provar por inducao forte em n que Pn e verdadeira para todo n N Caso Base n 0 Note que fazendo q r 0 obtemos que n 0 0 m 0 qm r e que 0 r m Portanto P0 e verdadeira 20 Prova do Teorema do Algoritmo da Divisao Para inteiros nao negativos Teorema Algoritmo da Divisao Sejam n m N Se m 0 entao existem numeros naturais q e r tais que n qmr e 0 r m Demonstracao Seja m 0 um natural qualquer Seja Pn a proposicao de que existem naturais q e r tais que n qm r e 0 r m Vamos provar por inducao forte em n que Pn e verdadeira para todo n N Caso Base n 0 Note que fazendo q r 0 obtemos que n 0 0 m 0 qm r e que 0 r m Portanto P0 e verdadeira 20 Prova do Teorema do Algoritmo da Divisao Para inteiros nao negativos Teorema Algoritmo da Divisao Sejam n m N Se m 0 entao existem numeros naturais q e r tais que n qmr e 0 r m Demonstracao Seja m 0 um natural qualquer Seja Pn a proposicao de que existem naturais q e r tais que n qm r e 0 r m Vamos provar por inducao forte em n que Pn e verdadeira para todo n N Caso Base n 0 Note que fazendo q r 0 obtemos que n 0 0 m 0 qm r e que 0 r m Portanto P0 e verdadeira 20 Prova do Teorema do Algoritmo da Divisao Para inteiros nao negativos Teorema Algoritmo da Divisao Sejam n m N Se m 0 entao existem numeros naturais q e r tais que n qmr e 0 r m Demonstracao Seja m 0 um natural qualquer Seja Pn a proposicao de que existem naturais q e r tais que n qm r e 0 r m Vamos provar por inducao forte em n que Pn e verdadeira para todo n N Caso Base n 0 Note que fazendo q r 0 obtemos que n 0 0 m 0 qm r e que 0 r m Portanto P0 e verdadeira 20 Prova do Teorema do Algoritmo da Divisao Pn existem naturais q e r tais que n qm r e 0 r m Continuacao da Demonstracao Passo Indutivo Seja k 1 um natural qualquer Vamos mostrar que P0 P1 Pk 1 Pk Hipotese de inducao Suponha que para todo numero natural j com 0 j k 1 existem numeros naturais q e r tais que j qm r e 0 r m A fim de completar o passo indutivo vamos mostrar que existem numeros naturais q e r tais que k qm r e 0 r m Existem dois casos a considerar k m e k m 21 Prova do Teorema do Algoritmo da Divisao Pn existem naturais q e r tais que n qm r e 0 r m Continuacao da Demonstracao Passo Indutivo Seja k 1 um natural qualquer Vamos mostrar que P0 P1 Pk 1 Pk Hipotese de inducao Suponha que para todo numero natural j com 0 j k 1 existem numeros naturais q e r tais que j qm r e 0 r m A fim de completar o passo indutivo vamos mostrar que existem numeros naturais q e r tais que k qm r e 0 r m Existem dois casos a considerar k m e k m 21 Prova do Teorema do Algoritmo da Divisao Pn existem naturais q e r tais que n qm r e 0 r m Continuacao da Demonstracao Passo Indutivo Seja k 1 um natural qualquer Vamos mostrar que P0 P1 Pk 1 Pk Hipotese de inducao Suponha que para todo numero natural j com 0 j k 1 existem numeros naturais q e r tais que j qm r e 0 r m A fim de completar o passo indutivo vamos mostrar que existem numeros naturais q e r tais que k qm r e 0 r m Existem dois casos a considerar k m e k m 21 Prova do Teorema do Algoritmo da Divisao Pn existem naturais q e r tais que n qm r e 0 r m Continuacao da Demonstracao Passo Indutivo Seja k 1 um natural qualquer Vamos mostrar que P0 P1 Pk 1 Pk Hipotese de inducao Suponha que para todo numero natural j com 0 j k 1 existem numeros naturais q e r tais que j qm r e 0 r m A fim de completar o passo indutivo vamos mostrar que existem numeros naturais q e r tais que k qm r e 0 r m Existem dois casos a considerar k m e k m 21 Prova do Teorema do Algoritmo da Divisao Lembrete Agora queremos provar que Pk e verdadeira Pk existem naturais q e r tais que k qm r e 0 r m Continuacao da Demonstracao Caso 1 k m Neste caso seja q 0 e r k Entao claramente temos que k qm r e 0 r m Portanto Pk e verdadeira Caso 2 k m Seja t k m Note que t k e note que como k m t e um numero natural Entao podemos aplicar a Hipotese de Inducao em t Pela HI existem q e r tais que t qm r e 0 r m Entao k m qm r Isso implica k qm r m q 1m r Fazendo q q 1 e r r concluımos que k qm r e 0 r m Portanto Pk e verdadeira Isso conclui o passo indutivo 22 Prova do Teorema do Algoritmo da Divisao Lembrete Agora queremos provar que Pk e verdadeira Pk existem naturais q e r tais que k qm r e 0 r m Continuacao da Demonstracao Caso 1 k m Neste caso seja q 0 e r k Entao claramente temos que k qm r e 0 r m Portanto Pk e verdadeira Caso 2 k m Seja t k m Note que t k e note que como k m t e um numero natural Entao podemos aplicar a Hipotese de Inducao em t Pela HI existem q e r tais que t qm r e 0 r m Entao k m qm r Isso implica k qm r m q 1m r Fazendo q q 1 e r r concluımos que k qm r e 0 r m Portanto Pk e verdadeira Isso conclui o passo indutivo 22 Prova do Teorema do Algoritmo da Divisao Lembrete Agora queremos provar que Pk e verdadeira Pk existem naturais q e r tais que k qm r e 0 r m Continuacao da Demonstracao Caso 1 k m Neste caso seja q 0 e r k Entao claramente temos que k qm r e 0 r m Portanto Pk e verdadeira Caso 2 k m Seja t k m Note que t k e note que como k m t e um numero natural Entao podemos aplicar a Hipotese de Inducao em t Pela HI existem q e r tais que t qm r e 0 r m Entao k m qm r Isso implica k qm r m q 1m r Fazendo q q 1 e r r concluımos que k qm r e 0 r m Portanto Pk e verdadeira Isso conclui o passo indutivo 22 Prova do Teorema do Algoritmo da Divisao Lembrete Agora queremos provar que Pk e verdadeira Pk existem naturais q e r tais que k qm r e 0 r m Continuacao da Demonstracao Caso 1 k m Neste caso seja q 0 e r k Entao claramente temos que k qm r e 0 r m Portanto Pk e verdadeira Caso 2 k m Seja t k m Note que t k e note que como k m t e um numero natural Entao podemos aplicar a Hipotese de Inducao em t Pela HI existem q e r tais que t qm r e 0 r m Entao k m qm r Isso implica k qm r m q 1m r Fazendo q q 1 e r r concluımos que k qm r e 0 r m Portanto Pk e verdadeira Isso conclui o passo indutivo 22 Prova do Teorema do Algoritmo da Divisao Lembrete Agora queremos provar que Pk e verdadeira Pk existem naturais q e r tais que k qm r e 0 r m Continuacao da Demonstracao Caso 1 k m Neste caso seja q 0 e r k Entao claramente temos que k qm r e 0 r m Portanto Pk e verdadeira Caso 2 k m Seja t k m Note que t k e note que como k m t e um numero natural Entao podemos aplicar a Hipotese de Inducao em t Pela HI existem q e r tais que t qm r e 0 r m Entao k m qm r Isso implica k qm r m q 1m r Fazendo q q 1 e r r concluımos que k qm r e 0 r m Portanto Pk e verdadeira Isso conclui o passo indutivo 22 Uma segunda versao da Inducao Forte 23 Princıpio da Inducao Forte Versao 2 Princıpio da Inducao Forte Versao 2 Seja Pn uma proposicao sobre um numero natural n Sejam tambem j e b inteiros positivos Se 1 Pb Pb 1 Pb j sao verdadeiras e 2 Pb Pb 1 Pk Pk 1 e verdadeira para todo inteiro k b j entao n N Pn e verdadeiro 24 Exemplo Teorema Qualquer valor de postagem igual ou maior que 12 reais pode ser formado usando exclusivamente selos de 4 e de 5 reais Demonstracao Seja Pn uma postagem de n reais pode ser formada usando exclusivamente selos de 4 e de 5 reais Vamos provar por inducao forte no numero de selos que Pn e verdadeira para todo n 12 Caso Base Seja n 12 13 14 15 Entao para cada n vale 12 reais pode ser formado com 3 selos de 4 reais 13 reais pode ser formado com 2 selos de 4 reais e 1 selo de 5 reais 14 reais pode ser formado com 1 selo de 4 reais e 2 selos de 5 reais 15 reais pode ser formado com 3 selos de 5 reais Isso prova que P12 P13 P14 P15 sao verdadeiras Isso completa o caso base 25 Exemplo Teorema Qualquer valor de postagem igual ou maior que 12 reais pode ser formado usando exclusivamente selos de 4 e de 5 reais Demonstracao Seja Pn uma postagem de n reais pode ser formada usando exclusivamente selos de 4 e de 5 reais Vamos provar por inducao forte no numero de selos que Pn e verdadeira para todo n 12 Caso Base Seja n 12 13 14 15 Entao para cada n vale 12 reais pode ser formado com 3 selos de 4 reais 13 reais pode ser formado com 2 selos de 4 reais e 1 selo de 5 reais 14 reais pode ser formado com 1 selo de 4 reais e 2 selos de 5 reais 15 reais pode ser formado com 3 selos de 5 reais Isso prova que P12 P13 P14 P15 sao verdadeiras Isso completa o caso base 25 Exemplo Teorema Qualquer valor de postagem igual ou maior que 12 reais pode ser formado usando exclusivamente selos de 4 e de 5 reais Demonstracao Seja Pn uma postagem de n reais pode ser formada usando exclusivamente selos de 4 e de 5 reais Vamos provar por inducao forte no numero de selos que Pn e verdadeira para todo n 12 Caso Base Seja n 12 13 14 15 Entao para cada n vale 12 reais pode ser formado com 3 selos de 4 reais 13 reais pode ser formado com 2 selos de 4 reais e 1 selo de 5 reais 14 reais pode ser formado com 1 selo de 4 reais e 2 selos de 5 reais 15 reais pode ser formado com 3 selos de 5 reais Isso prova que P12 P13 P14 P15 sao verdadeiras Isso completa o caso base 25 Exemplo Teorema Qualquer valor de postagem igual ou maior que 12 reais pode ser formado usando exclusivamente selos de 4 e de 5 reais Demonstracao Seja Pn uma postagem de n reais pode ser formada usando exclusivamente selos de 4 e de 5 reais Vamos provar por inducao forte no numero de selos que Pn e verdadeira para todo n 12 Caso Base Seja n 12 13 14 15 Entao para cada n vale 12 reais pode ser formado com 3 selos de 4 reais 13 reais pode ser formado com 2 selos de 4 reais e 1 selo de 5 reais 14 reais pode ser formado com 1 selo de 4 reais e 2 selos de 5 reais 15 reais pode ser formado com 3 selos de 5 reais Isso prova que P12 P13 P14 P15 sao verdadeiras Isso completa o caso base 25 Exemplo Teorema Qualquer valor de postagem igual ou maior que 12 reais pode ser formado usando exclusivamente selos de 4 e de 5 reais Demonstracao Seja Pn uma postagem de n reais pode ser formada usando exclusivamente selos de 4 e de 5 reais Vamos provar por inducao forte no numero de selos que Pn e verdadeira para todo n 12 Caso Base Seja n 12 13 14 15 Entao para cada n vale 12 reais pode ser formado com 3 selos de 4 reais 13 reais pode ser formado com 2 selos de 4 reais e 1 selo de 5 reais 14 reais pode ser formado com 1 selo de 4 reais e 2 selos de 5 reais 15 reais pode ser formado com 3 selos de 5 reais Isso prova que P12 P13 P14 P15 sao verdadeiras Isso completa o caso base 25 Exemplo Continuacao da Demonstracao Passo Indutivo Seja k um inteiro tal que k 15 Hipotese de Inducao Suponha que qualquer valor de postagem j com 12 j k pode ser formado usando selos de 4 e de 5 reais A fim de provar o passo indutivo vamos mostrar que uma postagem cujo valor e k 1 reais pode ser formada usando apenas selos de 4 e de 5 reais Pela HI uma postagem de k 3 reais pode ser formada usando apenas selos de 4 e de 5 reais pois 12 k 3 k Podemos formar uma postagem de k 1 reais usando os selos de postagem de k 3 reais mais um selo de 4 reais pois k 1 k 3 4 Assim provamos que se a HI e verdadeira entao Pk 1 tambem e verdadeira Ou seja e possıvel formar uma postagem de k 1 reais usando apenas selos de 4 e de 5 reais Isso completa a prova do passo indutivo 26 Exemplo Continuacao da Demonstracao Passo Indutivo Seja k um inteiro tal que k 15 Hipotese de Inducao Suponha que qualquer valor de postagem j com 12 j k pode ser formado usando selos de 4 e de 5 reais A fim de provar o passo indutivo vamos mostrar que uma postagem cujo valor e k 1 reais pode ser formada usando apenas selos de 4 e de 5 reais Pela HI uma postagem de k 3 reais pode ser formada usando apenas selos de 4 e de 5 reais pois 12 k 3 k Podemos formar uma postagem de k 1 reais usando os selos de postagem de k 3 reais mais um selo de 4 reais pois k 1 k 3 4 Assim provamos que se a HI e verdadeira entao Pk 1 tambem e verdadeira Ou seja e possıvel formar uma postagem de k 1 reais usando apenas selos de 4 e de 5 reais Isso completa a prova do passo indutivo 26 Exemplo Continuacao da Demonstracao Passo Indutivo Seja k um inteiro tal que k 15 Hipotese de Inducao Suponha que qualquer valor de postagem j com 12 j k pode ser formado usando selos de 4 e de 5 reais A fim de provar o passo indutivo vamos mostrar que uma postagem cujo valor e k 1 reais pode ser formada usando apenas selos de 4 e de 5 reais Pela HI uma postagem de k 3 reais pode ser formada usando apenas selos de 4 e de 5 reais pois 12 k 3 k Podemos formar uma postagem de k 1 reais usando os selos de postagem de k 3 reais mais um selo de 4 reais pois k 1 k 3 4 Assim provamos que se a HI e verdadeira entao Pk 1 tambem e verdadeira Ou seja e possıvel formar uma postagem de k 1 reais usando apenas selos de 4 e de 5 reais Isso completa a prova do passo indutivo 26 Exemplo Continuacao da Demonstracao Passo Indutivo Seja k um inteiro tal que k 15 Hipotese de Inducao Suponha que qualquer valor de postagem j com 12 j k pode ser formado usando selos de 4 e de 5 reais A fim de provar o passo indutivo vamos mostrar que uma postagem cujo valor e k 1 reais pode ser formada usando apenas selos de 4 e de 5 reais Pela HI uma postagem de k 3 reais pode ser formada usando apenas selos de 4 e de 5 reais pois 12 k 3 k Podemos formar uma postagem de k 1 reais usando os selos de postagem de k 3 reais mais um selo de 4 reais pois k 1 k 3 4 Assim provamos que se a HI e verdadeira entao Pk 1 tambem e verdadeira Ou seja e possıvel formar uma postagem de k 1 reais usando apenas selos de 4 e de 5 reais Isso completa a prova do passo indutivo 26 Exemplo Continuacao da Demonstracao Passo Indutivo Seja k um inteiro tal que k 15 Hipotese de Inducao Suponha que qualquer valor de postagem j com 12 j k pode ser formado usando selos de 4 e de 5 reais A fim de provar o passo indutivo vamos mostrar que uma postagem cujo valor e k 1 reais pode ser formada usando apenas selos de 4 e de 5 reais Pela HI uma postagem de k 3 reais pode ser formada usando apenas selos de 4 e de 5 reais pois 12 k 3 k Podemos formar uma postagem de k 1 reais usando os selos de postagem de k 3 reais mais um selo de 4 reais pois k 1 k 3 4 Assim provamos que se a HI e verdadeira entao Pk 1 tambem e verdadeira Ou seja e possıvel formar uma postagem de k 1 reais usando apenas selos de 4 e de 5 reais Isso completa a prova do passo indutivo 26 Exemplo Continuacao da Demonstracao Passo Indutivo Seja k um inteiro tal que k 15 Hipotese de Inducao Suponha que qualquer valor de postagem j com 12 j k pode ser formado usando selos de 4 e de 5 reais A fim de provar o passo indutivo vamos mostrar que uma postagem cujo valor e k 1 reais pode ser formada usando apenas selos de 4 e de 5 reais Pela HI uma postagem de k 3 reais pode ser formada usando apenas selos de 4 e de 5 reais pois 12 k 3 k Podemos formar uma postagem de k 1 reais usando os selos de postagem de k 3 reais mais um selo de 4 reais pois k 1 k 3 4 Assim provamos que se a HI e verdadeira entao Pk 1 tambem e verdadeira Ou seja e possıvel formar uma postagem de k 1 reais usando apenas selos de 4 e de 5 reais Isso completa a prova do passo indutivo 26 Exercıcio para casa 1 Exercıcio Nos slides anteriores provamos o teorema abaixo usando Inducao Forte Porem esse resultado pode ser provado usando apenas a Inducao Fraca Prove o teorema abaixo usando Inducao Fraca ou seja o Princıpio da Inducao Matematica PIM visto nas aulas anteriores Teorema Qualquer valor de postagem igual ou maior que 12 reais pode ser formado usando exclusivamente selos de 4 e de 5 reais 27 Exercício para casa 2 Exercício Prove que para todo natural n a fórmula fechada fn 15 1 52n 1 52n é uma solução para a relação de recorrência fn 0 se n 0 1 se n 1 fn1 fn2 se n 2 Dica Use indução forte Inducao Forte Inducao Fraca 29 Inducao Forte Inducao Fraca Algumas vezes a inducao forte e mais facil de usar Pode ser provado que a inducao forte e a inducao fraca sao equivalentes Qualquer prova por inducao fraca pode ser facilmente escrita como uma prova por inducao forte por quˆe Qualquer prova por inducao forte pode ser convertida em uma prova por inducao fraca mas nao e tao obvio A validade de ambos os princıpios de inducao segue do princıpio do bom ordenamento De fato os 3 princıpios sao equivalentes Ou seja qualquer prova que utilize um destes princıpios pode ser reescrita utilizando qualquer um dos outros dois Dependendo do caso a ser provado pode ser mais conveniente usar um ou outro princıpio 30 Inducao Forte Inducao Fraca Algumas vezes a inducao forte e mais facil de usar Pode ser provado que a inducao forte e a inducao fraca sao equivalentes Qualquer prova por inducao fraca pode ser facilmente escrita como uma prova por inducao forte por quˆe Qualquer prova por inducao forte pode ser convertida em uma prova por inducao fraca mas nao e tao obvio A validade de ambos os princıpios de inducao segue do princıpio do bom ordenamento De fato os 3 princıpios sao equivalentes Ou seja qualquer prova que utilize um destes princıpios pode ser reescrita utilizando qualquer um dos outros dois Dependendo do caso a ser provado pode ser mais conveniente usar um ou outro princıpio 30 Erros em provas por inducao matematica 31 Enunciado verdadeiro prova incorreta Teorema Para todo inteiro n 1 n e par Suposta demonstracao Prova por inducao forte em n Seja n 2 3 um inteiro qualquer e Pn a proposicao que afirma que n e par Caso base Quando n 2 2 2 1 2 Como 2 e par P2 e verdadeira Hipotese de inducao Para n 2 suponha que Pi e verdadeira para todo i 2 3 n 1 ou seja i e par Passo Indutivo Queremos provar que Pn 1 e verdadeiro ou seja que n 1 e par Pela definicao recursiva do fatorial n 1 n 1 n Pela HI sabemos que n e par Por um teorema conhecido sabemos que o produto de dois inteiros resulta em um numero par se pelo menos um dos dois inteiros for par Portanto n 1 e par e portanto Pn 1 e verdadeiro Como o caso base e o passo indutivo foram provados concluımos que n e par para todo inteiro n 1 32 Enunciado falso prova incorreta Teorema Para todo inteiro n nao negativo 5n 0 Suposta demonstracao Prova por inducao forte em n Seja Pn o predicado que afirma que 5n 0 e verdadeiro para todo n N Caso base Quando n 0 5n 5 0 0 Assim P0 e verdadeiro Hipotese de inducao Seja k N Suponha que 5n 0 para todo inteiro n no intervalo 0 n k Passo Indutivo Vamos mostrar que Pn e verdadeiro quando n k 1 ou seja vamos mostrar que 5k 1 0 Escreva k 1 como a soma k 1 i j onde i j sao inteiros satisfazendo 0 i j k Como 0 i j k podemos aplicar a hipotese de inducao a i e j a fim de obter 5i 0 e 5j 0 Entao 5k 1 5i j 5i 5j 0 0 0 Portanto 5k 1 0 Assim Pk 1 e verdadeiro Como o caso base e o passo indutivo foram provados concluımos que Pn e verdadeiro para todo natural n 33 Enunciado falso prova incorreta Moral da historia Certifiquese de que nao exista lacuna entre o caso base e o primeiro caso do passo indutivo 34 FIM