Frações Contínuas

Prévia do material em texto

1 ALGUMAS IDE´IAS 1
A expansa˜o de nu´meros reais em frac¸a˜o
cont´ınua simples
Romulo Lins
1 Algumas ide´ias
A expansa˜o, em frac¸a˜o cont´ınua simples, de um nu´mero real α (racional ou
irracional) e´ uma expressa˜o do tipo
α = q1 +
1
q2 +
1
q3 +
1
q4 +
1
. . .
nas quais os qi sa˜o inteiros positivos, com a excec¸a˜o de q1, que pode ser negativo.
Veremos que a expansa˜o termina em um nu´mero finito de termos se, e somente
se, α e´ racional. Por exemplo,
70
32
= 2 +
1
5 +
1
3
;
√
2 = 1 +
1
2 +
1
2 +
1
. . .
Veremos, tambe´m, que a expansa˜o e´ perio´dica (como no caso de
√
2, acima),
se, e somente se, α e´ um nu´mero irracional e alge´brico quadra´tico (raiz de uma
equac¸a˜o polinomial de grau 2, com coeficientes inteiros). O nu´mero e na˜o e´
alge´brico:
e = 2 +
1
1 +
1
2 +
1
1 +
1
1 +
1
4 +
1
1 +
1
. . .
Uma notac¸a˜o menos sugestiva, pore´m mais pra´tica e´
α = q1 +
1
q2 +
1
q3 +
1
q4 +
1
. . .
= [q1; q2, q3, q4, . . .]
1 ALGUMAS IDE´IAS 2
Assim:
70
32
= 2 + 1
5+ 1
3
= [2; 5, 3];
√
2 = [1; 2, 2, 2, . . .];
e = [2; 1, 2, 1, 1, 4, 1, . . . , 1, 2n, 1, . . .].
Definic¸a˜o 1 Dado um nu´mero real α, denotaremos por bαc a parte inteira de
α, que e´ definida como o maior inteiro ≤ α. Por exemplo:
b10, 2c = 10; b−5, 3c = −6; bpic = 3
E denotaremos por {α} a parte fraciona´ria de α, definida por {α} = α − bαc;
note que 0 ≤ {α} < 1 para todo α.
Uma vez que, dado α, bαc esta´ bem definida, α fica representado de maneira
u´nica por bαc+ {α}. Isto e´, se α = b+ c, b e´ inteiro, e 0 ≤ c < 1, enta˜o b = bαc
e c = {α}.
Um algor´ıtimo para produzir a expansa˜o de α em frac¸a˜o cont´ınua simples
(ou uma expansa˜o com quantos termos se queira, caso ela na˜o seja finita), e´ o
seguinte.
Tomamos q1 = bαc. Se {α} = 0, α e´ inteiro e a expansa˜o e´ ele mesmo. Se
{α} > 0, enta˜o {α} = 1
α2
para algum α2 > 0, e escrevemos
α = q1 +
1
α2
Repetindo o processo para α2, e assim sucessivamente, atingimos o que e´ procu-
rado:
α = q1 +
1
q2 +
1
q3 +
1
αn
Exemplo 1 Encontrar a expansa˜o em frac¸a˜o cont´ınua simples de
123
45
.
123
45
= 2 +
33
45
= 2 +
1
45
33
= 2 +
1
1 +
12
33
= 2 +
1
1 +
1
33
12
= 2 +
1
1 +
1
2 +
1
1 +
1
3
2 EXPLORANDO ALGUNS PADRO˜ES PARA EXPANSO˜ES 3
Exemplo 2 Encontrar a expansa˜o em frac¸a˜o cont´ınua simples de
√
2.
√
2 = 1+ (
√
2− 1) = 1+ 1
1√
2− 1
√
2 + 1√
2 + 1
= 1+
1√
2 + 1
= 1+
1
1 +
1√
2 + 1
+ 1
=
= 1 +
1
2 +
1√
2 + 1
= 1 +
1
2 +
1
1 +
1√
2 + 1
+ 1
= 1 +
1
2 +
1
2 +
1√
2 + 1
=
= 1 +
1
2 +
1
2 +
1
. . .
2 Explorando alguns padro˜es para expanso˜es
Nesta sec¸a˜o na˜o importam tanto os resultados particulares, e sim o ”esp´ırito”
da explorac¸a˜o, Vamos explorar que nu´meros teˆm certos tipos de representac¸a˜o
como expansa˜o em frac¸a˜o cont´ınua simples.
a. Para os nu´meros que teˆm expansa˜o
α = a+
1
a+
1
a+
1
a+
1
. . .
temos α = a+
1
α
, de onde α =
a+
√
a2 + 4
2
, descartando-se a soluc¸a˜o nega-
tiva. Por exemplo,
3 +
√
32 + 4
2
=
3 +
√
13
2
= [3; 3, 3...], e
1 +
√
12 + 4
2
=
1 +
√
5
2
= [1; 1, 1...]
b. Se m na˜o e´ um quadrado
√
m = b√mc+ 1
1√
m− b√mc
= b√mc+ 1√
m+ b√mc
m− b√mc2
2 EXPLORANDO ALGUNS PADRO˜ES PARA EXPANSO˜ES 4
Se m− b√mc2 = 1, enta˜o
√
m = b√mc+ 1√
m+ b√mc = a+
1
2a+
1
2a+
.. .
= [a; 2a]
onde a = b√mc. Mas, de posse da expansa˜o acima, obtemos
√
m = a+
1
a+ a+
1
2a+
.. .
= a+
1
a+
√
m
de onde se obte´m m = a2 + 1 (m = 2, 5, 10, 17, 26, . . .).
Se m− b√mc2 = 2, enta˜o
√
m = b√mc+ 1√
m+ b√mc
2
Como b
√
m+ b√mc
2
c = b√mc,
√
m = b√mc+ 1√
m+ b√mc
2
= b√mc+ 1
b√mc+
√
m+ b√mc
2
− b√mc
=
= b√mc+ 1
b√mc+
√
m− b√mc
2
= b√mc+ 1
b√mc+ 1
2√
m− b√mc
=
= b√mc+ 1
b√mc+ 1
2(
√
m+ b√mc)
2
= b√mc+ 1
b√mc+ 1√
m+ b√mc
=
= [a; a, 2a]
3 DOIS TEOREMAS 5
para a = b√mc. Analogamente ao caso anterior, obte´m-se m = a2 + 2.
Se m− b√mc2 = 3, enta˜o...
√
67 = [8; 5, 2, 1, 1, 7, 1, 1, 2, 5, 16] !!!!
c. O que e´ que ”resolve” nos dois primeiros casos? Em m− b√mc2 = 1 e´ o 1,
mas em m − b√mc2 = 2 e´ b
√
m+ b√mc
2
c = b√mc. Quer dizer, o padra˜o
emp´ırico na˜o tem origem num padra˜o matema´tico, por assim dizer.
d. Seja m = a2 + 1
a =
√
a2 <
√
a2 + 1 <
√
a2 + 1 = a+ 1⇔ a = b
√
a2 + 1c
Enta˜o m− b√mc2 = a2 + 1− a2 = 1. Por outro lado, se m− b√mc2 = 1,
representamos m = b2 + k, onde b2 ≤ m < (b+ 1)2, de modo que
b <
√
m < b+ 1
de onde b = b√b2 + 1c; observe que k < 2b+ 1. Como
m− b√mc2 = b2 + k − b
√
b2 + kc2 = b2 + k − b2 = k
k = 1, e m = b2 + 1
e. Usando a calculadora de Alpern (http://www.alpertron.com.ar/CONTFRAC.HTM)
ou a da Universidade de Surrey, UK (http://www.maths.surrey.ac.uk/hosted-
sites/R.Knott/Fibonacci/cfCALC.html), voceˆ pode explorar, empirica-
mente, expanso˜es, fazer conjecturas e tentar entendeˆ-las e, se poss´ıvel, de-
monstra´-las.
3 Dois teoremas
Teorema 1 A expansa˜o de α e´ finita se, e somente se, α e´ racional.
Demonstrac¸a˜o. (⇒) Se a expansa˜o e´ finita, a ”conta de volta” resulta, natu-
ralmente, em um nu´mero racional.
3 DOIS TEOREMAS 6
(⇐) Se α e´ racional, a determinac¸a˜o da expansa˜o corresponde ao uso do algor´ıtimo
de Euclides. Tomando α =
m
n
,
m = nq1 + r1 =⇒ m
n
= q1 +
r1
n
= q1 +
1
n
r1
n = r1q2 + r2 =⇒ n
r1
= q2 +
r2
r1
= q2 +
1
r1
r2
r1 = r2q3 + r3 =⇒ r1
r2
= q3 +
r3
r2
= q3 +
1
r2
r3
. . .
rk−3 = rk−2qk−1 + rk−1 =⇒ rk−3
rk−2
= qk−1 +
rk−1
rk−2
= qk−1 +
1
rk−2
rk−1
rk−2 = rk−1qk =⇒ rk−2
rk−1
= qk
e basta fazer as substituic¸o˜es correspondentes para obter a expansa˜o
m
n
= q1 +
1
q2 +
.. .
qk−2 +
1
qk−1 +
1
qk
Os qi sa˜o chamados de quocientes parciais
Teorema 2 A expansa˜o de α e´ infinita e perio´dica se, e somente se, α e´ irraci-
onal e alge´brico quadra´tico.
Demonstrac¸a˜o. (⇒) Vamos supor α > 1. Se a expansa˜o e´ infinita e perio´dica,
ela tem a forma
α = q1 +
1
q2 +
1
. . . qi−1 +
1
qi +
1
α+ k
Ao fazer a ”conta de volta”, claramente vamos terminar com uma equac¸a˜o em α,
de grau 2 e coeficientes inteiros;
α =
aα + b
cα + d
4 QUOCIENTES PARCIAIS E CONVERGENTES 7
Se fosse racional, a expansa˜o seria finita.
(⇐) A demonstrac¸a˜o geral na˜o e´ simples, e foi feita por Lagrange (veja, por
exemplo, H. Davenport, The Higher Arithmetic, p.83 e seguintes). Vamos apenas
apresentar um caso particular, simples.
Suponha que α > 0 e´ ra´ız de x2 − 3x− 1 = 0. Enta˜o, rearranjando,
x = 3 +
1
x
de onde deduzimos
α = 3 +
1
3 +
1
3 +
1
. . .
4 Quocientes parciais e convergentes
Dado um nu´mero real α e sua expansa˜o (finita ou na˜o) em frac¸a˜o cont´ınua
simples,
α = q1 +
1
q2 +
1
q3 +
1
q4 +
1
. . .
chamamos de convergentes aos resultados dos sucessivos truncamentos da ex-
pansa˜o:
4 QUOCIENTES PARCIAIS E CONVERGENTES 8
C1 =
P1
Q1
= q1
C2 =
P2
Q2
= q1 +
1
q2
C3 =
P3
Q3
= q1 +
1
q2 +
1
q3
C4 =
P4
Q4
= q1 +
1
q2 +
1
q3 +
1
q4
e assim por diante. Conhecidos os quocientes parciais, existe uma relac¸a˜o de
recorreˆncia que permite calcular Ck a partir de Ck−1, Ck−2 e de qk.
Comec¸amos observando que Ck se obte´m de Ck−1 substituindo qk−1 por
qk−1 +
1
qk
. Para facilitar a escrita da generalizac¸a˜o, tomaremos P0 = 1, Q0 = 0,
observando que, naturalmente, estes nu´meros na˜o correspondem a uma frac¸a˜o
(convergente). Assim,
4 QUOCIENTES PARCIAIS E CONVERGENTES9
C1 =
P1
Q1
=
q1
1
C2 =
P2
Q2
=
q1 +
1
q2
1
=
q2q1 + 1
q2.1 + 0
=
q2P1 + P0
q2Q1 +Q0
C3 =
P3
Q3
=
(
q2 +
1
q3
)
P1 + P0(
q2 +
1
q3
)
Q1 +Q0
=
q3P2 + P1
q3Q2 +Q1
C4 =
P4
Q4
=
(
q3 +
1
q4
)
P2 + P1(
q3 +
1
q4
)
Q2 +Q1
=
q4P3 + P2
q4Q3 +Q2
e, de modo geral,
Ck =
Pk
Qk
=
qkPk−1 + Pk−2
qkQk−1 +Qk−2
de modo que o numerador e o denominador das convergentes seguem
† =
{
Pk = qkPk−1 + Pk−2
Qk = qkQk−1 +Qk−2
Estas relac¸o˜es podem ser representadas no que Vinogradov chama de ”dispo-
sitivo pra´tico”:
k 0 1 2 3 . . . n . . .
qk q1 q2 q3 . . . qn . . .
Pk 1 P1 = q1 P2 = q2P1 + P0 P3 = q3P2 + P1 . . . Pn = qnPn−1 + Pn−2 . . .
Qk 0 Q1 = 1 Q2 = q2Q1 +Q0 Q3 = q3Q2 +Q1 . . . Qn = qnQn−1 +Qn−2 . . .
4 QUOCIENTES PARCIAIS E CONVERGENTES 10
Um exemplo nume´rico: expressamos α =
210
76
como frac¸a˜o cont´ınua simples:
210 = 76× 2+ 58
76 = 58× 1+ 18
58 = 18× 3+ 4
18 = 4× 4+ 2
4 = 2× 2
210
76
= 2+
1
1+
1
3+
1
4+
1
2
k 0 1 2 3 4 5
qk 2 1 3 4 2
Pk 1 2 3 11 47 105
Qk 0 1 1 4 17 38
As convergentes sa˜o:
C1 =
2
1
<
210
76
, C2 =
3
1
>
210
76
C1 < C3 =
11
4
<
210
76
, C2 > C4 =
47
17
>
210
76
C5 =
105
38
=
210
76
Duas observac¸o˜es sa˜o de extrema importaˆncia. Primeiro, que a u´ltima conver-
gente (no caso de α racional), embora equivalente a` frac¸a˜o original, na˜o precisa
ser numericamente igual a`quela; como demonstraremos, no caso das expanso˜es
finitas, a u´ltima convergente e´ sempre a frac¸a˜o reduzida equivalente a` original.
4 QUOCIENTES PARCIAIS E CONVERGENTES 11
Segundo, que as convergentes sa˜o, alternadamente, menores (n ı´mpar) e maiores
(n par) que α (com excec¸a˜o da u´ltima no caso de α racional, em que e´ igual); esta
alternaˆncia torna bastante interessante e u´til, no caso de α irracional, estudar se
e como as convergentes se aproximam de α.
Para k > 1,
Ck − Ck−1 = Pk
Qk
− Pk−1
Qk−1
=
PkQk−1 −QkPk−1
QkQk−1
Denominando hk = PkQk−1 − QkPk−1, e substituindo as relac¸o˜es (†) para
Pk, Qk, obtemos
hk = (qkPk−1 + Pk−2)Qk−1 − (qkQk−1 +Qk−2)Pk−1 =
= qkPk−1Qk−1 + Pk−2Qk−1 − qkQk−1Pk−1 −Qk−2Pk−1 =
= −(Pk−1Qk−2 −Qk−1Pk−2) = −hk−1
Como h1 = q1.0− 1.1 = −1, temos que
hk = PkQk−1 −QkPk−1 = (−1)k
para k > 0, e
Ck − Ck−1 = (−1)
k
QkQk−1
para k > 1. A primeira relac¸a˜o implica que (Pk, Qk) = 1, ja´ que
(Pk, Qk) | PkQk−1 −QkPk−1
e isto demonstra que todas as convergentes (inclusive a u´ltima, no caso de α
racional) sa˜o sempre frac¸o˜es reduzidas.
Suponha que Ck 6= α. A partir da expressa˜o
α = q1 +
1
q2 +
1
. . . qk−1 +
1
αk
4 QUOCIENTES PARCIAIS E CONVERGENTES 12
podemos obter Ck−1 com a substituic¸a˜o de
1
αk
por 0 (primeira substituic¸a˜o), e e
Ck com a substituic¸a˜o de
1
αk
por
1
qk
(segunda substituic¸a˜o):
Ck−1 = q1 +
1
q2 +
1
. . . +
1
qk−1
, Ck = q1 +
1
q2 +
1
. . . +
1
qk−1 +
1
qk
Como αk−1 = qk−1 +
1
αk
, a primeira substituic¸a˜o faz αk−1 ”diminuir”, e a
segunda ”aumentar”. E como αk−2 = qk−2 +
1
αk−1
, a primeira substituic¸a˜o faz
αk−2 ”aumentar” (porque αk−1 diminui) e a segunda ”diminuir” (porque αk−1
aumenta). E assim por diante:
primeira substituic¸a˜o segunda substituic¸a˜o
αk−1 aumenta αk−1 diminui
αk−2 diminui αk−2 aumenta
αk−3 aumenta αk−3 diminui
αk−4 diminui αk−4 aumenta
. . . . . .
de modo que, ao fazer uma das substituic¸o˜es, a convergente resultante fica maior
que α, e ao fazer a outra, fica menor que α, de onde se deduz que um dos nu´meros
Ck−1, Ck e´ menor que α, e o outro maior. Como C1 =
q1
1
< α, se α na˜o e´ inteiro
conclu´ımos que as convergentes sa˜o, a partir de k = 1, menor, maior, menor,
maior, ... que α (a menos, eventualmente, da u´ltima, que e´ igual no caso α raci-
onal).
De todo modo, tudo isto implica que α esta´ entre Ck−1 e Ck, de onde
|α− Ck−1| ≤ 1
QkQk−1
ou seja, Ck−1 e´ a melhor aproximac¸a˜o racional de α com denominador ≤ QkQk−1.
Ale´m disto, como os Qi formam uma sequeˆncia crescente, isto garante a con-
vergeˆncia de [q1; q2. . . . , ].
(I) O caso de pi: Tomando pi = 3, 14159, obtemos convergentes C1 = 3, C2 =
22
7
(a escolha de Arquimedes), C3 =
355
113
(nu´meros muito maiores que no caso ante-
4 QUOCIENTES PARCIAIS E CONVERGENTES 13
rior).
(II) O caso de [1; 1, 1, 1, . . .]: todos os quocientes qi sa˜o 1, de modo que
{
Pk = Pk−1 + Pk−2
Qk = Qk−1 +Qk−2
Como P0 = 1, P1 = q1 = 1, a sequeˆncia de numeradores e´ 1,1,2,3,5,8..., a
sequeˆncia de Fibonacci usual. Analogamente, a sequeˆncia de ”denominadores” e´
0,1,1,2,3,..., e as convergentes sa˜o C1 =
1
1
, C2 =
2
1
, C3 =
3
2
, C4 =
5
3
, . . .. Resta
determinar a que nu´mero real α corresponde esta expansa˜o em frac¸a˜o cont´ınua
simples.
Uma abordagem usa os fatos de que α = limn→∞
Fn
Fn−1
(limite que sabemos
existir) e que os nu´meros de Fibonacci teˆm a forma fechada:
Fn =
1√
5
[(
1 +
√
5
2
)n
−
(
1−√5
2
)n]
A validade desta igualdade pode ser provada, sem dificuldade, usando induc¸a˜o
finita. Mas caso ela na˜o fosse conhecida de antema˜o, poderia ser determinada
usando-se um me´todo associado a sequeˆncias definidas por recorreˆncias, como a
de Fibonacci.
Mas existe uma outra abordagem, mais simples, mas que pode ser feita igual-
mente rigorosa, embora a notac¸a˜o possa fazer parecer que na˜o. Temos que
α = 1 +
1
1+
1
1+
1
1+
.. .
= 1 +
1
α
de onde α2 − α − 1 = 0 e α = 1±
√
5
2
. A soluc¸a˜o negativa deve ser descartada,
ja´ que sabemos que α > 1 = C1, de modo que
1 +
1
1 +
1
1 +
1
1 +
. . .
=
1 +
√
5
2
4 QUOCIENTES PARCIAIS E CONVERGENTES 14
a sec¸a˜o a´urea ou nu´mero de ouro.