Matemática BásicaAula 6 Matemática Básica 3 Ainda sobre o princípio da indução ﬁnita Vimos que o Princípio da Indução Finita pode ser usada para demonstrar que sentenças

Matemática Básica

Humberto José Bortolossi

Departamento de Matemática Aplicada

Universidade Federal Fluminense

Aula 6

19 de abril de 2012

Aula 6 Matemática Básica 1

Ainda SobreO Princípio da Indução Finita


Ainda sobre o princípio da indução finita

Vimos que o Princípio da Indução Finita pode ser usada para demonstrar que sentençasdo tipo ∀n ∈ N = { 1, 2, 3, . . .}, P(n) são verdadeiras!

Mas, de fato, ele também pode ser usado para demonstrar que sentenças do tipo

∀n ∈ A = { 2, 3, 4, . . .}, P(n)

∀n ∈ B = { 3, 4, 5, . . .}, P(n)

∀n ∈ C = { 0, 1, 2, . . .}, P(n)

∀n ∈ D = {−1, 0, 1, . . .}, P(n)

são verdadeiras! Afinal, em termos dos Axiomas de Peano, os conjuntos A, B, C e Dsão tão bons quanto o conjunto N.





∀n ∈ A = { 2, 3, 4, . . .}, P(n)

∀n ∈ B = { 3, 4, 5, . . .}, P(n)

∀n ∈ C = { 0, 1, 2, . . .}, P(n)

∀n ∈ D = {−1, 0, 1, . . .}, P(n)






∀n ∈ A = { 2, 3, 4, . . .}, P(n)

∀n ∈ B = { 3, 4, 5, . . .}, P(n)

∀n ∈ C = { 0, 1, 2, . . .}, P(n)

∀n ∈ D = {−1, 0, 1, . . .}, P(n)






∀n ∈ A = { 2, 3, 4, . . .}, P(n)

∀n ∈ B = { 3, 4, 5, . . .}, P(n)

∀n ∈ C = { 0, 1, 2, . . .}, P(n)

∀n ∈ D = {−1, 0, 1, . . .}, P(n)






∀n ∈ A = { 2, 3, 4, . . .}, P(n)

∀n ∈ B = { 3, 4, 5, . . .}, P(n)

∀n ∈ C = { 0, 1, 2, . . .}, P(n)

∀n ∈ D = {−1, 0, 1, . . .}, P(n)






∀n ∈ A = { 2, 3, 4, . . .}, P(n)

∀n ∈ B = { 3, 4, 5, . . .}, P(n)

∀n ∈ C = { 0, 1, 2, . . .}, P(n)

∀n ∈ D = {−1, 0, 1, . . .}, P(n)






∀n ∈ A = { 2, 3, 4, . . .}, P(n)

∀n ∈ B = { 3, 4, 5, . . .}, P(n)

∀n ∈ C = { 0, 1, 2, . . .}, P(n)

∀n ∈ D = {−1, 0, 1, . . .}, P(n)






∀n ∈ A = { 2, 3, 4, . . .}, P(n)

∀n ∈ B = { 3, 4, 5, . . .}, P(n)

∀n ∈ C = { 0, 1, 2, . . .}, P(n)

∀n ∈ D = {−1, 0, 1, . . .}, P(n)






∀n ∈ A = { 2, 3, 4, . . .}, P(n)

∀n ∈ B = { 3, 4, 5, . . .}, P(n)

∀n ∈ C = { 0, 1, 2, . . .}, P(n)

∀n ∈ D = {−1, 0, 1, . . .}, P(n)



Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.

Demonstração. A prova será feita por indução. Considere o predicado

P(n) : n2 − n − 6 ≥ 0.

(Passo básico ) Devemos mostrar que P(3) é verdadeira. Em nosso caso, isso significa mostrar que32 − 3− 6 ≥ 0. Mas 32 − 3− 6 = 0, logo 32 − 3− 6 ≥ 0.

(Passo indutivo) Suponha que P(k) seja verdadeira. Devemos mostrar que P(k+1) também é verdadeira.Agora, se P(k) é verdadeira, então k2 − k − 6 ≥ 0. Para mostrar que P(k + 1) é verdadeira, devemosmostrar que (k + 1)2 − (k + 1)− 6 ≥ 0. Agora:

