Valberto Rômulo Feitosa Pereira
CEFETCE - Uned Cedro

O método de indução matemática foi usado ao longo da história, por pessoas como Maurolycus (1494-1575), Pascal (1623-1662) (em uma das demonstrações das propriedades de seu triângulo) e De Morgan (1806-1873). Mais tarde, o Princípio de Indução Finita (PIF) apareceu como o quinto axioma de Peano (1858-1932).

Uma das versões do PIF é:

“Uma proposição P(n), aplicável aos números naturais n, é verdadeira para todo n natural, n > n_o , quando:

1. P(n_o) é verdadeira, isto é, a propriedade é

o verdadeira para n = n_o.

2. Se P(n) é verdadeira para n_o < n < k, então P(k + 1) também é verdadeira.”

O PIF é, em geral, apresentado a nossos alunos na demonstração de afirmações do tipo:

Para qualquer número natural n, tem-se:

1³ + 2³ + 3³ + ... + n³ = (1 + 2 + 3 + ... + n)², ou

3²ⁿ– 1 é divisível por 8 ou, ainda, 2ⁿ> n.

Neste artigo, vamos mostrar a utilização do PIF em dois problemas tais que um olhar à primeira vista não sugere que possam ser resolvidos com indução.

Problema da fila do cinema

M . . . H

Um grupo de pessoas está em uma fila para comprar entradas para o cinema. A primeira pessoa na fila é uma mulher e a última é um homem. Mostre que, em algum ponto da fila, uma mulher está diretamente na frente de um homem.

Solução

Vamos usar o argumento da indução sobre n, sendo n o número de elementos da fila.

1. n = 2: o enunciado afirma que a única mulher está na frente do único homem e, portanto, a afirmação “em algum ponto da fila, uma mulher está diretamente na frente de um homem” é verdadeira.

2. Supondo a afirmação verdadeira para n = k, k > 2, vamos mostrar que é verdadeira para n = k + 1:

Neste caso, retirando a primeira mulher da fila, ficamos com uma fila de k pessoas, sendo a primeira mulher e a última homem. Pela hipótese de indução, há uma mulher diretamente na frente de um homem e isso continua verdadeiro ao recolocarmos a mulher no primeiro lugar da fila.

Logo, a afirmação é verdadeira.

Problema da existência de solução

Mostre que, para qualquer natural n, existem números inteiros x, y e z tais que x²+ y² = zⁿ.

Solução

Usando indução em n:

1. n = 1, a equação fica x² + y² = z, que tem, por exemplo, a solução (2; 3; 13).

n = 2, a equação fica x² + y² = z², e qualquer terna pitagórica, como (3; 4; 5), é solução.

2. Supondo a afirmação verdadeira para n = k, k > 2, vamos mostrar que é verdadeira para n = k + 1.

Tomemos (a, b, c) uma solução para n = k − 1: a² + b² = c^{k - 1}.

Então

(c²)a² + (c²)b² =(c²) c^{k - 1} ou (ca)² + (cb)² = c^{k + 1}, ou seja,

(ca; cb; c) é uma solução para a equação x² + y² = z^{k + 1}, como queríamos provar.

continuando...