analise combinatoria - Os numeros de fibonacci

Prévia do material em texto

MAT047: Ana´lise combinato´ria
Professor John MacQuarrie
Os nu´meros de Fibonacci
Os nu´meros de Fibonacci sa˜o uma sequeˆncia de nu´meros F0, F1, F1, . . . definidos
por uma regra muito simples:
F0 = 0
F1 = 1
Fn+1 = Fn + Fn−1 ∀n > 1.
Logo
F2 = F1 + F0 = 1 + 0 = 1
F3 = F2 + F1 = 1 + 1 = 2
F4 = F3 + F2 = 2 + 1 = 3
F5 = F4 + F3 = 3 + 2 = 5
A sequeˆncia cont´ınua:
0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , 89 , 144 , 233 , 377 , 610 , 987 , . . .
Os nu´meros de Fibonacci teˆm muitas propriedades interessantes. Uns exem-
plos:
Proposic¸a˜o. Temos
F1 + F2 + . . .+ Fn = Fn+2 − 1.
Demonstrac¸a˜o. Vamos reescrever a identidade Fn+1 = Fn + Fn−1 como
Fn−1 = Fn+1 − Fn.
Logo obtemos as igualdades
F1 = F3 − F2
F2 = F4 − F3
...
Fn = Fn+2 − Fn+1
Segue que
F1 + F2 + . . .+ Fn
= (��F3 − F2) + (��F4 −��F3) + (��F5 −��F4) + . . .+ (���Fn+1 −��Fn) + (Fn+2 −���Fn+1)
= Fn+2 − F2
= Fn+2 − 1.
1
Por exemplo,
F1 + F2 + F3 + F4 + F5 + F6 = 1 + 1 + 2 + 3 + 5 + 8 = 20 = 21− 1 = F8 − 1.
Os nu´meros de Fibonacci aparecem como soluc¸a˜o de problemas combinato´rios.
Por exemplo:
Exemplo. Seja Bn o nu´mero de sequeˆncias de 0’s e 1’s que na˜o conte´m um
nu´mero ı´mpar de 1’s consecutivos. Mostre que
Bn = Fn+1.
R: Vamos confirmar com alguns casos pequenos. As duas sequeˆncias de com-
primento 1 sa˜o
0 e 1.
Mas a segunda conte´m 1 (´ımpar) 1 consecutivo. Enta˜o a u´nica sequeˆncia per-
mitida e´ “0”, logo
B1 = 1 = F2 X
As sequeˆncias de comprimento 2 sa˜o
00 e 01 e 10 e 11,
de quais somente 00, 11 sa˜o permitidas, enta˜o
B2 = 2 = F3 X
Vamos contar quantas teˆm de comprimento n+ 1 (com n > 2) por induc¸a˜o. Ja´
fizemos os casos bases. Enta˜o suponha (hipo´tese da induc¸a˜o) que Bn = Fn+1 e
que Bn−1 = Fn.
u´ltimo d´ıgito 0: neste caso, quando tiramos o u´ltimo d´ıgito, obtemos uma sequeˆncia per-
mitida de comprimento n (pois ainda na˜o vai conte´r um nu´mero ı´mpar de
1’s consecutivos). Quantos teˆm enta˜o? Exatamente Bn = Fn+1 pela HI.
u´ltimo d´ıgito 1: neste caso, a sequeˆncia teˆm que terminar com a sequeˆncia 11 (pois e´
permitida). Enta˜o tire os u´ltimos dois d´ıgitos. Obtemos uma sequeˆncia
permitida de comprimento n−1, de quais existem exatamente Bn−1 = Fn
pela HI.
Logo, pelo princ´ıpio aditivo, existem
Bn+1 = Bn +Bn−1 = Fn+1 + Fn = Fn+2
sequeˆncias permitidas de comprimento n+ 1.
Por exemplo, as sequeˆncias permitidas de comprimento 5 sa˜o
00000 , 00011 , 00110 , 01100 , 11000 , 01111 , 11011 , 11110
enta˜o B5 = 8 = F6.
2
Existem va´rios jeitos achar uma “forma fechada”para Fn – isto e´, uma
fo´rmula para Fn que depende so´ de n. Um jeito que gosto usa diagonalizac¸a˜o
de matrizes:
Considere a matriz
A =
(
1 1
1 0
)
e o vetor (
F1
F0
)
=
(
1
0
)
.
Observe que
A
(
F1
F0
)
=
(
1 1
1 0
)(
F1
F0
)
=
(
F1 + F0
F1
)
=
(
F2
F1
)
.
Similarmente
A
(
F2
F1
)
=
(
1 1
1 0
)(
F2
F1
)
=
(
F2 + F1
F2
)
=
(
F3
F2
)
.
Isto e´, (
F3
F2
)
= A
(
F2
F1
)
= A2
(
F1
F0
)
.
Continuando este processo, obtemos(
Fn+1
Fn
)
= A
(
Fn
Fn−1
)
= A2
(
Fn−1
Fn−2
)
= . . . = An
(
F1
F0
)
.
Enta˜o, para entender Fn, temos que entender poteˆncias da matriz A. O me´todo
esperto fazer isso e´ por diagonalizar A:
Autovalores:
det(A− tI2) = det
(
1− t 1
1 −t
)
= −t(1− t)− 1 = t2 − t− 1.
Os autovalores enta˜o sa˜o
1±√1 + 4
2
=
1±√5
2
.
O nu´mero ϕ = 1+
√
5
2 e´ o famoso “nu´mero de ouro”. Vamos chamar por
ψ = 1−
√
5
2 o outro autovalor.
Autovetores:
λ = ϕ
A− ϕI2 =
(
1− ϕ 1
1 −ϕ
)
≡
(
1 −ϕ
0 0
)
(ϕ autovalor).
Desta matriz, obtemos o autovetor
(
ϕ
1
)
.
3
λ = ψ Uma conta similar da´ o autovetor
(
ψ
1
)
.
Logo (de GAAL ou a´lgebra linear), temos que A = PDP−1, onde
D =
(
ϕ 0
0 ψ
)
P =
(
ϕ ψ
1 1
)
e P−1 =
1
ϕ− ψ
(
1 −ψ
−1 ϕ
)
=
1√
5
(
1 −ψ
−1 ϕ
)
pois
ϕ− ψ = 1 +
√
5− (1−√5)
2
=
√
5.
Colocando tudo junto, obtemos:
Fn =
(
0 1
)(Fn+1
Fn
)
=
(
0 1
)
An
(
F1
F0
)
=
(
0 1
)
(PDP−1)n
(
1
0
)
=
(
0 1
)
P
(
ϕn 0
0 ψn
)
P−1
(
1
0
)
=
1√
5
(
1 1
)(ϕn 0
0 ψn
)(
1
−1
)
=
1√
5
(
ϕn ψn
)( 1
−1
)
=
ϕn − ψn√
5
.
Descobrimos assim uma fo´rmula fechada para Fn:
Fn =
ϕn − ψn√
5
Este resultado tem como consequeˆncia que podemos definir o nu´mero de
ouro a partir dos nu´meros de Fibonacci:
Corola´rio. Temos
lim
n→∞
Fn+1
Fn
= ϕ.
Demonstrac¸a˜o. Da fo´rmula fechada de Fn, obtemos que
Fn+1
Fn
=
ϕn+1 − ψn+1
ϕn − ψn .
4
Observe que |ϕ| ≈ 1.618 > 0.618 ≈ |ψ|. Usando o truque de ca´lculo, vamos
dividir todo mundo por ϕn:
lim
n→∞
Fn+1
Fn
= lim
n→∞
ϕn+1
ϕn − ψ
n+1
ϕn
ϕn
ϕn − ψ
n
ϕn
= lim
n→∞
ϕ− ψ
(
ψn
ϕn
)
1− ψnϕn
= lim
n→∞
ϕ− ψ
�
�
�>
0(
ψ
ϕ
)n
1−
�
�
�>
0(
ψ
ϕ
)n
= ϕ.
5