The Fibonacci sequence is defined as f_1=f_2=1,f_(n+2)=f_(n+1)+f_n. Assume that (f_n)/(f_(n-1))<a/b<(f_(n+1))/(f_n) (a and b are positive integers with no common prime factors). Show that b>=f_(n+1).

Roderick Bradley

Roderick Bradley

Answered question

2022-08-11

Show that b f n + 1
The Fibonacci sequence is defined as f 1 = f 2 = 1 , f n + 2 = f n + 1 + f n . Assume that f n f n 1 < a b < f n + 1 f n ( a and b are positive integers with no common prime factors). Show that b f n + 1

Answer & Explanation

Ayla Coffey

Ayla Coffey

Beginner2022-08-12Added 8 answers

Remark: f r + 1 f r are convergents of the continued fraction of φ the golden ratio. There is a theorem that any convergent is nearer to the number (whose CF we are looking at) than any other rational with a smaller denominator. That or something similar can potentially be used here.
Anyway, here is a simple proof that b f n + 1
First we show that b > f n
Subtract f n f n 1 from the given inequality to get
0 < a b f n f n 1 < f n + 1 f n f n f n 1 = 1 f n f n 1
We used the identity | f n + 1 f n 1 f n 2 | = 1 (Cassini's formula) to simplify the right hand side.
i.e
0 < a f n 1 b f n b < 1 f n
And so
b > f n ( a f n 1 b f n )
Now a f n 1 b f n is a positive integer and so is 1 and so b > f n
Now we show that b f n + 1
Now if a f n 1 b f n 2, then we will have b > 2 f n > f n + f n 1 = f n + 1
So assume that
a f n 1 b f n = 1
Now all solutions of
a u + b v = 1
are given by
a t = a 0 + t v
b t = b 0 t u
where t is an integer param, and a 0 , b 0 are some initial solution.
For us (again using Cassini's)
a 0 = f n + 1
b 0 = f n
u = f n 1
v = f n
Thus the solutions are
a t = f n + 1 t f n
b t = f n t f n 1
Since we want
b t > f n
we need t < 0 in which case
b = b t f n + f n 1 = f n + 1
Makayla Eaton

Makayla Eaton

Beginner2022-08-13Added 6 answers

Suppose a , a , a are non-negative integers and b , b , b are positive integers with a b b a = 1 and a b < a b < a b . Then
0 < a b a b  and  0 < a b a b .
Since these are all integers we have
1 a b a b  and  1 a b a b .
Multiplying the left inequality above by b , and multiplying the right inequality above by b we have
b b a b b a b  and  b b a b b a b .
Adding the above two inequalities we have
b + b ( b a b b a b ) + ( b a b b a b ) = b ( a b b a ) = b .
Since f n 2 f n 1 f n + 1 = ( 1 ) n 1 , if ( a , b ) = ( f n , f n 1 ) and ( a , b ) = ( f n + 1 , f n ) and if a b > a b , then a b b a = 1.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?