(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .

Pela hipótese de indução, k2− k −6 ≥ 0. Como 2 k ≥ 0 para todo k ∈ B, segue-se que k2− k −6+2 k =(k + 1)2 − (k + 1)− 6 ≥ 0.


Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.


P(n) : n2 − n − 6 ≥ 0.



(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .



Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.


P(n) : n2 − n − 6 ≥ 0.



(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .



Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.


P(n) : n2 − n − 6 ≥ 0.



(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .



Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.


P(n) : n2 − n − 6 ≥ 0.



(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .



Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.


P(n) : n2 − n − 6 ≥ 0.



(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .



Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.


P(n) : n2 − n − 6 ≥ 0.



(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .



Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.


P(n) : n2 − n − 6 ≥ 0.



(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .



Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.


P(n) : n2 − n − 6 ≥ 0.



(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .



Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.


P(n) : n2 − n − 6 ≥ 0.



(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .



Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.


P(n) : n2 − n − 6 ≥ 0.



(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .



Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.


P(n) : n2 − n − 6 ≥ 0.



(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .



Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.


P(n) : n2 − n − 6 ≥ 0.



(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .



Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.


P(n) : n2 − n − 6 ≥ 0.



(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .



Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.


P(n) : n2 − n − 6 ≥ 0.



(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .



Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.


P(n) : n2 − n − 6 ≥ 0.



(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .



Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.


P(n) : n2 − n − 6 ≥ 0.



(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .



Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.


P(n) : n2 − n − 6 ≥ 0.



(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .



Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.


P(n) : n2 − n − 6 ≥ 0.



(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .



Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.


P(n) : n2 − n − 6 ≥ 0.



(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .



Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.


P(n) : n2 − n − 6 ≥ 0.



(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .



Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.


P(n) : n2 − n − 6 ≥ 0.



(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .



Exemplo

Mostre que ∀n ∈ B = {3,4,5, . . .},n2 − n − 6 ≥ 0.


P(n) : n2 − n − 6 ≥ 0.



(k + 1)2 − (k + 1)− 6 = k2 + 2 k + 1− k − 1− 6 = k2 − k − 6 + 2 k .



O Segundo Princípio da Indução Finita


O Segundo Princípio da Indução

Dado um predicado P(n),• se P(1) é verdadeira e (Passo básico )• se P(k)⇒ P(k + 1) é verdadeira, (Passo indutivo)

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

Primeiro Princípio da Indução

Dado um predicado P(n),• se P(1) é verdadeira e (Passo básico )• se P(1) ∧ P(2) ∧ · · · ∧ P(k)⇒ P(k + 1) é verdadeira, (Passo indutivo)


Segundo Princípio da Indução










Exemplo

Mostre que todo número inteiro n ≥ 2 pode ser escrito como produto de números primos (admitindo-seo caso de um produto com um único fator caso n seja um número primo).

Demonstração. Usaremos o Segundo Princípio da Indução. Considere o predicado

P(n) : n pode ser escrito como produto de números primos.

(Passo básico ) Devemos mostrar que P(2) é verdadeira. Em nosso caso, isso significa mostrar que 2pode ser escrito como produto de números primos. Mas 2 é um número primo, logo 2 pode ser escritocomo um produto de números primos com um único fator (o próprio 2).

(Passo indutivo) Suponha que P(2) ∧ P(3) ∧ · · · ∧ P(k) seja verdadeira. Devemos mostrar que P(k + 1)também é verdadeira. Agora, se P(2)∧P(3)∧ · · · ∧P(k) é verdadeira, então todo número ≥ 2 e ≤ k podeser escrito como produto de números primos. Para mostrar que P(k + 1) é verdadeira, devemos mostrarque k + 1 pode ser escrito como produto de números primos. Se k + 1 é um número primo, nada há parase fazer: k +1 pode ser escrito como um produto de números primos com um único fator (o próprio k +1).Se k + 1 não é um número primo, então ele pode ser escrito na forma k + 1 = a b, com 2 ≤ a ≤ k e2 ≤ b ≤ k . Pela hipótese de indução, a e b podem ser escritos como produto de números primos. Logok + 1 = a b também pode ser escrito como produto de números primos.

Por que o Segundo Princípio da Indução é útil aqui? Considere k = 24 = 4 ·6. Para mostrar que P(24) é verdadeirausando essa decomposição, precisamos usar que P(4) e P(6) verdadeiras. A hipótese de indução do PrimeiroPrincípio permite usar apenas que P(23) é verdadeira, o que não nos ajuda aqui.


Exemplo








Exemplo








Exemplo








Exemplo








Exemplo








Exemplo








Exemplo








Exemplo








Exemplo








Exemplo








Exemplo








Exemplo








Exemplo








Exemplo








Exemplo








Exemplo








Exemplo








Exemplo








Exemplo








Exemplo








Exemplo








Exemplo








Exemplo








Exemplo








Exemplo








Exemplo








Exemplo








Exemplo (sem pegar pela mão)


Demonstração. Usaremos o Segundo Princípio da Indução. P(2) é verdadeira, pois 2 é um número primo.Suponha que todo número ≥ 2 e ≤ k pode ser escrito como produto de números primos. Queremosmostrar que k + 1 também pode ser escrito como produto de números primos. Se k + 1 é um númeroprimo, nada há para se fazer. Suponha então que k + 1 não seja um número primo. Portanto, ele podeser escrito na forma k + 1 = a b, com 2 ≤ a ≤ k e 2 ≤ b ≤ k . Pela hipótese de indução, a e b podem serescritos como produto de números primos. Logo k + 1 = a b também pode ser escrito como produto denúmeros primos.





















































Teorema: os dois princípios são equivalentes, isto é, quem tem um, demonstrao outro. Moral: qualquer demonstração usando um dos princípios pode serconvertida em uma demonstração usando o outro.





























Demonstração do teorema







(Primeiro Princípio ⇒ Segundo Princípio) Seja P(n) um predicado tal que P(1) é verdadeira e tal queP(1) ∧ P(2) ∧ · · · ∧ P(k) ⇒ P(k + 1) é verdadeira. Queremos mostrar que P(n) é verdadeira para todon ∈ N. Defina P̃(n) = P(1) ∧ P(2) ∧ · · · ∧ P(n). Note que P̃(1) = P(1) é verdadeira. Se P̃(k) éverdadeira, então P(1)∧P(2)∧· · ·∧P(k) é verdadeira. Por hipótese, P(k +1) também é verdadeira. LogoP(1)∧P(2)∧ · · · ∧P(k)∧P(k + 1) é verdadeira, isto é, P̃(k + 1) é verdadeira. Pelo Primeiro Princípio daIndução (aplicado ao predicado P̃(n)), P̃(n) = P(1) ∧ P(2) ∧ · · · ∧ P(n) é verdadeira para todo n ∈ N. Emparticular, P(n) é verdadeira para todo n ∈ N.





















































































































(Segundo Princípio ⇒ Primeiro Princípio) Seja P(n) um predicado tal que P(1) é verdadeira e tal queP(k) ⇒ P(k + 1) é verdadeira. Queremos mostrar que P(n) é verdadeira para todo n ∈ N. Afirmamosque o predicado P(n) também é tal que P(1) ∧ P(2) ∧ · · · ∧ P(k) ⇒ P(k + 1) é verdadeira. De fato: seP(1) ∧ P(2) ∧ · · · ∧ P(k) é verdadeira, em particular, P(k) é verdadeira. Por hipótese, P(k + 1) também éverdadeira. Pelo Segundo Princípio da Indução, P(n) é verdadeira para todo n ∈ N.










































































Outros nomes para o Segundo Princípio da Indução

O Segundo Princípio da Indução também é conhecido como

Princípio da Indução Completaou

Princípio da Indução Forte.


Outras Aplicações


Exemplo

Quais são os valores que podem ser gerados com selos de 3 e 5 centavos?

Linhas: quantidade selos de 3 centavos. Colunas: quantidade de selos de 5 centavos.

0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo



0 1 2 3 4 5 · · ·

0 0 5 10 15 20 25 · · ·

1 3 8 13 18 23 28 · · ·

2 6 11 16 21 26 31 · · ·

3 9 14 19 24 29 34 · · ·

4 12 17 22 27 32 37 · · ·

5 15 20 25 30 35 40 · · ·...

......

......

......

. . .


Exemplo

É possível produzir qualquer quantia n ≥ 8 (em centavos) com selos de 3 e 5 centavos.

Demonstração. Usaremos o Segundo Princípio da Indução. Considere o predicado:

P(n) : existem inteiros r ≥ 0 e s ≥ 0 tais que 3 r + 5 s = n.

(Passo básico ) O predicado P(n) é verdadeiro para n = 8, n = 9 e n = 10, pois 8 = 3 (1) + 5 (1),9 = 3 (3) + 5 (0) e 10 = 3 (0) + 5 (2).

(Passo indutivo) Se k ≥ 10, suponha que P(l) seja verdadeira para todo l ∈ {8, . . . , k}, isto é, suponhaque qualquer quantia em centavos l ∈ {8, . . . , k} possa ser produzida com selos de 3 e 5 centavos. Vamosmostrar que P(k+1) também é verdadeira, isto é, a quantia em centavos k+1 também pode ser produzidacom selos de 3 e 5 centavos. Pela hipótese de indução, existem inteiros r ≥ 0 e s ≥ 0 tais que

k − 2 = 3 r + 5 s.

Então, k + 1 = k − 2 + 3 = 3 r + 5 s + 3 = 3 (r + 1) + 5 s = 3 r̃ + 5 s, com r̃ = r + 1 ≥ 0 e s ≥ 0.

Mais do que uma demonstração, o Princípio da Indução nos dá um algoritmo para calcular os valores de r e s:

23 = 20 + 3 = 17 + 3 (2) = 14 + 3 (3) = 11 + 3 (4) = 8 + 3 (5) = 5 + 3 (6) = 5 (1) + 3 (6).

Desta maneira, a quantia de 23 centavos pode ser produzida com 1 selo de 5 centavos e 6 selos de 3 centavos.


Exemplo






k − 2 = 3 r + 5 s.



23 = 20 + 3 = 17 + 3 (2) = 14 + 3 (3) = 11 + 3 (4) = 8 + 3 (5) = 5 + 3 (6) = 5 (1) + 3 (6).



Exemplo






k − 2 = 3 r + 5 s.



23 = 20 + 3 = 17 + 3 (2) = 14 + 3 (3) = 11 + 3 (4) = 8 + 3 (5) = 5 + 3 (6) = 5 (1) + 3 (6).



Exemplo






k − 2 = 3 r + 5 s.



23 = 20 + 3 = 17 + 3 (2) = 14 + 3 (3) = 11 + 3 (4) = 8 + 3 (5) = 5 + 3 (6) = 5 (1) + 3 (6).



Exemplo






k − 2 = 3 r + 5 s.



23 = 20 + 3 = 17 + 3 (2) = 14 + 3 (3) = 11 + 3 (4) = 8 + 3 (5) = 5 + 3 (6) = 5 (1) + 3 (6).



Exemplo






k − 2 = 3 r + 5 s.



23 = 20 + 3 = 17 + 3 (2) = 14 + 3 (3) = 11 + 3 (4) = 8 + 3 (5) = 5 + 3 (6) = 5 (1) + 3 (6).



Exemplo






k − 2 = 3 r + 5 s.



23 = 20 + 3 = 17 + 3 (2) = 14 + 3 (3) = 11 + 3 (4) = 8 + 3 (5) = 5 + 3 (6) = 5 (1) + 3 (6).



Exemplo






k − 2 = 3 r + 5 s.



23 = 20 + 3 = 17 + 3 (2) = 14 + 3 (3) = 11 + 3 (4) = 8 + 3 (5) = 5 + 3 (6) = 5 (1) + 3 (6).



Exemplo






k − 2 = 3 r + 5 s.



23 = 20 + 3 = 17 + 3 (2) = 14 + 3 (3) = 11 + 3 (4) = 8 + 3 (5) = 5 + 3 (6) = 5 (1) + 3 (6).



Exemplo






k − 2 = 3 r + 5 s.



23 = 20 + 3 = 17 + 3 (2) = 14 + 3 (3) = 11 + 3 (4) = 8 + 3 (5) = 5 + 3 (6) = 5 (1) + 3 (6).



Exemplo






k − 2 = 3 r + 5 s.



23 = 20 + 3 = 17 + 3 (2) = 14 + 3 (3) = 11 + 3 (4) = 8 + 3 (5) = 5 + 3 (6) = 5 (1) + 3 (6).



Exemplo






k − 2 = 3 r + 5 s.



23 = 20 + 3 = 17 + 3 (2) = 14 + 3 (3) = 11 + 3 (4) = 8 + 3 (5) = 5 + 3 (6) = 5 (1) + 3 (6).



Exemplo






k − 2 = 3 r + 5 s.



23 = 20 + 3 = 17 + 3 (2) = 14 + 3 (3) = 11 + 3 (4) = 8 + 3 (5) = 5 + 3 (6) = 5 (1) + 3 (6).



Exemplo






k − 2 = 3 r + 5 s.



23 = 20 + 3 = 17 + 3 (2) = 14 + 3 (3) = 11 + 3 (4) = 8 + 3 (5) = 5 + 3 (6) = 5 (1) + 3 (6).



Exemplo






k − 2 = 3 r + 5 s.



23 = 20 + 3 = 17 + 3 (2) = 14 + 3 (3) = 11 + 3 (4) = 8 + 3 (5) = 5 + 3 (6) = 5 (1) + 3 (6).



Exemplo






k − 2 = 3 r + 5 s.



23 = 20 + 3 = 17 + 3 (2) = 14 + 3 (3) = 11 + 3 (4) = 8 + 3 (5) = 5 + 3 (6) = 5 (1) + 3 (6).



Exemplo






k − 2 = 3 r + 5 s.



23 = 20 + 3 = 17 + 3 (2) = 14 + 3 (3) = 11 + 3 (4) = 8 + 3 (5) = 5 + 3 (6) = 5 (1) + 3 (6).



Exemplo






k − 2 = 3 r + 5 s.



23 = 20 + 3 = 17 + 3 (2) = 14 + 3 (3) = 11 + 3 (4) = 8 + 3 (5) = 5 + 3 (6) = 5 (1) + 3 (6).



Exemplo






k − 2 = 3 r + 5 s.



23 = 20 + 3 = 17 + 3 (2) = 14 + 3 (3) = 11 + 3 (4) = 8 + 3 (5) = 5 + 3 (6) = 5 (1) + 3 (6).



Exemplo






k − 2 = 3 r + 5 s.



23 = 20 + 3 = 17 + 3 (2) = 14 + 3 (3) = 11 + 3 (4) = 8 + 3 (5) = 5 + 3 (6) = 5 (1) + 3 (6).



Exemplo






k − 2 = 3 r + 5 s.



23 = 20 + 3 = 17 + 3 (2) = 14 + 3 (3) = 11 + 3 (4) = 8 + 3 (5) = 5 + 3 (6) = 5 (1) + 3 (6).



Exemplo






k − 2 = 3 r + 5 s.



23 = 20 + 3 = 17 + 3 (2) = 14 + 3 (3) = 11 + 3 (4) = 8 + 3 (5) = 5 + 3 (6) = 5 (1) + 3 (6).



Exemplo






k − 2 = 3 r + 5 s.



23 = 20 + 3 = 17 + 3 (2) = 14 + 3 (3) = 11 + 3 (4) = 8 + 3 (5) = 5 + 3 (6) = 5 (1) + 3 (6).



Exemplo






k − 2 = 3 r + 5 s.



23 = 20 + 3 = 17 + 3 (2) = 14 + 3 (3) = 11 + 3 (4) = 8 + 3 (5) = 5 + 3 (6) = 5 (1) + 3 (6).



Exemplo






k − 2 = 3 r + 5 s.



23 = 20 + 3 = 17 + 3 (2) = 14 + 3 (3) = 11 + 3 (4) = 8 + 3 (5) = 5 + 3 (6) = 5 (1) + 3 (6).



Exemplo






k − 2 = 3 r + 5 s.



23 = 20 + 3 = 17 + 3 (2) = 14 + 3 (3) = 11 + 3 (4) = 8 + 3 (5) = 5 + 3 (6) = 5 (1) + 3 (6).



Exemplo






k − 2 = 3 r + 5 s.



23 = 20 + 3 = 17 + 3 (2) = 14 + 3 (3) = 11 + 3 (4) = 8 + 3 (5) = 5 + 3 (6) = 5 (1) + 3 (6).



Exemplo






k − 2 = 3 r + 5 s.



23 = 20 + 3 = 17 + 3 (2) = 14 + 3 (3) = 11 + 3 (4) = 8 + 3 (5) = 5 + 3 (6) = 5 (1) + 3 (6).



Exemplo






k − 2 = 3 r + 5 s.



23 = 20 + 3 = 17 + 3 (2) = 14 + 3 (3) = 11 + 3 (4) = 8 + 3 (5) = 5 + 3 (6) = 5 (1) + 3 (6).



Exemplo






k − 2 = 3 r + 5 s.



23 = 20 + 3 = 17 + 3 (2) = 14 + 3 (3) = 11 + 3 (4) = 8 + 3 (5) = 5 + 3 (6) = 5 (1) + 3 (6).



Exemplo






k − 2 = 3 r + 5 s.



23 = 20 + 3 = 17 + 3 (2) = 14 + 3 (3) = 11 + 3 (4) = 8 + 3 (5) = 5 + 3 (6) = 5 (1) + 3 (6).



Exemplo

Para todo n ≥ 1, existe um ladrilhamento por ladrilhos em formato de L ( ) para um jardim 2n × 2n coma estátua de Bill em um quadrado central.

B B


Exemplo


B B


Exemplo


B B


Exemplo


Demonstração. A prova será por indução, mas usaremos um predicado mais forte: P(n) : existe umladrilhamento por ladrilhos em formato de L para um jardim 2n × 2n com a estátua de Bill em qualquerquadrado.

(Passo básico ) P(1) é verdadeira: B , B ,B

,B

.

(Passo indutivo) Suponha que exista um ladrilhamento por ladrilhos em formato de L para jardins 2k × 2k

com um quadrado removido. Considere um jardim 2k+1 × 2k+1. Divida o jardim em 4 quadrantes 2k × 2k .O quadrante que contém a estátua de Bill pode ser ladrilhado com ladrilhos no formato de L (hipótesede indução). Coloque um ladrilho no formato de L na posição central de forma que cada um dos trêsquadrados do L esteja nos três quadrantes restantes. Tudo o que falta é ladrilhar cada um dos trêsquadrantes excluindo o quadrado central já ladrilhado, o que pode ser feito pela hipótese de indução.

B

2k

2k

2k 2k

2k+1


Exemplo




,B

.



B

2k

2k

2k 2k

2k+1


Exemplo




,B

.



B

2k

2k

2k 2k

2k+1


Exemplo




,B

.



B

2k

2k

2k 2k

2k+1


Exemplo




,B

.



B

2k

2k

2k 2k

2k+1


Exemplo




,B

.



B

2k

2k

2k 2k

2k+1


Exemplo




,B

.



B

2k

2k

2k 2k

2k+1


Exemplo




,B

.



B

2k

2k

2k 2k

2k+1


Exemplo




,B

.



B

2k

2k

2k 2k

2k+1


Exemplo




,B

.



B

2k

2k

2k 2k

2k+1


Exemplo




,B

.



B

2k

2k

2k 2k

2k+1


Exemplo




,B

.



B

2k

2k

2k 2k

2k+1


Exemplo




,B

.



B

2k

2k

2k 2k

2k+1


Exemplo




,B

.



B

2k

2k

2k 2k

2k+1


Exemplo




,B

.



B

2k

2k

2k 2k

2k+1


Exemplo




,B

.



B

2k

2k

2k 2k

2k+1


Exemplo




,B

.



B

2k

2k

2k 2k

2k+1


Exemplo




,B

.



B

2k

2k

2k 2k

2k+1


Exemplo: A Torre de Hanoi

Torre A Torre B Torre C

4

3

2

1

O objetivo desse jogo é mover todos os anéis de uma torre para a outra obedecendo duasregras:

(1) Apenas o anel mais acima de cada torre pode ser movido.(2) Um anel maior não pode ser colocado sobre um anel menor.

Este jogo foi criado pelo matemático francês Édouard Lucas em 1883. Há uma lenda que diz queexiste uma sala em um certo monastério com três grandes torres, uma delas com 64 anéis de ouro.Os monges desse monastério estão transferindo os anéis seguindo as regras acima. A lenda diz queo mundo terminará quando os monges conseguirem terminar a transferência.




4

3

2

1







4

3

2

1





Torre de Hanoi com 1 Anel

1



1

Anel transferido da torre A para a torre C.



1

OK


Torre de Hanoi com 2 Anéis

21



2 1

Anel transferido da torre A para a torre B.



1 2




21

Anel transferido da torre B para a torre C.



21

OK



321



32

1




3 2 1




3 21

Anel transferido da torre C para a torre B.



21

3




1 2 3

Anel transferido da torre B para a torre A.



1 32




321




321

OK



4321



432

1




43

1 2




43

21




4 3 21




41

3 2

Anel transferido da torre C para a torre A.



41

32

Anel transferido da torre C para a torre B.



4 321




321

4




32

41




2 3 41

Anel transferido da torre B para a torre A.



21

3 4

Anel transferido da torre C para a torre A.



21

43




2 1 43




1 432




4321




4321

OK



A Torre de Hanoi possui solução para qualquer número n ∈ N de anéis.

Mais ainda, se Tn é o númeromínimo de movimentos para transferir n anéis de uma torre para outra, então Tn+1 = 2 Tn + 1, comT1 = 1. Em particular, Tn = 2n − 1.

Demonstração. Vamos mostrar primeiro que o problema tem solução. Isso será feito por indução. Sen = 1, basta transferir o único anel de uma torre para outra. Suponha que seja sempre possível transferirk anéis de uma torre para outra. Queremos mostrar que é possível transferir k +1 anéis. Se os k +1 anéisestão, digamos, na torre A, transfira os k primeiros anéis para a torre B. Transfira então o (k + 1)-ésimoanel para a torre C e, em seguida, transfira os k anéis da torre B para a torre C.

A solução que propomos para o problema nos mostra que Tn+1 ≤ 2 Tn + 1. Vamos agora mostrar que,também, Tn+1 ≥ 2 Tn + 1. No processo de transferir os n + 1 anéis, em algum momento, os n anéissuperiores devem estar em uma torre, pois (1) não é possível mover o anel n + 1 sem que os n anéissuperiores tenham sido movidos e (2) esses n anéis devem todos estar em uma mesma torre para deixaruma torre vazia, uma vez que o (n + 1)-ésimo anel só pode ser movido para uma torre vazia. Assim,usamos pelo menos Tn movimentos. Ao transferir o (n+1)-ésimo anel, usamos 1 movimento. Ao transferiros n anéis menores para a torre onde o anel n+1 foi colocado, usamos pelo menos outros Tn movimentos.Logo, Tn+1 ≥ 2 Tn + 1.

Temos assim que T1 = 1 e Tn+1 = 2 Tn + 1. Escrevendo Un = Tn + 1, então U1 = T1 + 1 = 1 + 1 = 2 e

Tn+1 = 2 Tn + 1⇔ Un+1 − 1 = 2 (Un − 1) + 1⇔ Un+1 = 2 Un.

Assim, Un = 2n e, portanto, Tn = 2n − 1.



A Torre de Hanoi possui solução para qualquer número n ∈ N de anéis. Mais ainda, se Tn é o númeromínimo de movimentos para transferir n anéis de uma torre para outra, então Tn+1 = 2 Tn + 1, comT1 = 1.

Em particular, Tn = 2n − 1.




Tn+1 = 2 Tn + 1⇔ Un+1 − 1 = 2 (Un − 1) + 1⇔ Un+1 = 2 Un.




A Torre de Hanoi possui solução para qualquer número n ∈ N de anéis. Mais ainda, se Tn é o númeromínimo de movimentos para transferir n anéis de uma torre para outra, então Tn+1 = 2 Tn + 1, comT1 = 1. Em particular, Tn = 2n − 1.




Tn+1 = 2 Tn + 1⇔ Un+1 − 1 = 2 (Un − 1) + 1⇔ Un+1 = 2 Un.








Tn+1 = 2 Tn + 1⇔ Un+1 − 1 = 2 (Un − 1) + 1⇔ Un+1 = 2 Un.








Tn+1 = 2 Tn + 1⇔ Un+1 − 1 = 2 (Un − 1) + 1⇔ Un+1 = 2 Un.








Tn+1 = 2 Tn + 1⇔ Un+1 − 1 = 2 (Un − 1) + 1⇔ Un+1 = 2 Un.








Tn+1 = 2 Tn + 1⇔ Un+1 − 1 = 2 (Un − 1) + 1⇔ Un+1 = 2 Un.








Tn+1 = 2 Tn + 1⇔ Un+1 − 1 = 2 (Un − 1) + 1⇔ Un+1 = 2 Un.








Tn+1 = 2 Tn + 1⇔ Un+1 − 1 = 2 (Un − 1) + 1⇔ Un+1 = 2 Un.








Tn+1 = 2 Tn + 1⇔ Un+1 − 1 = 2 (Un − 1) + 1⇔ Un+1 = 2 Un.








Tn+1 = 2 Tn + 1⇔ Un+1 − 1 = 2 (Un − 1) + 1⇔ Un+1 = 2 Un.








Tn+1 = 2 Tn + 1⇔ Un+1 − 1 = 2 (Un − 1) + 1⇔ Un+1 = 2 Un.








Tn+1 = 2 Tn + 1⇔ Un+1 − 1 = 2 (Un − 1) + 1⇔ Un+1 = 2 Un.








Tn+1 = 2 Tn + 1⇔ Un+1 − 1 = 2 (Un − 1) + 1⇔ Un+1 = 2 Un.








Tn+1 = 2 Tn + 1⇔ Un+1 − 1 = 2 (Un − 1) + 1⇔ Un+1 = 2 Un.








Tn+1 = 2 Tn + 1⇔ Un+1 − 1 = 2 (Un − 1) + 1⇔ Un+1 = 2 Un.








Tn+1 = 2 Tn + 1⇔ Un+1 − 1 = 2 (Un − 1) + 1⇔ Un+1 = 2 Un.








Tn+1 = 2 Tn + 1⇔ Un+1 − 1 = 2 (Un − 1) + 1⇔ Un+1 = 2 Un.








Tn+1 = 2 Tn + 1⇔ Un+1 − 1 = 2 (Un − 1) + 1⇔ Un+1 = 2 Un.








Tn+1 = 2 Tn + 1⇔ Un+1 − 1 = 2 (Un − 1) + 1⇔ Un+1 = 2 Un.








Tn+1 = 2 Tn + 1⇔ Un+1 − 1 = 2 (Un − 1) + 1⇔ Un+1 = 2 Un.








Tn+1 = 2 Tn + 1⇔ Un+1 − 1 = 2 (Un − 1) + 1⇔ Un+1 = 2 Un.








Tn+1 = 2 Tn + 1⇔ Un+1 − 1 = 2 (Un − 1) + 1⇔ Un+1 = 2 Un.








Tn+1 = 2 Tn + 1⇔ Un+1 − 1 = 2 (Un − 1) + 1⇔ Un+1 = 2 Un.








Tn+1 = 2 Tn + 1⇔ Un+1 − 1 = 2 (Un − 1) + 1⇔ Un+1 = 2 Un.








Tn+1 = 2 Tn + 1⇔ Un+1 − 1 = 2 (Un − 1) + 1⇔ Un+1 = 2 Un.








Tn+1 = 2 Tn + 1⇔ Un+1 − 1 = 2 (Un − 1) + 1⇔ Un+1 = 2 Un.




Para n = 64 anéis são então necessários

T64 = 264 − 1 movimentos.

264 − 1 = 18446744073709551615.

Se os monges moverem um anel por segundo, serão necessários mais de

584 bilhões de anos

para eles transferirem todos os 64 anéis!





264 − 1 = 18446744073709551615.








264 − 1 = 18446744073709551615.








264 − 1 = 18446744073709551615.





Exemplo: Permutações

Quantas e quais são as permutações da lista (a,b)?Resposta: são 2 permutações, a saber,

(a,b), (b,a).

Quantas e quais são as permutações da lista (a,b, c)?Resposta: são 6 permutações, a saber,

(a,b, c), (a, c,b), (b,a, c), (b, c,a), (c,a,b), (c,b,a).

E o caso geral?




(a,b), (b,a).



E o caso geral?




(a,b), (b,a).



E o caso geral?




(a,b), (b,a).



E o caso geral?




(a,b), (b,a).



E o caso geral?




(a,b), (b,a).



E o caso geral?




(a,b), (b,a).



E o caso geral?



O número de permutações de uma lista com n elementos é igual a 1 · 2 · · · · · n = n!.

Demonstração. A prova será por indução. O número de permutações de uma lista com um únicoelemento é igual a 1 = 1!. Suponha que o número de permutações de uma lista com k elementos sejaigual a k !. Queremos mostrar que o número de permutações de uma lista (a1,a2,a3, . . . ,ak ,ak+1) comk + 1 elementos é igual a (k + 1)!. Ora, as permutações de (a1,a2,a3, . . . ,ak ,ak+1) podem ser divididasem k + 1 grupos: (

a1 , permutações de a2,a3, . . . , ak ,ak+1

),(


),

...(ak , permutações de a1,a2, . . . ,ak−1,ak+1

),(

ak+1, permutações de a1,a2, . . . ,ak−1, ak

).

Logo, o número total de permutações da lista (a1,a2,a3, . . . ,ak ,ak+1) é igual a

k ! + k ! + · · ·+ k ! + k !︸︷︷︸k+1 vezes

= (k + 1) k ! = (k + 1)!.

Note que a demonstração por indução que fizemos nos dá um algoritmo recursivo para calcularpermutações de listas.






),(


),


),(


).


k ! + k ! + · · ·+ k ! + k !︸︷︷︸k+1 vezes

= (k + 1) k ! = (k + 1)!.







),(


),


),(


).


k ! + k ! + · · ·+ k ! + k !︸︷︷︸k+1 vezes

= (k + 1) k ! = (k + 1)!.







),(


),


),(


).


k ! + k ! + · · ·+ k ! + k !︸︷︷︸k+1 vezes

= (k + 1) k ! = (k + 1)!.







),(


),


),(


).


k ! + k ! + · · ·+ k ! + k !︸︷︷︸k+1 vezes

= (k + 1) k ! = (k + 1)!.







),(


),


),(


).


k ! + k ! + · · ·+ k ! + k !︸︷︷︸k+1 vezes

= (k + 1) k ! = (k + 1)!.







),(


),


),(


).


k ! + k ! + · · ·+ k ! + k !︸︷︷︸k+1 vezes

= (k + 1) k ! = (k + 1)!.







),(


),


),(


).


k ! + k ! + · · ·+ k ! + k !︸︷︷︸k+1 vezes

= (k + 1) k ! = (k + 1)!.







),(


),


),(


).


k ! + k ! + · · ·+ k ! + k !︸︷︷︸k+1 vezes

= (k + 1) k ! = (k + 1)!.







),(


),


),(


).


k ! + k ! + · · ·+ k ! + k !︸︷︷︸k+1 vezes

= (k + 1) k ! = (k + 1)!.







),(


),


),(


).


k ! + k ! + · · ·+ k ! + k !︸︷︷︸k+1 vezes

= (k + 1) k ! = (k + 1)!.







),(


),


),(


).


k ! + k ! + · · ·+ k ! + k !︸︷︷︸k+1 vezes

= (k + 1) k ! = (k + 1)!.







),(


),


),(


).


k ! + k ! + · · ·+ k ! + k !︸︷︷︸k+1 vezes

= (k + 1) k ! = (k + 1)!.







),(


),


),(


).


k ! + k ! + · · ·+ k ! + k !︸︷︷︸k+1 vezes

= (k + 1) k ! = (k + 1)!.







),(


),


),(


).


k ! + k ! + · · ·+ k ! + k !︸︷︷︸k+1 vezes

= (k + 1) k ! = (k + 1)!.







),(


),


),(


).


k ! + k ! + · · ·+ k ! + k !︸︷︷︸k+1 vezes

= (k + 1) k ! = (k + 1)!.







),(


),


),(


).


k ! + k ! + · · ·+ k ! + k !︸︷︷︸k+1 vezes

= (k + 1) k ! = (k + 1)!.



Documents

Matemática BásicaAula 6 Matemática Básica 3 Ainda sobre o princípio da indução ﬁnita Vimos que o Princípio da Indução Finita pode ser usada para demonstrar que sentenças