Quote:
Originally Posted by stargroup100
On the other hand, there's an easily recognizable pattern in the numerator: n_k = a_k * n_[k-1] + n_[k-2]
This easily gives me the correct answer, but I can't show why this pattern holds true.
|
finding the convergents of a continued fraction using a recurrence relation is a standard result you'd find in any number theory textbook or set of lecture notes. the result you get is that both the numerator and denominator obey this recurrence.
to prove it, we
define sequences of numbers using this relation and show that they have the properties we want using induction.
so for a given continued fraction [a0; (a1, a2, a3...)] (using the notation in the question) we define
p0 = a0
p1 = a0*a1 + 1
q0 = 1
q1 = a1
p_n = a_n*p_(n-1) + p_(n-2) and q_n = a_n*q_(n-1) + q_(n-2)
we want to prove
p_n / q_n = [a0; (a1, a2, ..., a_n)]
we use induction. n=0 and n=1 are boring
assume true for n=k then
[a0; (a1, a2, ..., a_(k+1))] = [a0; (a1, a2, ..., a_k + 1/a_(k+1))]
=
( a_k + 1/a_(k+1) )*p_(k-1) + p_(k-2)
-------------------------------------
( a_k + 1/a_(k+1) )*q_(k-1) + q_(k-2)
=
a_k*p_(k-1) + p_(k-2) + p_(k-1)/a_(k+1)
----------------------------------------
a_k*q_(k-1) + q_(k-2) + q_(k-1)/a_(k+1)
=
p_k + p_(k-1)/a_(k+1)
----------------------
q_k + q_(k-1)/a_(k+1)
=
a_(k+1)*p_k + p_(k-1)
----------------------
a_(k+1)*q_k + q_(k-1)
= p_(k+1)/q_(k+1)
which completes the induction
finally we need to prove that these fractions p_n/q_n are irreducible
to do this we prove that:
p_n*q_(n-1) - q_n*p_(n-1) = (-1)^(n+1)
and you do an induction sort of like the previous one. from this it follows instantly that p_n and q_n are coprime, so these recurrences give you the fractions in lowest terms.
edit: does anybody know when the fuck i'll be able to log into project euler again because (1) i want to see which problems i've solved and (2) most importantly i want that dark website background back like i've always been used to using, which i can only access while logged in