Indução matemática

A indução matemática é um método de demonstração muito usado na matemática, na maioria das vezes quando trabalhamos com números naturais ou com alguma outra sequência.

Princípio

O princípio básico é que demonstramos a afirmação dada para um primeiro elemento; nos números naturais positivos, na maioria das vezes, é n = 1. Demonstramos isso por simples substituição. No passo seguinte, o passo indutivo, demonstramos a implicação “se a afirmação vale para n = a, então vale também para n = a + 1”.

Desses dois passos podemos deduzir que a expressão dada vale para todos os n (de algum conjunto com o qual estamos trabalhando). Por que é assim? No início, demonstramos que a expressão vale para n = 1. Ao mesmo tempo, sabemos que, se a expressão vale para n = a, vale também para n = a + 1. Escolhemos então a = 1. Sabemos que, para a = 1, a expressão vale e também sabemos que vale para a + 1 = 2. Neste momento sabemos que a expressão vale para a = 2. Mas, como vale também para a + 1, precisa valer também para 2 + 1 = 3. E assim por diante.

Primeiro exemplo

O primeiro exemplo será trivial. Vamos demonstrar que, se a qualquer número par somarmos dois, obtemos novamente um número par. Como nos movemos nos números naturais positivos, escrevemos em geral o número par como 2n, em que n é um número natural positivo. Se no lugar de n substituirmos qualquer número natural positivo, obtemos no resultado um número par, isso é visível à primeira vista. A divisibilidade se escreve com uma barra vertical assim:

$$2\mid 2n$$

Essa notação significa que o dois divide sem resto a expressão 2n. Já que sabemos escrever a divisibilidade, podemos escrever também o que devemos demonstrar por indução matemática.

$$2\mid 2n+2;n\in {\mathbb{N}}^{\ast }$$

Isso é o que devemos demonstrar no primeiro exemplo, ou seja, que o dois divide a expressão 2n + 2 — exatamente o que corresponde ao enunciado original em palavras “se a qualquer número par somarmos dois, obtemos novamente um número par”.

No primeiro passo da indução, demonstramos isso para o primeiro elemento, para o um. Substituímos na expressão n = 1:

$$\begin{array}{rcl}2& \mid & 2\cdot 1+2\\ 2& \mid & 4\end{array}$$

O dois divide o quatro sem resto, então para o primeiro elemento vale. Em seguida vem o passo indutivo, em que precisamos demonstrar que, se vale para o a-ésimo elemento, vale também para o elemento (a + 1). No início, supomos que vale a nossa hipótese, isto é, n = a:

$$2\mid 2a+2$$

Supomos que essa expressão é verdadeira — vamos usá-la na construção da demonstração. Agora queremos demonstrar que

$$2\mid 2(a+1)+2.$$

O que fizemos? No lugar de a escrevemos (a + 1). Os parênteses são importantes, esta expressão estaria errada: 2a + 1 + 2. Não somamos um à expressão inteira, mas realmente transformamos a em uma expressão uma unidade maior, isto é, (a + 1). Transformamos a expressão eliminando os parênteses.

$$\begin{array}{rcl}2& \mid & 2(a+1)+2\\ 2& \mid & 2a+2+2\end{array}$$

Agora, uma pequena digressão sobre a divisibilidade. Se temos dois números, digamos p e q, que são divisíveis por algum número, por exemplo r, então vale que a soma deles também é divisível por r. Vale, portanto:

$$(r\mid p\wedge r\mid q)\Rightarrow r\mid (p+q)$$

Podemos substituir ali, por exemplo, os números p = 8, q = 20 e r = 4. Vemos que o quatro divide tanto o oito quanto o vinte. E da mesma forma divide também a soma deles, 8 + 20 = 28.

Como aproveitamos isso no nosso exemplo? Dividimos o segundo membro nas parcelas p e q assim:

$$p=2a+2;q=2$$

O número q, isto é, o dois, é trivialmente divisível por dois. E a expressão p também é divisível por dois, porque a hipótese nos diz isso. A expressão p corresponde exatamente à nossa hipótese, que supomos ser verdadeira. E, se p é divisível por dois e, ao mesmo tempo, q é divisível por dois, então a soma deles também é divisível por dois.

Mais uma vez sobre a hipótese. No início, dissemos que supomos que vale

$$2\mid 2a+2.$$

