Livro Texto 2 - Matemática Discreta

Prévia do material em texto

41
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
Unidade II
5
10
15
20
25
30
35
4 O PRINCÍPIO DA CASA DO POMBO (OU PCP)
O nome deste princípio advém do fato de que se houver n 
casinhas de pombos e nelas pousarem mais do que n pombos, 
então, pelo menos, em uma casa haverá mais de um pombo.
4.1 Formulações
Podemos formular este princípio de forma menos pitoresca:
Princípio da casa do pombo (coloquial)
“Se mais do que n objetos forem distribuídos em n caixas, 
então haverá pelo menos uma caixa com mais do que um 
objeto.”
Também podemos formular tal princípio na linguagem 
matemática de duas maneiras equivalentes:
Princípio da casa do pombo (formal 1)
Sejam A e B conjuntos finitos, e ƒ : A → B uma função.
Se |B| < |A|, então ƒ não é injetora.
Princípio da casa do pombo (formal 2)
Sejam A e B conjuntos finitos, e ƒ : A → B uma função.
Se |A| < |B|, então ƒ não é sobrejetora.
42
Unidade II
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
No enunciado formal, o conjunto A corresponderia ao 
conjunto dos pombos, o conjunto B corresponderia ao conjunto 
das casinhas, e a função ƒ faria o papel de alocar cada pombo 
em uma casinha.
4.2 Exemplos
Exemplo 1
Qual o número mínimo de pessoas que devem estar em uma 
sala de aula para que haja certeza de que, ao menos, duas delas 
tenham o nome iniciado com a mesma letra? (Suponha que o 
alfabeto tenha 26 letras.)
Solução
Como existem 26 letras possíveis para a inicial, pelo princípio 
da casa do pombo devem existir ao menos 27 pessoas.
(Neste problema, as 26 letras fazem o papel das “casas”; e as 
27 pessoas, o lugar do “pombos”.)
Observação
No exemplo 1, assim como em muitos outros, será sempre 
útil raciocinar a partir do pior caso. Assim como o problema 
pergunta qual o número mínimo de pessoas que devem estar 
em uma sala para que haja certeza de que ao menos duas delas 
tenham o nome iniciado com a mesma letra, devemos pensar 
que, no pior caso, 26 pessoas poderiam ter as iniciais diferentes, 
pois existem 26 letras disponíveis, mas a próxima pessoa, com 
certeza, teria uma inicial repetida.
Exemplo 2
Qual o número mínimo de pessoas que devem ser reunidas 
para garantir que ao menos duas delas fazem aniversário no 
mesmo dia? (Considere um ano com 365 dias.)
43
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
Solução
Como existem 365 dias possíveis para a data de aniversário, 
pelo PCP devem ser reunidas ao menos 366 pessoas.
Exemplo 3
Quantas vezes um dado deve ser lançado para termos certeza 
de que cairão números repetidos?
Solução
Como existem 6 possibilidades para o lançamento de um 
dado, pelo PCP devemos lançar o dado ao menos 7 vezes.
Exemplo 4
Um baralho é constituído por 52 cartas, divididas da seguinte 
forma: possui quatro naipes (copas, ouros, paus e espadas), e 
cada um dos naipes possui os seguintes valores: A (Ás), 2, 3, 4, 5, 
6, 7, 8, 9, 10, J (Valete), Q (Dama) e K (Rei).
Os naipes de copas e ouros são figuras vermelhas e os 
naipes de paus e espadas, figuras pretas. Quantas cartas devem 
ser retiradas de um baralho para garantirmos que sairão, ao 
menos:
a) Duas cartas do mesmo naipe?
b) Uma carta vermelha?
c) Um Rei?
d) Dois Reis?
e) Duas cartas pretas?
f) Três cartas do mesmo naipe?
g) Duas Damas?
44
Unidade II
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
h) Duas cartas de mesmo valor independentemente do naipe?
i) Sete números?
j) Três letras pretas?
Solução
a) Como são quatro naipes possíveis, pelo PCP, devemos 
retirar 5 cartas.
b) Como dois naipes são vermelhos e dois são pretos, existem 
26 cartas vermelhas e 26 cartas pretas. Pelo PCP, devemos, 
então, retirar 27 cartas.
c) Como em 52 cartas apenas 4 são Reis, podemos retirar 
52 - 4 = 48 cartas que não são Reis. Pelo PCP, devemos, 
então, retirar 49 cartas.
d) Como acima, podemos retirar 52 - 4 = 48 cartas que não 
são Reis. Pelo PCP, devemos, então, retirar 48 + 2 = 50 
cartas.
e) Existem 26 cartas vermelhas e 26 cartas pretas. No 
pior caso, podemos tirar 26 cartas vermelhas e uma 
preta (independentemente da ordem) e a próxima bola 
será, obrigatoriamente, preta. Portanto, serão 28 cartas 
retiradas.
f) Existem quatro naipes. No pior caso, podemos retirar 
oito cartas de três naipes, sem haver repetição. Portanto, 
devemos retirar nove cartas.
g) De 52 cartas apenas quatro são Damas, portanto, podemos 
retirar uma Dama e 52 - 4 = 48 cartas que não são 
Damas e, independentemente da ordem, a próxima carta 
a ser retirada deverá ser, obrigatoriamente, uma Dama. 
Portanto, devemos retirar 50 cartas.
h) Existem 13 valores possíveis, então após 14 retiradas 
haverá repetição de algum valor.
45
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
i) Cada naipe possui quatro letras e nove números, de forma 
que o baralho possui 4.4 = 16 letras e 4.9 = 36 números. 
Podemos, então, no pior caso, retirar as 16 letras e, em 
seguida, serão retirados, obrigatoriamente, os números. 
Pelo PCP, devemos retirar 16 + 7 = 23 cartas.
j) Podemos, no pior caso, retirar todas as 26 cartas vermelhas. 
Em seguida, podemos retirar todos os 18 números pretos 
e, posteriormente, retirar as três letras pretas. Portanto, 
pelo PCP, devemos retirar 47 cartas.
Exemplo 5
Quantos números devem ser escolhidos no conjunto A = {1, 
2, 3, 4, 5, 6}, sem repetição, para garantir que, pelo menos, um 
par de números tenha soma ímpar?
Solução
Se retirarmos, primeiramente, um número par, poderemos, 
no pior caso, escolher posteriormente mais dois números pares, 
para, somente na quarta escolha, podermos escolher um número 
ímpar, resultando, então, em uma soma ímpar.
Analogamente, se retirarmos um número ímpar, poderemos, 
no pior caso, escolher, a seguir, mais dois números ímpares, para, 
somente na quarta escolha, podermos escolher um número 
par, resultando, então, em uma soma ímpar. Em qualquer caso, 
precisamos, então, de quatro escolhas.
Exemplo 6
Quantos números devem ser escolhidos no conjunto A = {1, 
2, 3, 4, 5, 6} para garantir que, se escolhermos dois números sem 
repetição desse subconjunto, pelo menos, um par de números 
tenha soma 7?
46
Unidade II
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
Solução
Notemos que os pares de números do conjunto A, cuja 
soma resulte em 7, são {1,6} , {2,5} e (3,4}. Se retirarmos um 
número qualquer, poderemos, no pior caso, escolher um número 
de outra dupla e depois outro número da terceira dupla, e na 
próxima escolha, obrigatoriamente, ele cairá em uma das duplas 
já ocupadas por um número, ou seja, se escolhermos quatro 
números do conjunto A, necessariamente um dos pares terá o 
número sete como soma.
5 O PRINCÍPIO DE INDUÇÃO FINITA
5.1 Introdução
Observemos as seguintes situações:
Situação 1
Um gerente de uma firma precisa de uma função que 
gere números primos, e pede a um funcionário que encontre 
determinada função. Após muito trabalho, ele chega à seguinte 
função ƒ : IN → IN dada por ƒ(n) = n2 - n + 41. Começa, então, 
a testar alguns números:
ƒ(0) = 41
ƒ(1) = 41
ƒ(2) = 43
ƒ(3) = 47
ƒ(4) = 53
ƒ(5) = 61
ƒ(6) = 71
ƒ(7) = 83
47
MATEMÁTICADISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
ƒ(8) = 97
ƒ(9) = 113
ƒ(10) = 131
Após testar mais alguns números e verificar que, de fato, 
ƒ(n) são todos números primos, é convencido e faz a seguinte 
afirmação ao seu patrão:
Afirmação 1: “Considere a função ƒ : IN → IN dada por 
ƒ(n) = n2 - n + 4
Então, ∀n ∈ IN, ƒ(n) é um número primo.”
Situação 2
Um gerente de uma firma precisa de uma função que some 
os n primeiros números ímpares, e pede a um funcionário que 
encontre determinada função. O funcionário faz, então, algumas 
observações:
 n Soma dos n primeiros ímpares
