Problemas

#Notas Soltas: Redução ao Absurdo e Indução Fraca

Neste post pretendo complementar o que já foi feito ao longo das aulas de Bases Matemáticas, quando foi ensinado a técnica por indução redução ao absurdo.

Começamos por um problema que envolve estimativas para a soma de n números inteiros.

Problema

Se para cada n\geq 2 natural, temos que a soma dos n números inteiros a_1,a_2,\ldots,a_n é tal que

a_1+a_2+\ldots+a_n \geq 19 n,

então pelo menos um dos a_i (i=1,2,\ldots,n) é maior que 18.

Resolução

A resolução deste problema pode ser realizada, combinando indução matemática com redução ao absurdo:

CASO BASE (n=2)

Para provar que para n=2 se tem a implicação

a_1+a_2\geq 38 \implies a_1> 18 ou a_2> 18,

 comece por assumir, por redução ao absurdo que

a_1+a_2\geq 38 & a_1\leq 18 e a_2\leq 18.

Usando propriedades elementares de números reais, segue que

36 \geq a_1+a_2\geq 38.

e, em particular, que 36 \geq 38, o que é absurdo (complete aqui com a sua justificativa).

PASSO INDUTIVO (n=k \implies n=k+1)

Por hipótese de indução, comece por supor que a_1+a_2+\ldots+a_k \geq 19 k implica que pelo menos um dos a_i (i=1,2,\ldots,k) seja maior que 18.

Seja b=a_1+a_2+\ldots+a_k. Suponha agora, por redução ao absurdo, que

b+a_{k+1}\geq 19(k+1) & a_{i}\leq 18.

para todos os i =1,2,\ldots,k+1.

Segue então em particular que b+a_{k+1}\leq b+18

e, consequentemente a dupla desigualdade

b+18\geq b+a_{k+1}\geq 19(k+1).

Da dupla desigualdade acima concluímos, em particular, que b+18\geq 19(k+1).

Obtemos assim que b\geq 19k+1>19k.

Usando agora a hipótese de indução, temos que a condição b>19k implica, em particular, que pelo menos um dos a_i's é maior que 18, o que contraria o fato assumido por absurdo (todos os a_i's são menores ou iguais 18).

Observação:

Vejamos agora como o mesmo tipo de estratégia pode ser aplicado para provar propriedade abaixo. Iremos em particular recorrer à desigualdade triangular e à sua generalização indutiva (Exercícios 82. (c) & 86. (b) do livro de exercícios):

Se a soma de n números reais satisfaz a condição de módulo

|a_1+a_2+\ldots+a_n|>n

então pelo menos um dos a_i‘s satisfaz a condição |a_i|>1.

Para n=1 a demonstração é deveras trivial. A técnica de redução ao absurdo apenas faz sentido de ser aplicada para o caso de n\geq 2:

Com efeito, se as inequações |a_1+a_2+\ldots+a_n|>n e |a_i|\leq 1 (i=1,2,\ldots,n) fossem satisfeitas, poderíamos provar indutivamente que

n<|a_1+a_2+\ldots+a_n|\leq |a_1|+|a_2|+\ldots+|a_n|\leq n,

Seguiria então que n<n (absurdo?!).

Deixe um comentário