DCC111  Matemática Discreta

UFMG/ICEx/DCC

Lista de Exercícios 4

Sequências e Indução Matemática

2o Semestre de 2017

Ciências Exatas & Engenharias

1. O conjunto dos números racionais Q é enumerável, ou seja, é possível atribuir (associar) a cada número racional um número natural. Abaixo, os números racionais positivos estão representados na forma de um par ordenado onde o primeiro número representa o numerador e o segundo o denominador. Começando do número racional 1  par ordenado (1, 1)  é possível associar o número natural 1 e, seguindo o sentido das setas, atribuir o próximo número natural denindo assim uma sequência de enumeração. Dado o número racional positivo , qual é o número natural correspondente? ... ... ... ... ... . . . ↑ p q

(1, 6)

(2, 6) (3, 6) (4, 6) (5, 6) (6, 6). . . (1, 5) (2, 5) (3, 5) (4, 5) (5, 5) (6, 5). . . ↑ & (1, 4) (2, 4) (3, 4) (4, 4) (5, 4) (6, 4). . . & (1, 3) (2, 3) (3, 3) (4, 3) (5, 3) (6, 3). . . ↑ & & (1, 2) (2, 2) (3, 2) (4, 2) (5, 2) (6, 2). . . & & (1, 1)→(2, 1) (3, 1)→(4, 1) (5, 1)→(6, 1). . .

2. Prove por indução matemática que 12 + 22 + . . . + n2 =

3. Prove por indução matemática que

n(n + 1)(2n + 1) , n ≥ 1. 6

1 + 3 + 5 + . . . + (2n − 1) = n2 , n ≥ 1.

4. Prove por indução matemática que 13 + 23 + . . . + n3 = (1 + 2 + . . . + n)2 , n ≥ 1.

5. Prove por indução matemática que 2 · 1 + 2 · 2 + 2 · 3 + . . . + 2n = n2 + n, n ≥ 1.

6. Prove por indução matemática que n−1 X

i(i + 1) =

i=1

n(n − 1)(n + 1) ,∀ 3

inteiros n ≥ 2.

7. Ache a fórmula fechada para a soma 1 1 1 1 + + + ... + 1·2 2·3 3·4 n(n + 1)

∀

inteiros n ≥ 1 e prove o seu resultado por indução matemática. 1

8. Ache a fórmula fechada para o produto       1 1 1 1 1− 1− 1− ... 1 − 2 3 4 n

inteiros n ≥ 2 e prove o seu resultado por indução matemática. 9. Ache a fórmula fechada para a soma ∀

1 1 1 + + ... + 1·3 3·5 (2n − 1) · (2n + 1)

inteiros n ≥ 1 e prove o seu resultado por indução matemática. 10. Ache a fórmula fechada para a soma X ∀

n

1 , (i − 1)i

inteiros n ≥ 2 e prove o seu resultado por indução matemática. 11. Prove o seguinte predicado P (n) usando indução matemática: P (n): Qualquer número inteiro positivo n ≥ 8 pode ser escrito como a soma de 3's e 5's. 12. Suponha que temos selos de 4 e 7 centavos. Prove que é possível ter qualquer valor de postagem de 18 centavos ou mais usando somente esses selos. 13. Prove por indução matemática que n < 2 , para todos inteiros n ≥ 5. 14. Seja a seqüência a , a , a , . . . denida como i=2

∀

2

1

2

n

3

a1

=

3

ak

=

7ak−1 , ∀

inteiros k ≥ 2

Prove por indução matemática que a = 3 · 7 para todos os inteiros n ≥ 1. 15. Seja a seqüência a , a , a , . . . denida como n−1

n

1

2

3

a1

=

1

a2

=

3

ak

= ak−2 + 2ak−1 , ∀

inteiros k ≥ 3

Prove por indução matemática que a é ímpar para todos os inteiros n ≥ 1. 16. Seja a seqüência g , g , g , . . . denida como n

0

1

2

g0

=

12

g1

=

29

gk

=

5gk−1 − 6gk−2 , ∀

Prove por indução matemática que g = 5 · 3 17. Seja a seqüência h , h , h , . . . denida como

n

n

0

1

+ 7 · 2n

inteiros k ≥ 2

para todos os inteiros n ≥ 0.

2

h0

=

1

h1

=

2

h2

=

3

hk

= hk−1 + hk−2 + hk−3 , ∀

Prove por indução matemática que h

n

≤ 3n

inteiros k ≥ 3

para todos os inteiros n ≥ 0. 2

18. Seja a seqüência x , x , x , . . . denida como 0

1

2

x0

=

0

x1

=

1

xk

=

5x3k−1 + 7xk−2 , ∀

inteiros k ≥ 2

Prove por indução matemática que se k é múltiplo de 3 então x é par. 19. Seja a seqüência a , a , a , . . . denida como k

0

1

2

a0

=

0

a1

=

0

ak

= ak−1 + 3k (k − 1), ∀

inteiros k ≥ 2

Ache a fórmula fechada para o k-ésimo termo e prove por indução matemática. 20. Seja a seqüência a , a , a , . . . denida como 0

1

2

a0

=

0

a1

=

1

ak

=

k − ak−1 , ∀

inteiros k ≥ 1

Ache a fórmula fechada para o k-ésimo termo e prove por indução matemática. 21. Prove por indução matemática que ∀n ≥ 1, 3 − 2 é ímpar. n

3