1 1
2 1 + 3 = 4
3 1 + 3 + 5 = 9
4 1 + 3 + 5 + 7 = 16
5 1 + 3 + 5 + 7 + 9 = 25
6 1 + 3 + 5 + 7 + 9 + 11 = 36
7 1 + 3 + 5 + 7 + 9 + 11 + 13 = 49
8 1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 = 64
9 1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 = 81
10 1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 + 19 = 100
Após um pouco de reflexão, ele percebe que a função ƒ : 
IN* → IN, dada por ƒ(n) = n2, é a função pedida. Apresenta-a, 
então, ao seu patrão e faz a seguinte afirmação:
48
Unidade II
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
Afirmação 2
“∀n ∈ IN*, a soma dos n primeiros números ímpares, é dada 
pela função ƒ : IN* → IN, dada por ƒ(n) = n2”.
Você agiria da mesma forma que esses funcionários agiram? 
Arriscaria seu emprego? O grande problema dessas afirmações 
é que são afirmações sobre um número infinito de termos, e 
alguns testes, ou mesmo um grande número de testes, não 
garante a veracidade das afirmações.
De fato, a afirmação 1 é falsa, basta tomar n = 41 e obteremos 
ƒ(41) = 412 - 41 + 41 = 412, que, obviamente, não é um número 
primo, já que é divisível por 41.
Já a segunda afirmação é verdadeira, e será provada no 
exemplo1.
É claro que um grande número de testes não aumenta a 
segurança da afirmação, para ver isso, basta tomar a seguinte 
afirmação: ∀n ∈ IN : n ≤ 10001000.
A afirmação será verdadeira para os primeiros 10001000 
números, mas falhará quando n = 10001000 + 1.
Uma ferramenta matemática utilizada para provar tais 
afirmações (quando verdadeiras, evidentemente) é o Princípio 
de Indução Finita, que enunciaremos a seguir.
5.2 Princípio de Indução Finita (PIF fraco)
Seja A(n) uma afirmação sobre um número natural n 
arbitrário. Se provarmos:
1) A(0)
49
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
2) ∀k [A(k) → A(k + 1)]
Então, ∀nA(n).
Observação 1
O item 1, acima, é chamado de base da indução e mostra 
que a afirmação vale para o primeiro número natural, mas 
a afirmação pode valer apenas a partir de um certo número 
natural n0, e, nesse caso, a hipótese de indução toma a forma 
A(n0).
Observação 2
O item 2 é chamado de Passo Indutivo e a suposição A(k), 
no antecedente da implicação, é chamada de Hipótese de 
Indução (HI), e devemos utilizá-la para mostrar o consequente 
da implicação A(k + 1), que será chamado de tese.
Observação 3
O Princípio de Indução Finita pode também ser apresentado 
em versão conjuntista.
5.3 Princípio de Indução Finita (PIF) – versão 
conjuntista
Seja S um subconjunto dos números naturais IN, tal que:
1) 0 ∈ S
2) ∀k [k ∈ S → k + 1 ∈ S]
Então, S = IN.
(São válidas, nesse caso, as mesmas observações e 
nomenclaturas citadas anteriormente.)
50
Unidade II
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
5.4 Exemplos – (PIF fraco)
Exemplo 1
Prove, usando o PIF, que ∀n > 1 : A(n), onde A(n) é a seguinte 
afirmação:
 1 3 5 7 2 1 2 1