Por isso, quando, durante a construção da demonstração, nos deparamos com a expressão 2a + 2, pudemos dizer que ela é divisível por dois. Justamente porque é a nossa hipótese. Esse costuma ser o passo mais difícil da indução matemática — entender quando e por que se pode usar a hipótese de indução.

Com isso a indução termina, a demonstração foi realizada com sucesso, o teorema vale.

Se quiséssemos, poderíamos decompor de outro modo e não precisaríamos usar a hipótese. p = 2n e q = 2 + 2. O número q = 4 é trivialmente divisível por dois e, da mesma forma, p = 2n, porque, depois de dividir por dois, nos resta o número n, que é natural, isto é, inteiro. Novamente obtivemos, assim, duas expressões que são ambas divisíveis por dois, então a soma delas também é divisível por dois.

Nos dois casos, porém, demonstramos que

1. a expressão dada vale para n = 1,
2. se a expressão vale para n, então vale também para n + 1.

Daqui já podemos deduzir:

• Sabemos que a expressão vale para n = 1.
• Se vale para n, precisa valer também para n + 1, isto é, também para 1 + 1, ou seja, a expressão vale também para n = 2.
• Se vale para n, precisa valer também para n + 1, isto é, também para 2 + 1, ou seja, a expressão vale também para n = 3.
• Se vale para n, precisa valer também para n + 1, isto é, também para 3 + 1, ou seja, a expressão vale também para n = 4.
• Se vale para n, precisa valer também para n + 1, isto é, também para 4 + 1, ou seja, a expressão vale também para n = 5.
• …

Segundo exemplo

Em seguida, vamos demonstrar por indução matemática uma afirmação simples:

$$2^n\ge 2n;n\in {\mathbb{N}}^{\ast }.$$

Primeiro o passo base: verificamos se a afirmação vale para n = 1, como primeiro elemento dos números naturais positivos, dos quais escolhemos n.

$$\begin{array}{rcl}{2}^1& \ge & 2\cdot 1\\ 2& \ge & 2\end{array}$$

Isso vale trivialmente. Agora passamos ao passo indutivo, no qual precisamos verificar se, quando vale para n = a, vale também para n = a + 1. Assim, a nossa hipótese é que vale

$$2^a\ge 2a$$

e queremos demonstrar:

$$2^{a+1}\ge 2(a+1)$$

Primeiro, desenvolvemos o primeiro membro com as regras de cálculo com potências e, no segundo membro, simplesmente aplicamos a distributiva.

$$2\cdot 2^a\ge 2a+2$$

No primeiro membro, em vez da multiplicação, usamos a adição, e deixamos o segundo sem mudança.

$$2^a+2^a\ge 2a+2$$

Agora aproveitamos a hipótese. A hipótese é uma afirmação que supomos válida. Na inequação temos, em ambos os lados, duas expressões que estão somadas. Ao mesmo tempo, porém, sabemos que

$$\begin{array}{rcl}{2}^a& \ge & 2a\\ 2^a& \ge & 2.\end{array}$$

A primeira linha é a própria hipótese e a segunda afirmação é trivial (o menor 2^a ocorre para a = 1 e isso é igual justamente a dois). Assim, sabemos que, no primeiro membro, ambas as expressões são maiores ou iguais a ambas as expressões do segundo membro. Com isso demonstramos por indução que, se a expressão vale para a, então vale também para (a + 1) e, como a expressão vale também para o um, a expressão dada é verdadeira.

Terceiro exemplo

Vamos tentar demonstrar a seguinte afirmação:

$$3\mid n\Rightarrow 3\mid n^2;n\in {\mathbb{N}}^{\ast }$$

Em palavras: se n é divisível por três, então n² também é divisível por três. Se n não é divisível por três, então a expressão vale trivialmente (pela definição de implicação), então vamos nos ocupar dos casos em que n é divisível por três. Isso nos gera uma sequência de números naturais a_i=3, 6, 9, 12, 15… A partir de agora, vamos nos mover nessa sequência a_i.

Começamos a demonstração por indução pelo primeiro passo, isto é, se vale para o primeiro elemento. Lembro que nos movemos na sequência a_i, então tomamos o primeiro elemento dessa sequência, isto é, o elemento a₁, que é o três. Para o três, a expressão vale:

$$3\mid 3\Rightarrow 3\mid 3^2$$

Agora passamos ao passo indutivo. Vemos que a sequência a_i poderia ser escrita como 3n, em que n é um número natural positivo. Ou seja, o segundo elemento é três unidades maior que o anterior etc. Agora suponhamos que a expressão valha para n e precisamos garantir que valha também para (n + 3), que é a regra que gera o elemento seguinte na sequência em que nos movemos. Escrevemos primeiro a hipótese:

