(k + 1)2 + (k + 1) é ímpar. Observe que (k + 1)2 + (k + 1) = k2 + 2k + 1 + k + 1 = (k2 + k) + 2(k + 1) Este resultado é impar, pois (k2 + k) é ím...

(k + 1)2 + (k + 1) é ímpar. Observe que

(k + 1)2 + (k + 1) = k2 + 2k + 1 + k + 1 = (k2 + k) + 2(k + 1)

Este resultado é impar, pois (k2 + k) é ímpar pela hipótese de indução, 2(k + 1) é par, e um número ímpar somado com um número par é ímpar.

Fim.

Exercício 5.16: Considere a afirmação (obviamente falsa) P(n): “Para todo número real a > 0 e todo natural n, an = 1”. Encontre o erro na demonstração por indução abaixo.

Prova:

• Base: P(0) é obviamente verdadeira uma vez que a0 = 1.

• Hipótese de indução: Suponha que P(k) é verdadeira para algum k ≥ 0, ou seja, ak = 1.

• Passo de indução: Vamos mostrar que P(k+1) é verdadeira, isto é ak+1 = 1. Observe que

ak+1 = ak−1 · a = ak−1 · ak−1

ak−2 = 1 · 1

1 = 1.

Portanto P(k + 1) também é verdadeira.

Fim.

5.6 Princípio da Indução Completa

Vamos agora enunciar o princípio da indução completa (PIC), também chamado de princípio da indução forte. Esta versão alternativa do princípio da indução matemática serve, como a anterior, para demonstrar sentenças na forma “(∀n ∈ N) P(n)”. Em alguns casos essa técnica torna a demonstração da sentença mais fácil que a técnica anterior. Na seção 5.9 provaremos a equivalência desses dois princípios.

Teorema 5.5: Seja P(n) uma sentença aberta sobre N. Suponha que

1. P(0) é verdade; e

2. para todo k em N, ((∀i ∈ N) i ≤ k, P(i))→ P(k + 1),

então P(n) é verdade para todo n ∈ N.

Portanto para provar que “(∀n ∈ N) P(n)” é verdadeiro, usando indução completa, devemos proceder da seguinte forma:

1. Base da indução: Mostrar que P(0) é verdade.

2. Hipótese de indução: Supor que, para algum k ∈ N, P(i) é verdade para todo i com 0 ≤ i ≤ k.

3. Passo da indução: Mostrar que P(k + 1) é verdade.

Como no PIM, podemos generalizar e considerar a base n0 no lugar de 0.

Exemplo 5.11: Definimos que um número natural p > 1 é primo quando os únicos divisores dele são 1 e o próprio p. Vamos mostrar que todo inteiro maior ou igual a 2 é primo ou é um produto de primos.

Prova:

Seja P(n) a sentença aberta “n é primo ou é um produto de primos.” Vamos provar que (∀n ∈ N) n ≥ 2→ P(n), por indução completa.

• Base: P(2) é verdade pois 2 é primo.

• Hipótese de indução: Suponha que, para algum k ≥ 2, P(i) é verdade para todo i ∈ N com 2 ≤ i ≤ k.

• Passo da indução: Vamos provar que P(k + 1) também é verdade. Se k + 1 é primo então P(k+1) é verdadeiro. Se k+1 não é primo, como k+1 ≥ 2, ele deve ter algum divisor diferente de 1 e de k+1. Ou seja, k+1 = aḃ para algum a e b, com 1 < a ≤ k. Como a > 1, concluímos que b < k + 1; como a < k + 1, concluímos que b > 1. Ou seja, 2 ≤ a ≤ k e 2 ≤ b ≤ k. Pela hipótese de indução, portanto, a e b são primos ou produtos de primos. Portanto k + 1 = a · b também é um produto de primos.

Fim.

5.6.1 Formulação do PIC usando conjuntos

Assim como no caso do PIM, o princípio da indução completa também pode ser enunciando usando a linguagem da teoria de conjuntos:

Teorema 5.6: Seja S um subconjunto de N tal que

1. 0 ∈ S , e

2. Para todo k em N, {0, 1, 2, . . . , k} ⊆ S → k + 1 ∈ S ;

então S = N.

5.7 Exercícios

Exercício 5.17: Prove que todo número natural m > 0 pode ser escrito como soma de potências de 2, isto é, existem números inteiros n1, n2, . . . , nr, com 0 ≤ n1 < n2 < · · · < nr, tais que

m = 2n1 + 2n2 + · · · + 2nr

Exercício 5.18: Sejam m moedas, uma das quais é falsa e tem peso diferente das demais. Use o exercício anterior mostrar, por indução, que bastam nr pesagens com uma balança de pratos para descobrir a moeda falsa.

Exercício 5.19: Os números de Fibonacci F0, F1, F2, . . . são definidos pelas seguintes regras: F0 = 0, F1 = 1, e Fn = Fn−1 + Fn−2 para todo número natural n maior ou igual a 2. Prove, por indução, que

1. (∀n ∈ N) Fn < (13 8 )n.

2. (∀m, n ∈ N) FmFn + Fm+1Fn+1 = Fm+n+1.

3. (∀n ∈ N) S n = Fn − 1 onde S n é o número de somas realizadas ao se calcular Fn.

Exercício 5.20: Sejam α e β as duas soluções da equação x2 − x − 1 = 0, com α > 0. Prove que Fn = (αn − βn)/(α − β), para todo n em N.

Exercício 5.21: Sejam x um número real diferente de zero, tal que x + 1 x é um número inteiro. Prove que, para todo número natural n, xn + 1 x é inteiro.

5.8 Princípio da Boa Ordenação

Uma outra maneira de provar sentenças abertas sobre número naturais é usar uma propriedade dos números naturais conhecida como o princípio da boa ordenação (PBO).

Seja S um conjunto de números reais. Um elemento mínimo de S é um y ∈ S tal que para todo x ∈ S, y ≤ x. O princípio da boa ordenação diz que

Teorema 5.7: Todo subconjunto não vazio S de N tem um elemento mínimo.

Note que esta afirmação não é válida para subconjuntos de R ou Z; isto é, existem subconjuntos de R e de Z que não tem elemento mínimo.

Como exemplo de uso do PBO, vamos provar o Teorema da Divisão de Euclides:

Teorema 5.8: Sejam a, b ∈ N, com b ≠ 0. Então existem q, r ∈ N tais que a = bq + r com 0 ≤ r < b.

Prova:

Sejam a, b ∈ N, com b ≠ 0, e seja

S = { a − b · k : k ∈ N, a − b · k ≥ 0 }

Observe que S ⊆ N pois a − b · k ≥ 0; e que S ≠ ∅ pois contem a = a − b · 0. Então pelo PBO S tem um elemento mínimo. Seja r = a − b · q esse elemento.

Suponha agora que r ≥ b. Nesse caso a − b · (q + 1) = r − b