2
1
2+ + + + + − = − =
=
∑............. ( ) ( , . )n n i n
i
n
ou seja
Solução
1) Base (n = 1):
Na expressão do lado esquerdo, para n = 1, obtemos 
2 1 2 1 1 1
1
1
. .i
i
− = − =
=
∑ , e, na expressão do lado direito, obtemos 
12 = 1, portanto A(1) é verdadeira.
2) Hipótese de indução (HI): 
1 3 5 7 2 1 2+ + + + + − =............. ( )k k
3) Tese: 
1 3 5 7 2 2 1 1 12+ + + + + + + − = +............. . [ .( ) ] ( )k k k
4) Vamos mostrar nossa tese:
1 3 5 7 2 2 1 1 2 1 12 2+ + + + + + + − = + + − = +............. . [ .( ) ] [ .( ) ]k k k k kHI 22 1 12. ( )k k+ = +
5) Portanto, pelo PIF, ∀ ≥n A n1: ( ) .
Exemplo 2
Prove, usando o PIF, que ∀ ≥n A n1: ( ) , onde A(n) é a seguinte 
afirmação: 1 2 3 4
1
2
+ + + + + = +................ .( )n n n (ou seja, 
i
n n
i
n
=
∑ = +
1
1
2
.( )
)
51
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
Solução
1) Base (n = 1):
Na expressão do lado esquerdo, para n = 1, obtemos i
i=
∑ =
1
1
1, 
 e, na expressão do lado direito, obtemos 
1 1 1
2
2
2
1
.( )+ = = , 
portanto A(1) é verdadeira.
2) Hipótese de indução (HI): 
1 2 3 4
1
2
+ + + + + = +................ .( )k k k
3) Tese: 
1 2 3 4 1
1 2
2
+ + + + + + + = + +................ ( ) ( ).( )k k k k
4) Vamos mostrar nossa tese:
1 2 3 4 1
1
2
1
1+ + + + + + + = + + + = + +................ ( ) .( ) ( ) .( )k k k k k k kHI 22 1
2
1 2
2
.( ) ( ).( )k k k+ = + +
5) Portanto, pelo PIF, ∀ ≥n A n1: ( ) .
Exemplo 3
Prove, usando o PIF, que ∀ ≥n A n1: ( ) , onde A(n) é a seguinte 
afirmação: 2 2 2 2 2 2 10 1 2 3 1+ + + + + = −−.............. n n (ou seja, 
2 2 11
1
i
i
n
n−
=
∑ = − )
Solução
1) Base (n = 1):
Na expressão do lado esquerdo, para n = 1, obtemos 
2 2 2 11
1
1
1 1 0i
i
−
=
−∑ = = = , e, na expressão do lado direito, 
obtemos 21 - 1 = 2 - 1 = 1, portanto A(1) é verdadeira.
52
Unidade II
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
2) Hipótese de indução (HI): 
2 2 2 2 2 2 10 1 2 3 1+ + + + + = −−.............. k k
3) Tese: 
2 2 2 2 2 2 2 10 1 2 3 1 1+ + + + + + = −− +.............. k k k
4) Vamos mostrar nossa tese:
2 2 2 2 2 2 2 1 2 2 2 1 2 10 1 2 3 1 1+ + + + + + = − + = − = −− +.............. .k k HI k k k k
5) Portanto, pelo PIF, ∀ ≥n A n1: ( ) .
Exemplo 4
Prove, usando o PIF, que ∀ ≥n A n1: ( ) , onde A(n) é a seguinte 
afirmação: 1
1 2
1
2 3
1
3 4
1
4 5
1
1 1. . . .
.............
.( )
+ + + + +
+
=
+n n
n
n
 
