Método de indução

O termo «indução» tem origem na Filosofia. A entrada do Dicionário de Fi- losofia de Simon Blackburn que lhe diz respeito começa do seguinte modo: Indução Termo usado sobretudo para designar qualquer processo de raciocí-
nio que nos conduza de premissas empíricas a conclusões empíricas, que,apesar de apoiadas pelas premissas, não são dedutivamente deriváveisdelas.
Assim, induzir é passar de algum conjunto de hipóteses para uma conclu- são que é compatível com essas hipóteses mas não pode ser deduzida delas. Porexemplo, seria natural induzir do estudo dos mamíferos que não há mamífe-ros que nasçam em ovos e que em todos eles as fêmeas amamentam os filhos.
Ambas as conclusões são compatíveis com tudo aquilo que podemos observarsobre mamíferos num raio de milhares de quilómetros em redor de Portugal.
Mas apenas a segunda das conclusões é verdadeira, pois os ornitorrincos e osequidnas são ovíparos.
É frequente em Matemática surgir a tentação de se passar da observação de vários casos particulares para uma conclusão geral. Vejamos alguns exemplos.
Exemplo 1: Se n ∈ , então
e assim sucessivamente. É fácil verificar directamente que aquilo que se afirmano exemplo é verdade para pequenos valores de n (ou até não tão pequenoscomo isso, se se recorrer a um computador). Mas será que é sempre verdade? Exemplo 2: Se n ∈ , então n2 − n + 41 é primo.
Facilmente se verifica que isto é verdade para pequnos valores de n . Assim, por exemplo, se n for igual a 1, 2, 3, 4 ou 5, então n 2 − n + 41 é igual a 41, 43,47, 53 ou 61 respectivamente; estes cinco números são primos. Isso continuaráa ocorrer à medida que n cresce? Exemplo 3: Qualquer número natural par maior do que 2 pode ser escrito como
soma de dois números primos.
Mais uma vez, facilmente se verifica que esta afirmação é verdadeira para números pequenos (4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, . . . ) mas será sempre verdade? Os exemplos anteriores podem ser vistos como exemplos de afirmações que pretendem ser válidas para todos os números naturais. Isto é óbvio nos casosdos exemplos e quanto ao exemplo este pode ser enunciado da seguinteforma: Se n for um número natural, então 2n + 2 pode ser escrito comosoma de dois números primos.
As afirmações feitas nos exemplos anteriores serão verdadeiras ou falsas? Exemplo A afirmação é verdadeira. A maneira mais simples de ver porquê é
Mas há aqui muitos termos que se cancelam entre si (−1/2 e 1/2, por exem-plo). Cancelando tudo o que se pode cancelar sobra apenas Exemplo A afirmação é falsa. Seja p (n) = n2 −n +41. Então os números p (1),
p (2), . . . , p (40) são primos, mas p (41) = 412 − 41 + 41 = 412, que não éprimo.
Exemplo Neste caso pura e simplesmente não se sabe se a afirmação é ver-
dadeira ou falsa! Até hoje nunca foi descoberto nenhum número inteiropar maior do que 2 que não possa ser escrito como soma de dois núme-ros primos, apesar do muito que já se pensou sobre o assunto nos últimosdois séculos e meio e do uso de computadores nas últimas décadas! Oenunciado do exemplo é conhecido por «conjectura de Goldbach».
O método de indução (que também se designa por princípio de indução) é um método de demonstrar enunciados que são válidos para todos os númerosnaturais. Ao contrário do que sucede na contexto da Filosofia, trata-se aqui deuma verdadeira demonstração.
Vejamos em que é consiste o método. Seja P(n) uma afirmação relativa a um número natural n ; por exemplo, retomando o exemplo a afirmação P(n)poderá ser Então dizer que aquilo que é afirmado no exemplo é verdade é o mesmo quedizer que, para cada n ∈ , P(n) é uma afirmação verdadeira. O método de indução consiste no seguinte: para provar que cada P(n) é uma afirmação ver-dadeira, prova-se que • P(1) é uma afirmação verdadeira; • sempre que P(n) for uma afirmação verdadeira (com n ∈ ), P(n +1) tam- Vejamos como fazer isto no caso do exemplo • seja n um número natural qualquer; quer-se provar que se P(n) for ver- dade (ou seja, se se tiver então também se tem P(n + 1), isto é Mas estamos a supor que se tem e, portanto, Exemplo 4: Se n ∈ , então n3 − n é múltiplo de 3.
Tal como no caso anterior, seja P(n) a afirmação «n3 − n é múltiplo de 3».
Apliquemos então o método de indução.
• Tem-se P(1), pois isto apenas quer dizer que 13 −1 é múltiplo de 3, ou seja, que 0 é múltiplo de 3, o que é obviamente verdade.
e suponha-se que se tem P(n), i. e. suponha-se que n3 − n é múltiplo de 3; quer-se provar que se tem P(n +1), o que equivale a afirmarque (n + 1)3 − (n + 1) é múltiplo de 3. Mas (n + 1)3 − (n + 1) = n3 + 3n2 + 3n + 1 − n − 1 = n3 − n + 3(n2 + n).
Então (n +1)3−(n +1) é a soma de n3−n (que se está a supor que é múltiplode 3) com 3(n2+n) (que é obviamente múltiplo de 3). Logo, (n +1)3−(n +1)é também múltiplo de 3.
Considere-se agora o seguinte problema: quanto dá a soma dos n primeiros números naturais ímpares? Comece-se por calcular esta soma para pequenosvalores de n : e assim sucessivamente. Os quatro números que surgem à direita nas quatroigualdades anteriores são, respectivamente, 12, 22, 32 e 42. Será que este padrãocontinua indefinidamente? Mesmo que verificássemos que este padrão conti-nua para os 10, 100 ou 1000 números seguintes, não poderíamos concluir dessefacto que a soma dos n primeiros números naturais ímpares é sempre igual an 2. Para o demonstrar, vai-se empregar o método de indução.
Exemplo 5: Se n ∈ , então
1 + 3 + 5 + · · · + (2n − 1) = n2.
Seja P(n) a afirmação Então • Ter-se P(1) é ser verdade que 1 = 12, coisa que não oferece dúvidas.
, P(n) for verdadeira, então quer-se provar que P(n + 1) 1 + 3 + 5 + · · · + (2n − 1) + (2n + 1) = (n + 1)2.
Mas a soma das primeiras n parcelas do membro da esquerda é, por hi-pótese, igual a n 2; logo, 1 + 3 + 5 + · · · + (2n − 1) + (2n + 1) = n2 + 2n + 1 = (n + 1)2.
Porque é que o método de indução funciona? Para perceber isso, é preciso dos números naturais. Este conjunto é for- mado por 1, pelo número que vem a seguir a 1 (ou seja, 2), pelo número quevem a seguir a esse (ou seja, 3) e assim sucessivamente. Por outro lado, se seconsegue aplicar o método de indução a uma sucessão de prP(1),P(2), P(3), . . . então aquilo que se terá provado é que 1) a proposição P(1) é verdadeira; 2) sempre que a proposição P(n) for verdadeira (esta hipótese designa-se por hipótese de indução), a proposição P(n + 1) também é verdadeira.
1) a proposição P(1) é verdadeira porque se provou isso; 2) a proposição P(2) é verdadeira porque P(1) é verdadeira e porque se pro- vou que sempre que se tem P(n), tem-se P(n + 1) e, em particular, comose tem P(1), tem-se P(2); 3) a proposição P(3) é verdadeira porque P(2) é verdadeira e porque se pro- vou que sempre que se tem P(n), tem-se P(n + 1) e, em particular, comose tem P(2), tem-se P(3); 4) a proposição P(4) é verdadeira porque P(3) é verdadeira e porque se pro- vou que sempre que se tem P(n), tem-se P(n + 1) e, em particular, comose tem P(3), tem-se P(4) e assim sucessivamente. Quais serão então as proposições P(n) (n ∈ ) que seterão demonstrado? A primeira (P(1)), a que vem a seguir a essa (P(2)), a quevem a seguir a essa (P(3)) e assim sucessivamente. Mas então estará provadoque se tem P(n) para qualquer número natural n! Isto também permite ver que não se pode usar indução para demonstrar propriedades dos números reais. Por exemplo, considere-se a seguinte proposi-ção: se x ∈ , então sen(x π) = 0. Tem-se então: 1Uma proposição é uma afirmação que é verdadeira ou falsa. Por exemplo, «4 > 2» e «2+2 = 5» são proposições. Por outro lado, «x 0» não é uma proposição (ser verdadeira ou falsa depende de x ) mas «para cada x ∈ , x 0» ou «há números reais x tais que x 1) sen(1.π) = sen(π) = 0; sen (x + 1)π = sen(x π + π) = sen(xπ)cos(π) + cos(xπ)sen(π)= 0 + 0= 0.
Mas, no entanto, a proposição não é verdadeira! O enunciado é falso para, porexemplo x = 1/2. O que falha aqui é que, embora não é formado somente por aqueles números.
Mas isto não quer dizer que o método de indução só possa ser aplicado aos números naturais. Pela mesma razão que a que foi dada para explicar porqueé que o método de indução funciona, ele aplica-se, por exemplo, para demons-trar que uma determinada propriedade é válida para todos os números inteirosmaiores ou iguais a um número inteiro dado p ; basta provar que a propriedadeé válida para o número p e que, se for válida para um número n ( p ), entãotambém é válida para n + 1.
Exemplo 6: Se n
É claro que 7(= 2×3+1) é menor ou igual a 9(= 32). Por outro lado, suponha- n 2 (hipótese de indução); quer- 2(n + 1) + 1 = 2n + 3 = (2n + 1) + 2 pela hipótese de indução; basta então provar que n 2 + 2 (n +1)2 = n2 +2n +1.
o que é verdade qualquer que seja n ∈ .
Ao tentar-se demonstrar por indução uma sucessão P(1), P(2), . . . de pro- posições, por vezes deparamo-nos com o seguinte fenómeno: ao provar-se queP(n) implica P(n + 1) (aquilo que se designa por passo de indução), constata-seque para fazer aquela demonstração é necessário usar indução novamente! Quefique claro que isso não tem mal nenhum.
Exemplo 7: Se n
Para n = 5, não há problema (32 > 25). Suponha-se agora que, para n tem 2n > n2; quer-se provar que 2n+1 > (n + 1)2. Mas 2n+1 = 2 × 2n > 2n2, pela hipótese de indução; portanto, basta provar que 2n 2 (n + 1)2 ⇐⇒ 2n2 n2 + 2n + 1 ⇐⇒ n2 2n + 1, que é precisamente a desigualdade do exemplo Além disso, no exemplo provou-se que se tem aquela desigualdade sempre que n razão, a desigualdade é válida quando n Concluindo: demonstrar por indução uma proposição relativa a todos os números naturais consiste em demonstrar que é válida para o número 1 e emdemonstrar o passo de indução. É só isso! Naturalmente, demonstrar que éválida para o número 1 pode ser mais ou menos difícil e o mesmo se aplica ademonstrar o passo de indução.
Existe também um outro método de demonstrar resultados sobre os núme- ros naturais que se designa por indução forte e que consiste no seguinte: parase demonstrar que as proposições P(1), P(2), . . . são todas verdadeiras demons-tra-se que P(1) é verdadeira e que, para cada n ∈ , se as proposições P(1), P(2),. . . , P(n) forem verdadeiras, então P(n + 1) também é verdadeira.
Exemplo 8: Qualquer número natural maior do que 1 pode ser escrito como
produto de números primos.
Antes de se passar à demonstração, é preciso deixar claro que, ao falar-se de «produto de primos», está-se também a considerar a possibilidade de haverum único primo envolvido; assim, 18 pode ser escrito como produto de primosporque 18 = 2 × 3 × 3 (e 2 e 3 são primos), 49 pode ser escrito produto de primosporque 49 = 7 × 7 (e 7 é primo) e 5 pode ser escrito como produto de primosporque 5 = 5 (e 5 é primo).
Demonstrar-se o que é enunciado no exemplo é então o mesmo que de- monstrar que, para cada n ∈ , é válida a seguinte proposição: n = 1 ou n podeser escrito como produto de primos. Para n = 1, é claro que se tem isto. Sejaagora n ∈ e suponha-se que já se provou que os números de 1 a n têm todos a propriedade de serem iguais a 1 ou poderem ser escritos como produto de pri-mos; quer-se provar que acontece o mesmo com n + 1. É claro que n + 1 nãoé igual a 1; quer-se então provar que pode ser escrito como produto de primos.
Se n + 1 for primo, então pode ser escrito como produto de primos. Por outrolado, se n +1 não for primo, então pode-se escrever n +1 como um produto k ×londe k e l são números naturais maiores do que 1 e menores do que n + 1. Masentão k ∈ {2, . . . , n}, pelo que, por hipótese, k pode ser escrito como produto deprimos. O mesmo argumento aplica-se a l e, como n + 1 = k × l , n + 1 pode serescrito como produto de primos.
Uma propriedade básica dos números naturais que está relacionada com o método de indução é o princípio da boa ordenação. Para o enunciar é conveni-ente introduzir a seguinte expressão: diz-se que um elemento a de um conjuntoC de números reais é primeiro elemento de C se: • para cada x ∈ C , a É frequente o primeiro elemento de um conjunto ser também designado pormínimo desse conjunto. Naturalmente, um conjunto de números reais não temque ter primeiro elemento; ]0, +∞[, da boa ordenação diz então o seguinte: qualquer conjunto não vazio de núme-ros naturais tem primeiro elemento. E porque é que isto é verdade? Como talvezfosse de esperar, vai-se demonstrar a validade do princípio da boa ordenaçãousando indução. Mais precisamente, vai-se usar indução para demonstrar que,para cada número natural n , se C for um conjunto de números naturais quecontenha n , então C tem primeiro elemento.
É claro que se 1 ∈ C , então 1 é o primeiro elemento de C , pois 1 ∈ C (por hipótese) e qualquer número natural é maior ou igual a 1; por maioria de razão,qualquer elemento de C é maior ou igual a 1. Suponha-se agora que, para umn ∈ , qualquer conjunto C de números naturais que contenha n tem primeiroelemento; quer-se provar que qualquer conjunto C de números naturais quecontenha n + 1 tem primeiro elemento. É claro que, como já foi visto atrás, se1 ∈ C então 1 é o primeiro elemento de C . Por outro lado, se 1 / conjunto obtido a partir de C subtraindo 1 a cada um dos seus elementos. EntãoC ⊂ , pois 1 é o único número natural n tal que n −1 / Por outro lado, n ∈ C , pois n + 1 ∈ C . Mas então, pela hipótese de indução, Ctem primeiro elemento p e é então claro que p + 1 é o primeiro elemento de C .
O princípio da boa ordenação também permite demonstrar teoremas. Vai- -se dar um exemplo humorístico, mas que ilustra a ideia básica.
Exemplo 9: Todos os números naturais são interessantes.
Se o conjunto dos números naturais desinteressantes não fosse vazio, teria um primeiro elemento n . Mas então n , sendo o primeiro número desinteres-sante, até que era interessante! Com um pouco de prática, é fácil ver que qualquer demonstração que se possa fazer por indução forte também pode ser feita recorrendo ao princípio daboa ordenação e vice-versa.
Analogamento ao método de indução, que é um método de demonstrar su- cessões de proposições, também há a possibilidade de se fazerem definições porindução. O tipo mais simples de uma definição deste tipo consiste em definir-seuma sucessão (a n )n∈ do seguinte modo: 2) para cada n ∈ , define-se a n+1 a partir de a n .
2Mas deve-se observar que quando um conjunto C tem primeiro elemento, então só pode ter um. De facto, se a e b forem ambos primeiros elementos de C então, pela definição de primeiroelemento, a a , pelo que a = b .
Exemplo 10: Seja (a n )n∈ a sucessão de números naturais tal que a 1 = 1 e, para
cada n ∈ , a n+1 = 2a n + 1.
Que sucessão é esta? Por definição, a 1 = 1. Quanto é a 2? Como 2 = 1+1 e a 1 está definido (é igual a 1), então a 2 = 2a 1 + 1 = 3. Quanto a a 3, como 3 = 2 + 1,tem-se que a 3 = 2a 2 + 1 = 7. É claro que a 4 = 2a 3 + 1 = 15, que a 5 = 2a 4 + 1 = 31e assim sucessivamente.
Exemplo 11: Dada uma sucessão (a n )n∈ de números reais, é usual definir-se
k como sendo igual a a 1 + a 2 + · · · + a n . Uma maneira mais elegante de definir o somatário consiste em defini-lo indutiv Este método de definir o somatório tem a vantagem de não usar reticências, quepodem ser uma fonte de ambiguidade.
Exemplo 12: Dado um número natural k , considere-se a sucessão (a n )n∈ tal
que:
2) a n+1 é igual 3a n + 1 se a n for ímpar e é igual a metade de a n se a n for Que sucessão é esta se k = 1? É claro que a 1 = 1. Como a 1 é ímpar, a 2 = 3a 1+1 =4. Este número é par e então a 3 = a2/2 = 2. Pelo mesmo argumento, a 4 = a3/2 = 1.
Agora regressou-se ao valor 1 e então o processo recomeça. Vê-se então que,para k = 1, a sucessão é Os cálculos a fazer são os mesmos se k = 2 ou k = 4; obtêm-se respectivamenteas sucessões Se k = 3, a sucessão é ligeiramente mais complicada: 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, . . .
Uma coisa que se constata à medida que se vão calculando estas sucessões comvalores cada vez maiores de k é que a sucessão acaba sempre por ir dar a 1. Seráque isso acontece para qualquer k ? É um problema em aberto! É também possível fazer definições por recorrência nas quais se definem os dois primeiros termos e depois se define cada um dos restantes à custa dos doisanteriores.
3As definições indutivas costumam ser designadas por definições por recorrência.
Exemplo 13: A sucessão de Fibonacci (Fn )n∈ define-se por
3) se n ∈ , então Fn+2 = Fn + Fn+1.
Os primeiros termos desta sucessão são 1, 1, 2, 3, 5, 8, 13, 21, 34, . . .
Exemplo 14: Seja (a n )n∈ a sucessão de números naturais tal que
3, a n é o menor número natural para o qual seja verdade que Quanto é a 3? É o menor número natural tal que logo, a 3 = 379. Por seu lado, a 4 é o menor número natural para o qual A sucessão do exemplo anterior cresce bastante rapidamente; os dez primei- ros termos são 8, 55, 379, 2 612, 18 002, 124 071, 855 106, 5 893 451, 40 618 081 e279 942 687.
Naturalmente, podem-se também definir sucessões por recorrência defi- nindo primeiro os três primeiros termos e definindo cada um dos restantes àcusta dos três anteriores, definindo os quatro primeiros termos e definindo cadaum dos restantes à custa dos quatro anteriores e assim sucessivamente.
Exemplo 15: Seja (a n )n∈ a sucessão do exemplo e seja (bn )n∈ a sucessão
de números naturais tal que
1) bn = a n para cada n ∈ {1,2,3,4}; 5, bn = 6bn−1 + 7bn−2 − 5bn−3 − 6bn−4 b5 = 6b4 + 7b3 − 5b2 − 6b1 = 6 × 2 612 + 7 × 379 − 5 × 55 − 6 × 8= 18 002.
Não é necessária uma grande perspicácia para se ver que os cinco primeiros termos desta sucessão são também os cinco primeiros termos da sucessão doexemplo Quanto aos quatro primeiros, isso não será propriamente surpre-endente, pois resulta da própria definição de bn para n ∈ {1,2,3,4}, mas à partidanão havia nenhum motivo para se pensar que b5 = a 5. De facto, quem prosse-guir com os cálculos não terá dificuldade em constatar que b6 = a 6, b7 = a 7,b8 = a 8 e assim por diante. Será que as duas sucessões são idênticas? Nãosão, mas é preciso levar os cálculos mesmo muito longe para nos apercebermosdisso, pois tem-se a n = bn para cada n < 11 057. Quanto aos números a 11 057 eb11 057, são números com 9 270 algarismos cada que diferem em uma unidade!Isto é mais um exemplo de como, quando se está perante uma proposição re-lativa a números naturais, não basta provar que é verdadeira para um grandenúmero deles para se concluir que é verdadeira em todos os casos.

Source: http://www.lia.ufc.br/~wladimir/matdisc2010.2/inducao.pdf