Exercícios Matemática

Instituto Federal de Educac~ao, Ci^encia e Tecnologia - Ceara (IFCE)

Bacharelado em Ci^encias da Computac~ao

Matematica Discreta

Prof. Emanuel Viana

Lista 3

17.02.2017

Nome:

1. Temos n dolares para gastar. Todo dia compramos um doce por 1 dolar, ou um

sorvete por 2 dolares. De quantas maneiras podemos gastar o dinheiro?

2. Quantos subconjuntos do conjunto f1; 2; : : : ; ng n~ao cont^em dois inteiros consecutivos?

Seja Fn o n-esimo numero de Fibonacci.

3. Prove que F3n e par.

4. Prove as seguintes identidades:

(a) F1 + F3 + F5 + : : : + F2n􀀀1 = Fn

(b) F0 􀀀 F1 + F2 􀀀 F3 + : : : 􀀀 F2n􀀀1 + F2n = F2n􀀀1 􀀀 1

(c) F2

0 + F2

1 + F2

2 + : : : + F2

n = Fn:Fn+1

(d) Fn􀀀1Fn+1 􀀀 F2

n = (􀀀1)n

5. Desejamos estender os numeros de Fibonacci na outra direc~ao, i.e., queremos denir

Fn para valores negativos de n. Desejamos fazer isso de modo que a recorr^encia

Fn+1 = Fn + Fn􀀀1

permaneca valida. Assim, de F􀀀1+F0 = F1 obtemos F􀀀1 = 1; ent~ao, de F􀀀2+F􀀀1 =

F0 obtemos F􀀀2 = 􀀀1 etc. Como est~ao esses "numeros de Fibonacci com ndices

negativos"relacionados aqueles com ndices positivos, isto e, mostre que

F􀀀n = (􀀀1)n+1Fn:

2

6. Prove a seguinte recorr^encia para os numeros de Fibonacci de ndice mpar.

F2n+1 = 3F2n􀀀1 􀀀 F2n􀀀3:

7. Prove, usando induc~ao, que os numeros de Fibonacci s~ao dados pela seguinte formula.

Fn =

1

p

5

(

1 +

p

5

2

!n

􀀀

1 􀀀

p

5

2

!n)

:

8. Dena uma sequ^encia de inteiros Ln, chamados de numeros de Lucas, por L1 = 1,

L2 = 3 e Ln+1 = Ln + Ln􀀀1. Mostre que Ln pode ser