(ou seja, 1
1 11 i i
n
ni
n
.( )+
=
+=
∑ )
Solução
1) Base (n = 1):
Na expressão do lado esquerdo, para n = 1, obtemos 
1
1
1
1 1 1
1
21
1
i ii .( ) .( )+
=
+
=
=
∑ , e, na expressão do lado direito, 
obtemos 
1
1 1
1
2+
= , portanto A(1) é verdadeira.
2) Hipótese de indução (HI): 
1
1 2
1
2 3
1
3 4
1
4 5
1
1 1. . . .
.............
.( )
+ + + + +
+
=
+k k
k
k
53
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
3) Tese: 
1
1 2
1
2 3
1
3 4
1
4 5
1
1
1
1 2. . . .
.............
.( ) ( ).( )
+ + + + +
+
+
+ +
= +
k k k k
k 11
2k +
4) Vamos mostrar nossa tese:
1
1 2
1
2 3
1
3 4
1
4 5
1
1
1
1 2. . . .
.............
.( ) ( ).( )
+ + + + +
+
+
+ +
=
k k k k
HI kk
k k k
k k
k k
k k
k k
+
+
+ +
=
= + +
+ +
= + +
+ +
1
1
1 2
2 1
1 2
2 1
1 2
2
( ).( )
.( )
( ).( ) ( ).( ))
( )
( ).( )( )
( )
= +
+ +
= +
+
k
k k
k
k
1
1 2
1
2
2
5) Portanto, pelo PIF, ∀ ≥n A n1: ( ) .
Exemplo 5
Prove, usando o PIF, que ∀ ≥n A n1: ( ) , onde A(n) é a seguinte 
afirmação: n < 2n
Solução
1) Base (n = 1): 1 < 2 = 21 Ok.
2) Hipótese de indução (HI): k < 2k (onde k ≥ 1)
3) Tese: k + 1 < 2k+1
4) Vamos mostrar nossa tese:
k HI k k k k k+ < + < + = = +1 2 1 2 2 2 2 2 1.
5) Portanto, pelo PIF, ∀ ≥n A n1: ( ) .
Exemplo 6
Prove, usando o PIF, que ∀ ≥n A n1: ( ) , onde A(n) é a seguinte 
afirmação: 7 2 13| n − .
54
Unidade II
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
Observação
7 2 13| n − lê-se: “7 2 13divide n − ”.
Lembremos que em IN: b a b e c IN a b c| : .⇔ ≠ ∃ ∈ =0 .
Solução
1) Base (n = 1): 2 1 2 1 8 1 73 1 3. − = − = − = , portanto 
7 2 13 1| . − Ok.
2) Hipótese de indução (HI): 7 2 13| .k −
3) Tese: 7 2 13 1| .( )k+ −
4) Vamos mostrar nossa tese:
2 1 2 1 2 2 1 8 2 1 7 1 2 1 7 23 1 3 3 3 3 3 3 3.( ) . . . . .. . ( ). .k k k k k k+ +− = − = − = − = + − = ++ −2 13.k
por HI, 7 2 13| .k − , e, obviamente, 7 7 23| . .k , logo 
7 7 2 2 13 3| . . .k k+ − .
Ou seja, 7 2 13 1| .( )k+ − .
5) Portanto, pelo PIF, ∀ ≥n A n1: ( ) .
Observação
O Princípio de Indução Finita pode ser apresentado em 
outra versão, o chamado Princípio de Indução Finita Forte, 
que enunciaremos a seguir.
5.5 Princípio de Indução Finita Forte (PIF forte)
Seja A(n) uma afirmação sobre um número natural n 
arbitrário. Se provarmos:
55
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
1) A(0)
2) ∀k [∀t (t ≤ k → A(t)) → A(k + 1)]
Então, ∀n A(n).
A diferença entre as duas versões é que, se queremos provar 
∀n A(n), no Passo Indutivo, o Princípio de Indução Finita parte da 
suposição A(k), onde k é um número arbitrário, e o Princípio de 
Indução Finita Forte parte da suposição de que não apenas A(k) é 
válido, mas que A(n) é válido para todos os valores menores que k.
Observação 1
A diferença entre as duas versões é que, se queremos provar 
∀n A(n), no Passo Indutivo, o Princípio de Indução Finita parte da 
suposição A(k), onde k é um número arbitrário. Já o Princípio de 
Indução Finita Forte parte da suposição de que não apenas A(k) 
é válido, mas que A(n) é válido para todos os valores menores 
que k.
Observação 2
Os dois princípios são equivalentes, ou seja, o que conseguimos 
provar com um, conseguimos provar com o outro.
5.6 Exemplos (PIF forte)
Exemplo 1 (Teorema Fundamental da Aritmética-
existência)
Prove que todo número natural n ≥ 2 ou é primo ou pode ser 
escrito como um produto de primos.
Solução:
1) Base (n = 2): Como 2 é primo, Ok.
56
Unidade II
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
2) Hipótese de indução (HI):
“Seja k ≥ 2. Então, todo número 1 ≤ k ou é um número primo 
ou pode ser decomposto como produto de números primos”.
3) Tese: k + 1 é um número primo ou pode ser decomposto 
como produto de números primos.
4) Vamos mostrar nossa tese:
Se k + 1 é um número primo, está provado.
Se k + 1 não é um número primo, então, é um produto de 
dois números a e b , onde a ≤ k ≤ e b ≤ k.
Então, como a ≤ k e b ≤ k, por HI, a e b são primos ou são 
produto de primos.
Seja, então, a = a1 . a2.........ar, com r ≥ 1 e b = b1 . b2.........bs, 
com s ≥ 1, onde a1 . a2.........ar, b1 . b2.........bs são números primos.
Então, k ab a a a b b br s+ = =1 1 2 1 2. . ........ . . ........ , ou seja, k + 1 é 
um produto de números primos.
5) Portanto, pelo PIF Forte, todo número natural n ≥ 2 ou é 
primo ou pode ser escrito como produto de números primos.
Exemplo 2
Prove que todo número natural maior que zero pode 
ser escrito como uma soma de potências de 2 distintas. 
Por exemplo: 15 2 2 2 23 2 1 0= + + + e 24 2 24 3= + e 
31 2 2 2 2 24 3 2 1 0= + + + + .
Solução
1) Base (n = 1): Basta notar que 1 = 20. Ok
57
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
2) Hipótese de indução (HI):
Todo número l k≤ pode ser escrito como uma soma de 
potências de 2 distintas.
3) Tese: k + 1 pode ser escrito como uma soma de potências 
de 2 distintas.
4) Vamos mostrar nossa tese:
Se k + 1 é uma potência de 2, está provado.
Se k + 1 não é uma potência de 2, por HI, k pode ser escrito 
como uma soma de potências de 2 distintas, ou seja, para algum 
m ≥ 1, temos que k ai
i
m
i=
=
∑
0
2. , onde a ou ai i= =0 1, mas 
com am = 1.
Vamos definir uma nova sequência bn:
Primeiramente, vamos estender a sequência an considerando 
am+ =1 0 .
Então, na decomposição k ai
i
m
i=
=
+
∑
0
1
2. , seja i0 o primeiro 
índice, tal que ai0 0= .
Definimos, então, a sequência bn da seguinte forma:
b se i i
b
b a se i i
i
i
i i
= <
=
= >