$$3\mid n\Rightarrow 3\mid n^2$$

e depois o que queremos demonstrar

$$3\mid (n+3)\Rightarrow 3\mid (n+3{)}^2.$$

Desenvolvemos o parêntese do outro lado usando a fórmula:

$$3\mid (n+3)\Rightarrow 3\mid n^2+6n+9.$$

E já estamos quase no fim. No primeiro membro, temos uma expressão que certamente é divisível por três, porque n é, segundo a hipótese, divisível por três (só nos movemos nos números da sequência a_i) e o três também é divisível por três. No segundo membro, temos primeiro n², que, segundo a hipótese, é divisível por três. De fato, sabemos que n é divisível por três e a hipótese diz que, se n é divisível por três, então n² também é divisível por três:

$$3\mid n\Rightarrow 3\mid n^2$$

Em seguida vem a expressão 6n, que é trivialmente divisível por três. Você pode imaginar isso como a simplificação de uma fração:

$$\frac{6n}{3}=2n$$

A variável n é algum número natural positivo, então também o produto 2n será um número natural positivo, isto é, depois de dividir por três obtivemos um número natural positivo e a expressão 6n precisa, assim, ser divisível por três. E o nove no final é, novamente, divisível por três. A expressão vale para o primeiro elemento e para o passo indutivo, então é verdadeira.

Número de parênteses em uma expressão

O último exemplo será um pouco atípico. Vamos tentar demonstrar a afirmação de que o número de parênteses em uma expressão simples é sempre par, para você ver que a indução matemática pode ser usada também em um contexto totalmente diferente dos números naturais. No início, precisamos definir o que é uma expressão simples. Uma expressão simples é:

• um número natural positivo,
• se p é uma expressão simples, então (p²) também é uma expressão simples,
• se p e q são expressões simples, então (p + q) também é uma expressão simples.

Então, o que é uma expressão simples: 12, 54, (5 + 6), (12 + 7), (6²), ((5 + 6)²). E, ao contrário, estas não são expressões simples:

• 1 + 2 → faltam os parênteses externos,
• (1 + 2 → falta o parêntese direito,
• 13² → faltam os parênteses externos,
• (1 + 2 + 3) → faltam parênteses, a notação correta deveria ser (1 + (2 + 3))

Uma expressão simples pode surgir, por exemplo, assim. No início, escolhemos a expressão simples (a + b). Agora, no lugar de a substituímos a expressão simples a = (c + d), então obtemos ((c + d) + b) e, no lugar de b, substituímos o três: ((c + d) + 3). No lugar de c substituímos o dez: ((10 + d) + 3) e, por fim, no lugar de d substituímos (5²): ((10 + (5²)) + 3). É importante respeitar os parênteses, senão não vai funcionar.

Agora vamos demonstrar que uma expressão simples contém um número par de parênteses (entre os números pares inclui-se também o zero).

No primeiro passo da indução, escolhemos algum primeiro elemento. Neste caso, o primeiro elemento será a expressão simples mais trivial, que é um número natural positivo qualquer. Assim, estabelecemos

$$j=n;n\in {\mathbb{N}}^{\ast }.$$

Para a expressão j vale que o número de parênteses é zero, então o primeiro elemento satisfaz a afirmação. No passo indutivo, vamos supor que temos duas expressões simples p e q e que ambas têm um número par de parênteses. Então precisamos demonstrar que também as expressões simples (p + q) e (p²) têm um número par de parênteses.

Primeiro a adição. Vamos definir ainda a função z(q), que devolve o número de parênteses da expressão q. Então vale que a expressão (p + q) tem z(p) + z(q) + 2 parênteses. Ou seja, tem dois parênteses a mais do que a soma dos parênteses das expressões p e q. Pela hipótese, tanto z(p) quanto z(q) são pares; então, se somarmos três números pares, obtemos novamente um número par. Para esse caso, a afirmação vale.

Agora a potência. Novamente vale a hipótese de que a expressão simples p contém um número par de parênteses. A expressão (p²) contém então z(p) + 2 parênteses, ou seja, de novo dois parênteses a mais que a expressão p. Também neste caso somamos números pares, e o resultado é, portanto, par.

A afirmação vale para o primeiro elemento e vale também no passo indutivo, por isso a afirmação é verdadeira.