Bases Matemática (19)

Prévia do material em texto

Aula 5 de Bases Matemáticas
Rodrigo Hausen
1 de julho de 2014
1 Princípio da Indução Finita
1.1 Versão Fraca
Definição 1 (P.I.F., versão fraca) Seja p(n) uma proposição aberta no
universo dos números naturais.
SE valem ambas as propriedades abaixo:
• (Base de indução) p(n0) é verdadeira para algum n0 ∈ N
• (Passo de indução) p(n)⇒ p(n+ 1) para todo n ≥ n0
ENTÃO p(n) é verdadeira para todo n ≥ n0.
Exercício 1 Demonstre que 2n ≥ 1 + n para todo número natural.
Demonstração. Seja p(n) = �2n ≥ 1 + n.� Demonstraremos que p(n) é
verdadeira para todo n ∈ N usando o P. I. F.
Base de indução: p(0) é verdadeira? Ou seja, 20 ≥ 1 + 0 ? Sim.
Passo de indução: p(n)⇒ p(n+ 1) para todo n ≥ 0 ?
Assuma que p(n) é verdade, ou seja, que 2n ≥ 1 + n. O que podemos
dizer sobre 2n+1?
2n ≥ 1 + n
2 · 2n ≥ 2 · (1 + n)
2n+1 ≥ 2 + 2n
2n+1 ≥ 1 + n+ 1 + n ≥ 1 + n+ 1 , pois n ≥ 0
2n+1 ≥ 1 + n+ 1
Logo, se p(n), então p(n+ 1) é verdade.
Como tanto a base, quanto o passo de indução são válidos, então p(n) é
verdade para todo n ≥ 0. �
Ao usar o PIF, tenha cuidado! É necessário demonstrar tanto a base,
quanto o passo de indução. A falta de cuidado com o PIF pode levar a
conclusões absurdas, tais como as que se seguem.
1
Absurdo 1 É verdade que n = 0 para todo n ∈ N.
Demonstração errada. Seja p(n) = “n = 0′′. Como p(0) é válida, pois
0 = 0, então p(n) vale para todo n. �
Erro na demonstração: não mostramos que o passo de indução é válido!
É impossível demonstrar que vale o passo de indução, já que p(n) é falsa
para n > 0.
Absurdo 2 n2 + n é ímpar para todo n ≥ n0
Demonstração errada. Seja p(n) = “n2 + n é ímpar.�
Assuma que p(n) é válida, logo n2 + n = 2k + 1 para algum k ∈ N. O
que podemos dizer de (n+ 1)2 + (n+ 1)?
(n+ 1)2 + (n+ 1) = n2 + 2n+ 1 + n+ 1
= n2 + n︸ ︷︷ ︸
=2k+1, por hipótese
+2n+ 2
= 2k + 1 + 2n+ 2
= 2 (k + n+ 1)︸ ︷︷ ︸
∈N
+1
Logo, (n + 1)2 + (n + 1) também é ímpar, portanto está demonstrado que
n2 + n é ímpar para todo n ∈ N. �
Erro na demonstração: Não demonstramos que a base de indução p(0) é
válida. Veja que são falsas:
p(0) = “02 + 0 é ímpar′′
p(1) = “12 + 1 é ímpar′′
p(2) = “22 + 2 é ímpar′′
Não existe nenhum n0 que sirva para demonstrar a base de indução, uma
vez que p(n) é falso para todo n. Veja que n2 + n = n(n+ 1) é sempre par:
se n for par, então o produto n(n + 1) é múltiplo de 2; se se n for ímpar,
então n+ 1 é par e o produto n(n+ 1) continua sendo múltiplo de 2. Logo,
na˜o p(n) = “n2 + n é par� é verdadeira para todo n ∈ N.
Vamos voltar para o uso correto do PIF.
Exercício 2 Demonstre que o número máximo de movimentos necessários
para resolver o jogo das Torres de Hanoi com n discos é, no máximo, 2n−1.
O jogo das Torres de Hanoi é composto de uma plataforma onde estão
fixados 3 pinos e n discos de tamanhos diferentes que possuem um furo no
meio para encaixarem nos pinos. Regra geral: em qualquer configuração
dos n discos, é proibido haver um disco maior sobre um disco menor. Na
configuração inicial, todos os discos estão encaixados em um dos pinos.
2
n
n−1
2
1
..
.
Cada jogada consiste em mover um disco de um pino para outro, sempre
respeitando a regra geral. O objetivo do jogo é mover todos os discos do
pino original para um dos outros dois pinos.
Seja T (n) o número de movimentos necessários para resolver o jogo das
Torres de Hanói com n discos.
Exemplos:
• com 1 disco, T (1) = 1 movimento (mova o disco do pino origem para
outro pino).
• com 2 discos:
2
1
Início
2 1
1o. movimento
1 2
2o. movimento
1
2
3o. movimento
T (2) ≤ 3 (para provar que T (2) = 3, precisaríamos demonstrar que
não dá para resolver em menos do que 3 movimentos)
Podemos refrasear o enunciado do exercício como: demonstre que T (n) ≤
2n − 1 para todo n ≥ 1.
Demonstração. Consideremos a proposição p(n) = “T (n) ≤ 2n − 1.′′
Vamos demonstrá-la para n ≥ 1 usando o PIF.
Base de indução: p(1) é verdadeira?
Ou seja, queremos saber se vale T (1) ≤ 21 − 1. Isto é verdade, pois para
resolver o problema para apenas 1 disco, basta movê-lo para outro pino (1
movimento).
Passo de indução: p(n)⇒ p(n+ 1) ?
Suponha que p(n) é verdadeiro, ou seja, T (n) ≤ 2n − 1, o que significa
que podemos resolver o problema para n discos em, no máximo, 2n − 1
3
movimentos. Como podemos usar este fato para resolver o problema para
n+ 1 discos?
n+1
n
2
1
..
.
Início
n+1
n
2
1
..
.
T(n) mov.
Mova os n discos menores para
outro pino
n+1
1 mov.
n
2
1
..
.
Mova disco maior para pino não
ocupado
n
2
1
..
.
n+1
T(n) mov.
Mova os n discos menores para
cima do disco maior
De acordo com o raciocínio mostrado no diagrama acima, podemos re-
solver o problema das torres de Hanoi com n+1 discos usando, no máximo,
T (n) + 1 + T (n) movimentos, ou seja:
T (n+ 1) ≤ 2T (n) + 1
T (n+ 1) ≤ 2(2n − 1) + 1
T (n+ 1) ≤ 2 · 2n − 2 + 1
T (n+ 1) ≤ 2n+1 − 1
A última desigualdade demonstra que p(n+ 1) é válida. �
1.2 Versão Forte
Exercício 3 Demonstre que todo número natural maior ou igual a dois é
primo ou produto de primos.
Demonstração. Seja p(n) = “n é primo oun é produto de primos′′. Usa-
remos o PIF para demonstrar que p(n) é verdadeira para n ≥ 2.
Base de indução: p(2) é verdade? Sim, pois 2 é primo.
Passo de indução: p(n)⇒ p(n+ 1)?
Assuma que p(n) é válida, ou seja, que n é primo oun é produto de primos.
O que podemos falar de n+ 1?
Se n+1 for primo, p(n+1) já é verdade e não há mais nada a demonstrar.
Caso contrário, n + 1 não é primo, o que significa que n + 1 é múltiplo de
algum natural a, ou seja
n+ 1 = a · k para algum k ∈ N
4
Note que, tanto a quanto k não podem ser maiores do que n+ 1, pois caso
contrário, o produto seria maior do que n+ 1. Ambos tampouco podem ser
iguais a n + 1, pois isto implicaria que o outro número é igual a 1, o que
resultaria em n + 1 primo, pois ele só seria divisível por n + 1 e 1, o que
contradiria o fato de n+ 1 não ser primo.
Portanto, temos n+ 1 = a · k, onde a ≤ n e k ≤ n.
Vamos interromper a demonstração por um momento para observar que,
com a versão fraca do PIF, nada podemos afirmar sobre a nem sobre k, já
que a única hipótese é que n é primo ou produto de primos. Se a < n ou
k < n, fica difícil usar a versão fraca.
Nestes casos, usamos uma outra versão do PIF, chamada de versão forte.
Definição 2 (Versão forte do Princípio da Indução Finita) Seja p(n)
uma proposição aberta no universo dos números naturais.
SE valem ambas as propriedades abaixo:
• (Base de indução) p(n0) é verdadeira para algum n0 ∈ N
• (Passo de indução) p(n0) e p(n0 + 1) e . . . p(n− 1) e p(n)⇒ p(n+ 1)
para todo n ≥ n0
ENTÃO p(n) é verdadeira para todo n ≥ n0.
Note que a única diferença entre a versão fraca e a versão forte é que
na versão forte podemos assumir como verdadeiras as proposições p(n0),
p(n0 + 1), . . . , p(n− 1), p(n).
Retornando à demonstração anterior, vamos reescrever o passo de indu-
ção (não precisamos mexer na demonstração da base de indução pois ela é
idêntica para as duas versões).
Retornando à demonstração do Exercício 3:
Passo de indução: p(n0) e p(n0 + 1) e . . . p(n− 1) e p(n)⇒ p(n+ 1) ?
Assuma que são verdadeiras p(n0), p(n0+1), . . . , p(n), ou seja, que todos
os números naturais entre n0 e n são primos ou produtos de primos.
Como já visto anteriormente, se n+1 não é primo, então n+1 = a·k, onde
a, k são números naturais entre 2 e n. Pela hipótese do passo de indução,
tanto a quanto k são inteiros ou produto de primos, logo a · k é produto de
primos. �
5