0
1
0
0
0
Então, k a a bHI i
i
m
i
i
i
m
i
i
i
m
+ =





 + =





 + =
=
+
=
+
=
+
∑ ∑1 2 1 2 2
0
1
0
1
0
0
1
. . *∑∑ .2i 
onde b ou bi i= =0 1.
Obs.: * decorre da definição da sequência bi.
58
Unidade II
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
5) Portanto, pelo PIF Forte, todo número natural n ≥ 2 ou é 
primo ou pode ser escrito como produto de primos.
Observação
Neste último exemplo, o conceito de indução, que é o que 
nos importa, é aparente. A parte final, envolvendo somatórios, é 
apenas um artifício para não haver repetição nas potências de 2. 
Para melhor visualizar, vamos ver alguns exemplos, lembrando 
que queremos adicionar 1 (ou seja, 20) a uma dada decomposição 
de k.
Exemplo 1
Vamos adicionar 20 a k = + + +2 2 2 25 3 1 0 . Temos, então:
k + = + + + + = + + + = + + + = + + =1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 25 3 1 0 0 5 3 1 0 5 3 1 1 5 3 1( ) . . 22 2 25 3 2+ +
Exemplo 2
Vamos adicionar 20 a k = + +2 2 26 3 0 . Temos, então:
k + = + + + = + + = + +1 2 2 2 2 2 2 2 2 2 2 26 3 0 0 6 3 0 6 3 1( ) .
Exemplo 3
Vamos adicionar 20 a k = + + + +2 2 2 2 24 3 2 1 0 . Temos, 
então:
k + = + + + + + = + + + + = + + + + =1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
2
4 3 2 1 0 0 4 3 2 1 0 4 3 2 1 1
4
( ) .
++ + + = + + + = + + = + + = + =
= +
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
2 2
3 2 1 4 3 2 2 4 3 2 4 3 3 4 3
4
. . .
44 4 52 2 2= =.
59
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
6 RECURSÃO
6.1 Definições
A recursão é um processo construtivo de obtenção de certos 
objetos a partir de outros obtidos em passos anteriores. Mais 
precisamente, dizemos que uma função F, com domínio nos 
números naturais, é definida recursivamente, supondo que seja 
conhecida uma função G, que satisfaz o seguinte esquema:
F c
F n G n F n se n
( )
( ) ( , ( )) ,
0
1 1
=
= − ≥




Observação 1
A expressão F(0) = c é denominada base da recursão, e c 
representa um valor fixado.
Observação 2
No esquema acima, tomamos como argumento inicial o 
número zero, mas poderíamos escolher outro, por exemplo: 
F(1).
Observação 3
Poderíamos escrever o esquema acima da seguinte forma:
F c
F n G n F n se n
( )
( ) ( , ( )) ,
0
1 0
=
+ = ≥



Frequentemente, utilizaremos ambas as formas.
60
Unidade II
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
Observação 4
O esquema acima pode ser escrito de forma mais completa:
F x x f x x
F n x x G n F n
n n
n
( , , ....., ) ( , ....., )
( , , ....., ) ( , (
0
1
1 1
1
=
= − −11 11 1, , ....., ), , ....., ),x x x x se nn n ≥




Mas, para a maioria das nossas aplicações, o primeiro 
esquema será suficiente.
6.2 Exemplos
Exemplo 1
A função multiplicação de um número natural por um número 
a fixo, supondo a soma conhecida, é definida recursivamente 
por:
a
a b ab a
.
.( ) .
0 0
1
=
+ = +



Exemplo 2
A função potência com base a fixo, supondo a multiplicação 
conhecida, é definida recursivamente por:
a
a a ab b
0
1
1=
=



 + .
Exemplo 3
A função fatorial, supondo a multiplicação conhecida, é 
definida recursivamente por:
0 1
1 1
!
( )! ( ). !
=
+ = +


 a a a
61
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
Exemplo 4
A função somatória de uma dada sequência ai, supondo a 
soma conhecida, é definida recursivamente por:
a a
a a a
i
i
i
i
n
i
i
n
n
=
=
+
=
+
∑
∑ ∑
=
= +









0
0
0
0
1
0
1
Exemplo 5
Dada a seguinte função F , definida por recursão, escreva os 
6 primeiros termos gerados:
F
F n F n se n
( )
( ) . ( ) ,
1 2
2 1 2
=
= − ≥



Solução:
F
F F F
F F F
( )
( ) . ( ) . ( ) .
( ) . ( ) . ( ) .
1 2
2 2 2 1 2 1 2 2 4
3 2 3 1 2 2 2 4 8
=
= − = = =
= − = = =
FF F F
F F F
F
( ) . ( ) . ( ) .
( ) . ( ) . ( ) .
(
4 2 4 1 2 3 2 8 16
5 2 5 1 2 4 2 16 32
= − = = =
= − = = =
66 2 6 1 2 5 2 32 64) . ( ) . ( ) .= − = = =F F
Exemplo 6
Dada a seguinte função F, definida por recursão, escreva os 6 
primeiros termos gerados:
F
F n F n n se n
( )
( ) ( ) ,
1 1
1 22
=
= − + ≥




