Lista 1 - Indução

Prévia do material em texto

Universidade Federal de Pernambuco
Teoria dos Números
Indução
Professora: Maria do Desterro A. da Silva 1
Exercícios
1. Usando o Princípio da Boa Ordenação (PBO), mostre que:
(a) Não existe um inteiro n tal que 0 < n < 1;
(b) Para cada inteiro m, não existe n tal que m < n < m+ 1;
(c) Se m e n são inteiros com m < n, então m + 1 ⩽ n. Reciprocamente, se
m+ 1 ⩽ n, então m < n.
2. Prove por indução:
(a) 12 + 22 + 32 + . . . + n2 =
n(n+ 1)(2n+ 1)
6
;
(b) 1 + 3 + 5 + . . . + (2n− 1) = n2;
(c) 1 ⋅ 2 + 2 ⋅ 3 + 3 ⋅ 4 + . . . + n(n+ 1) = n(n+ 1)(n+ 2)
3
;
(d) 13 + 23 + 33 + . . . + n3 =
[
n(n+ 1)
2
]2
(e) n! > 2n, ∀n ⩾ 4;
(f) n2 > 2n+ 1, ∀n ⩾ 3;
(g) 9|(10n+1 − 9n− 10), ∀n ⩾ 1;
(h) 2n < 2n+1;
(i) 2n > n2, ∀n ⩾ 5;
(j) 133|11n+2 + 122n+1, ∀n ⩾ 0.
3. Prove que para todo n, n ⩾ 1, 32n+1 + 2n+2 é múltiplo de 7 e que 32n+2 + 26n+1
é múltiplo de 11.
4. Prove que o produto de dois inteiros consecutivos é divisível por 2.
1Professora Assistente do Núcleo de Formação Docente, UFPE (desterrouepb@gmail.com)
1
5. Para cada inteiro n, n ⩾ 0, o inteiro 9n − 1 é divisível por 8.
6. A Torre de Hanói é uma torre com n discos, inicialmente empilhados por taman-
hos decrescentes em um dos três pinos dados. O objetivo é transferir a torre
inteira para um dos outros pinos, movendo apenas um disco de cada vez e sem
colocar um maior em cima de um menor. Prove que podemos realizar a transfer-
ência dos n discos, de acordo com as regras de Édouard Lucas, com, no mínimo,
2n − 1 movimentos.
Outra forma de enunciar a primeira e segunda forma do Princípio
de Indução Finita
Proposição 1. (Primeira forma do Princípio de Indução Finita) Seja n0 um número
inteiro positivo e suponhamos que a cada inteiro n, n ⩾ n0, está associada uma afir-
mação A(n), a qual possui, para cada n, um valor lógico V (quando verdadeira) ou F
(quando falsa). Suponhamos que as condições 1 e 2 abaixo sejam verificadas:
1. A afirmação A(n) é verdadeira para n = n0;
2. Para cada k ⩾ n0, se A(k) é verdadeira, então (é possível demonstrar que) A(k+
1) é também verdadeira.
Entao a afirmação A(n) é verdadeira para cada n ⩾ n0.
Proposição 2. (Segunda forma do Princípio de Indução Finita) Seja n0 um número
inteiro positivo e suponhamos que a cada inteiro n, n ⩾ n0, está associada uma afir-
mação A(n), a qual possui, para cada n, um valor lógico V (quando verdadeira) ou F
(quando falsa). Suponhamos que as condições 1 e 2 abaixo sejam verificadas:
1. A afirmação A(n) é verdadeira para n = n0;
2. Para cada k ⩾ n0, se A(k) é verdadeira para n0 ⩽ n ⩽ k, então (é possível
demonstrar que) A(k+ 1) é também verdadeira.
Entao a afirmação A(n) é verdadeira para cada n ⩾ n0.
Questão. Assumindo o Princípio da Boa Ordenação verifique a segunda forma do
Princípio de Indução Finita.
2