62
Unidade II
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
Solução
F
F F F
F F F
( )
( ) ( ) ( )
( ) ( ) ( )
1 1
2 2 1 2 1 4 1 4 5
3 3 1 3 2 9 5 9
2
2
=
= − + = + = + =
= − + = + = + ==
= − + = + = + =
= − + = + =
14
4 4 1 4 3 16 14 16 30
5 5 1 5 4 25
2
2
F F F
F F F
( ) ( ) ( )
( ) ( ) ( ) 330 25 55
6 6 1 6 5 36 55 36 912
+ =
= − + = + = + =F F F( ) ( ) ( )
Exemplo 7
Dada a seguinte função F, definida por recursão, escreva os 6 
primeiros termos gerados:
F
F n
F n
sen
( )
( )
( )
,
1 2
1
1
2
=
=
−
≥




Solução
F
F
F F
F
F F
F
F
( )
( )
( ) ( )
( )
( ) ( )
( )
1 2
2
1
2 1
1
1
1
2
3
1
3 1
1
2
1
1
2
2
4
1
=
=
−
= =
=
−
= = =
=
(( ) ( )
( )
( ) ( )
( )
( ) ( )
4 1
1
3
1
2
5
1
5 1
1
4
1
1
2
2
6
1
6 1
1
5
−
= =
=
−
= = =
=
−
= =
F
F
F F
F
F F
11
2
63
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
Exemplo 8
Dada a seguinte função F, definida por recursão, escreva os 6 
primeiros termos gerados:
F
F n F n n se n
( )
( ) ( ) ,
1 1
1 22
=
= − + ≥




Solução
F
F F F
F F F
( )
( ) ( ) ( )
( ) ( ) ( )
1 1
2 2 1 2 1 4 1 4 5
3 3 1 3 2 9 5 9
2
2
=
= − + = + = + =
= − + = + = + ==
= − + = + = + =
= − + = + =
14
4 4 1 4 3 16 14 16 30
5 5 1 5 4 25
2
2
F F F
F F F
( ) ( ) ( )
( ) ( ) ( ) 330 25 55
6 6 1 6 5 36 55 36 912
+ =
= − + = + = + =F F F( ) ( ) ( )
Exemplo 9 (Sequência de Fibonacci)
Dada a seguinte função F, definida por recursão, escreva os 6 
primeiros termos gerados:
F
F
F n F n F n se n
( )
( )
( ) ( ) ( ),
1 1
2 2
1 2 3
=
=
= − + − ≥




 (sequência de Fibonacci)
Observação:
Esta importante sequência é definida com base dupla, ou 
seja, são dados os valores de F(1) e F(2).
64
Unidade II
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
Solução
F( )1 1=
F
F F F F F
F F F
( )
( ) ( ) ( ) ( ) ( )
( ) ( ) ( )
2 2
3 3 1 3 2 2 1 2 1 3
4 4 1 4 2
=
= − + − = + = + =
= − + − == + = + =
= − + − = + = + =
=
F F
F F F F F
F F
( ) ( )
( ) ( ) ( ) ( ) ( )
( ) (
3 2 3 2 5
5 5 1 5 2 4 3 5 3 8
6 66 1 6 2 5 4 8 5 13− + − = + = + =) ( ) ( ) ( )F F F
Exemplo 10
Escreva uma função recursiva que gere a seguinte sequência 
(estão listados em ordem crescente de índices, ou seja, 
a a a a1 2 3 4, , , , ....... ): 1 3 9 27 81, , , , , .......
Solução
F
F n F n se n
( )
( ) . ( ),
1 1
3 1 2
=
= − ≥



Exemplo 11
Escreva uma função recursiva que gere a seguinte sequência 
(estão listados em ordem crescente de índices, ou seja, 
a a a a1 2 3 4, , , , ....... ): 2 4 16 256, , , , ............
Solução
F
F n F n se n
( )
( ) ( ),
1 2
1 22
=
= − ≥




Exemplo 12
Escreva uma função recursiva que gere a seguinte sequência 
(estão listados em ordem crescente de índices, ou seja, 
a a a a1 2 3 4, , , , .......) : 1 2 4 7 11 16 22, , , , , , , ...........
65
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
Solução
F
F n F n n se n
( )
( ) ( ) ( ),
1 1
1 1 2
=
= − + − ≥



Exemplo 13
Uma colônia de bactérias tem inicialmente uma população 
de 50.000 bactérias.
Sabe-se que a cada hora o número de bactérias triplica.
Escreva uma definição recursiva para B(n) = número de 
bactérias no início da n-ésima hora (considere Q(0) = 50000).
Solução
Q
Q n Q n se n
( )
( ) . ( ) ,
0 50000
3 1 1
=
= − ≥



Exemplo 14
Um investidor investiu R$ 600,00 em uma aplicação que 
rende 10% de juros compostos ao ano.
Escreva uma definição recursiva para Q(n) = quantia de 
dinheiro no n-ésimo ano (considere Q(0) = 600,00).
Solução
 
Q
Q n Q n Q n
( ) ,
( ) ( ) , . ( )
0 600 00
1 0 1 1
=
= − + −



ou seja, 
Q
Q n Q n
( ) ,
( ) , . ( )
0 600 00
11 1
=
= −



Exemplo 15 (função de Ackermann)
Dada a seguinte função F, definida por recursão, calcule F(2,1):
F n n
F m F m se m
F m n F m F m n se m
( , )
( , ) ( , ) ,
( , ) ( , ( , )) , ,
0 1
0 1 1 1
1 1
= +
= − ≥
= − − nn≥



 1
66
Unidade II
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
Obs.: Note que a função de Ackermann é uma função de 
duas variáveis.
Solução
1) F F F F F( , ) ( , ( , )) ( , ( , ))2 1 2 1 2 1 1 1 2 0= − − =
2) F F F( , ) ( , ) ( , )2 0 2 1 1 1 1= − =
3) F F F F F( , ) ( , ( , )) ( , ( , ))11 1 1 1 1 1 0 1 0= − − =
4) F F F( , ) ( , ) ( , )1 0 1 1 1 0 1= − =
5) F( , )0 1 1 1 2= + =
6) F( , )1 0 2= (linhas 4, 5)
7) F F( , ) ( , )11 0 2= (linhas 3, 6)
8) F( , )0 2 2 1 3= + =
9) F( , )11 3= (linhas 7, 8)
10) F( , )2 0 3= (linhas 2, 9)
11) F F( , ) ( , )2 1 1 3= (linhas 1, 10)12) F F F F F( , ) ( , ( , )) ( , ( , ))13 1 1 1 3 1 0 1 2= − − =
13) F F F F F( , ) ( , ( , )) ( , ( , ))12 1 1 1 2 1 0 1 1= − − =
14) F F( , ) ( , )12 0 3= (linhas 9,13)
15) F( , )0 3 3 1 4= + =
16) F( , )12 4= (linhas 14,15)
17) F F( , ) ( , )13 0 4= (linhas 12, 16)
18) F( , )0 4 4 1 5= = =
19) F( , )13 5= (linhas 17, 18)
20) F( , )2 1 5= (linhas 11, 19)
Portanto, F( , )2 1 5= .
67
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
6.3 Conjuntos definidos por recursão
De forma análoga, podemos definir um conjunto, 
recursivamente, escolhendo um elemento inicial e definindo 
uma cláusula de pertinência ao conjunto.
Exemplo 1
Definimos recursivamente um conjunto numérico M da 
seguinte forma:
a) 2 ∈ M
b) Se x ∈ M , então x + 3 ∈ M
c) Se x ∈ M , então 2.x ∈ M
Quais dos seguintes números pertencem à M?
a) 1
b) 6
c) 5
d) 3
e) 12
f ) 15
g) 4
Solução
Apenas o número 5.
Exemplo 2
Definimos recursivamente um conjunto numérico M da 
seguinte forma:
68
Unidade II
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
i) 2 ∈ M
ii) 3 ∈ M
iii) Se x ∈ M e y ∈ M , então x .y ∈ M
Quais dos seguintes números pertencem a M?
a) 5
b) 6
c) 4
d) 21
e) 12
f ) 15
g) 24
Solução
6, 4, 12, 24
6.4 Cadeias
Definição
Seja ∑ um conjunto finito de símbolos. Então, ∑* denota o 
conjunto de todas as sequências finitas de símbolos de ∑.
Observação
Entre as sequências de ∑* , deve constar o símbolo λ , que 
denota a sequência vazia.
Definição
Sejam x , y ∈ ∑* . Então a concatenação de x e y é a 
sequência xy.
69
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
Por exemplo: se ∑ = { 0 , 1}, e sejam x a sequência 001010, y a 
sequência 111011, z a sequência 1001 e λ a sequência vazia. Então:
xy é a sequência 001010 111011.
xz é a sequência 001010 1001.
yx é a sequência 111011001010.
zxy é a sequência 1001001010111011.
xλ é a sequência 001010.
λyλ é a sequência 111011.
6.4.1 Exemplos
Exemplo 1
Dado um alfabeto ∑ qualquer, forneça uma definição 
recursiva para | x | = número de símbolos da cadeia x.
Solução
| |
| |
| | | | | |
λ =
∈ ⇒ =
= +




0
1x x
xy x y
Σ
Exemplo 2
Dado um alfabeto ∑ qualquer, forneça uma definição 
recursiva para xR = o reverso da cadeia x. (o reverso de uma 
cadeia x é a cadeia x escrita ao contrário. Por exemplo, se x é a 
cadeia 124557, então, xR é a cadeia 755421).
Solução
λ λR
R
R R R
x x x
xy y x
=
∈ ⇒ =
=






Σ
( )
70
Unidade II
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
6.5 A Torre de Hanói
O problema da Torre de Hanói:
Existem 3 torres (A, B e C) e na torre A existem n discos com 
raios distintos empilhados de forma que seus raios estejam em 
ordem decrescente (ou seja, dado um disco qualquer, o disco 
acima tem raio menor).
O problema da Torre de Hanói consiste em passar todos os 
discos da torre A para a torre C, possivelmente utilizando a torre 
B como auxiliar, obedecendo às seguintes condições:
1) É permitido mover apenas um disco de cada vez.
2) É permitido utilizar qualquer uma das três torres para a 
movimentação dos discos.
3) Em nenhuma etapa, um disco pode ficar em cima de outro 
disco com raio menor.
Para ilustrar, vamos exibir os passos para a solução do jogo 
de Hanói para 3 discos:
Passo zero (posição inicial):
A B C
Passo 1:
A B C
71
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
Passo 2:
A B C
Passo 3:
A B C
Passo 4:
A B C
Passo 5:
A B C
Passo 6:
A B C
72
Unidade II
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
Passo 7 (posição final):
A B C
O problema da Torre de Hanói suscita várias questões:
1) Existe solução?
2) A existência da solução depende do número de discos?
3) Caso exista solução, qual é o menor número de movimentos 
necessários?
Vamos responder a todas essas questões, porém as 
afirmações e suas demonstrações terão caráter intuitivo, 
já que trataremos as torres e os discos como objetos reais, 
embora o problema possa ser formalizado.
6.5.1 Alguns resultados
Teorema 1
Seja n o número de discos.
 ∀ ≥n 1 o problema da Torre de Hanói admite solução.
Dem: Por indução sobre o número de discos.
Base: n = 1.
Se existe apenas um disco, basta transferir o disco da torre 
A para a torre C.
Hipótese de Indução: O problema de Hanói admite 
solução para k discos.
73
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
Mostremos que existe solução para k+1 discos.
De fato, seja D o disco de raio máximo.
Então, D deve ser o último disco, e existem k discos 
empilhados sobre ele.
Por Hipótese de Indução, é possível transferir esses k 
primeiros discos da torre A para a torre B, notando que, 
para isso, não é necessário mover o disco D, e, tampouco, 
D limita qualquer movimento, já que é o de maior raio, e 
admite qualquer outro disco acima dele (ou seja, o disco 
D funciona como o “chão”).
É feita, então, a transferência do disco D para a torre 
C, e depois usando novamente a Hipótese de Indução, 
transfiro os k discos que estão agora na torre B para a 
torre C, empilhado-os sobre o disco D.
Com isso, atingimos a configuração final seguindo as 
especificações pedidas.
O que responde às perguntas 1 e 2.
Para responder à pergunta 3, façamos antes algumas 
observações:
• Chamaremos de movimento qualquer mudança de um 
disco de uma torre para outra torre distinta.
• O Teorema 1 mostrou que ∀ ≥ 1, o problema de Hanói, 
admite solução.
Seja, então, T(n) a função que fornece o menor número 
de movimentos para transferir n discos de uma torre para 
outra torre distinta. É claro que T(n) está bem definida, 
pois mostramos que o problema é solúvel e, obviamente, 
T(n) é limitada inferiormente.
74
Unidade II
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
Teorema 2
Seja T(n) a função que fornece o menor número de 
movimentos para transferir n discos de uma torre para 
outra torre distinta.
Então, 
T
T n T n se n
( )
( ) . ( ) ,
1 1
2 1 1 2
=
= − + ≥



Dem:
Se existe apenas um disco, basta transferir o disco da torre 
A para a torre C.
Logo, T(1) = 1.
Suponhamos que existam n ≥ 2 discos empilhados em A.
Então, primeiramente transferimos os n - 1 primeiros 
discos de A para B. Por definição, foram necessários T(n 
- 1) movimentos. Podemos transferir, portanto, o disco 
de maior raio de A para C, e isso requer apenas um 
movimento. Finalmente, transferimos os n - 1 discos de 
B para C, empilhando-os sobre o disco de maior raio, e, 
para isso, por definição, foram necessários mais T (n - 1) 
movimentos. Portanto, para transferir os n discos de A para 
C foram necessários no total 2 . T (n - 1)movimentos.
Portanto, 
T
T n T n se n
( )
( ) . ( ) ,
1 1
2 1 1 2
=
= − + ≥



Resumindo:
O problema de Hanói admite solução para qualquer número 
n de discos, eo menor número de movimentos possível 
para atingir a configuração final é dado pela função T(n) 
que obedece à seguinte relação de recorrência:
75
MATEMÁTICA DISCRETA
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
T
T n T n se n
( )
( ) . ( ) ,
1 1
2 1 1 2
=
= − + ≥



Forma fechada para a função T(n):
Podemos obter uma expressão não recursiva (forma 
fechada) para T(n).
De fato, calculando alguns valores de T(n) na forma 
recursiva, obtemos:
T
T
T
T
T
T
T
T
T
( )
( )
( )
( )
( )
( )
( )
( )
(
1 1
2 3
3 7
4 15
5 31
6 63
7 127
8 255
9
=
=
=
=
=
=
=
=
))
( )
=
=
511
10 1023T
Observando os valores de n e T(n), podemos conjecturar 
que T(n) =2n - 1.
De fato, tal expressão é válida. É o que demonstraremos, a 
seguir, no Teorema 3.
Teorema 3
Seja T(n) a função que fornece o menor número de 
movimentos para transferir n discos de uma torre para 
76
Unidade II
Re
vi
sã
o:
 A
m
an
da
/A
le
ss
an
dr
o 
- 
Di
ag
ra
m
aç
ão
: L
éo
 -
 2
1/
02
/2
01
1
outra torre distinta. Mostramos no Teorema 2 que T(n) 
pode ser definida recursivamente por:
T
T n T n se n
( )
( ) . ( ) ,
1 1
2 1 1 2
=
= − + ≥



Então, ∀ ≥ = −n T n n1 2 1: ( ) .
Dem: Por indução sobre n.
Base: n = 1.
Então, T( )1 1 2 11= = − . OK
Hipótese de Indução: T k k( ) = −2 1
Mostremos que T k k( )+ = −+1 2 11 :
De fato, T k T kDEF HI k k k( ) . ( ) .( ) .+ = + = − + = − + = −+1 2 1 2 2 1 1 2 2 2 1 2 11
∴ ∀ ≥ = −n T n n1 2 1: ( ) CQD (conforme queríamos 
demonstrar).
Referências bibliográficas
GERSTING, Judith L. Fundamentos matemáticos para a ciência 
da computação. São Paulo: LTC, 2004.
SCHEINERMAN, Edward R. Matemática discreta: uma 
introdução. São Paulo: Saraiva, 2004.