More on the Fibonacci series and the Golden Ratio

In my previous blog, I had concluded with a relation between the golden ratio and the Fibonacci sequence. It can be stated as below:

pⁿ = F_n+1 p + F_n ---- (1)

Where p is the golden ratio

And the Fibonacci sequence starts off from 1, 1

i.e. 1, 1, 2, 3, 5, 8, 13, 21 etc.

Now I shall use this equality to prove something else about the relation between the Fibonacci sequence and the golden ratio, namely:

lim                     F_n+1

                        -------      =    p

n -> infinity         F_n

Let us suppose that:

R =      lim                   F_n+1

                                 -------

            n -> infinity     F_n

By doing so, we implicitly assume that such a limiting value for the ratio of two successive Fibonacci terms exists.

R is the ratio of the greater of two successive Fibonacci numbers to the lesser of the two, as the numbers become infinitely large. Thus, R can also be expressed as:

R =      lim                    F_n

                                  ------

            n -> infinity      F_n-1

Now, to start the proof, first divide both sides of (1) by F_n

pⁿ                     F_n+1

---        =          -------  p  +  1

F_n                     F_n

pⁿ                   F_n+1

--- - 1  =         -------  p

F_n                   F_n

F_n+1                  (pⁿ / F_n) - 1

------   =         -------------------

F_n                                 p

                        [p(p^n-1)/F_n] - 1

            =         -------------------

                                    p

p^n-1 = F_n p + F_n-1 so:

                        [p(F_n p + F_n-1)/F_n] - 1

            =         ------------------------------

                                    p

                        p² + p(F_n-1/F_n) – 1

            =         --------------------------

                                    p

                                  F_n-1               1

            =         p +      -------      –        --

                                  F_n                  p

                      F_n-1                p² - 1

            =         ------     +        --------

                      F_n                     p

p² = p + 1 so:

                      F_n-1               p + 1 - 1

            =         -------   +        ----------

                      F_n                    p

F_n+1               F_n-1

-------  =         ------   +  1 ----- (2)*

F_n                  F_n

Now, as we discussed earlier,

R =      lim                   F_n+1

                                 -------

            n -> infinity      F_n

  

R =      lim                  F_n

                                 -------

            n -> infinity     F_n-1

Thus, as n tends to infinity, (2) becomes:

R = 1/R + 1

R = (1 + R)/R

R² = 1 + R

(This is the same quadratic equation as the one for the golden ratio)

R² – R – 1 = 0

Then R = [-b +- √ (b2 – 4ac)]/2a

R = [1 +- √ (1 + 4)]/2 = [1 +- √5]/2

Additionally, as all Fibonacci numbers are positive,

R = [1 + √5]/2 (which is equal to the golden ratio)

Therefore, the ratio of the greater to the smaller of two successive terms of the Fibonacci sequence, as we go on to bigger and bigger terms, tends to the Golden Ratio.

* The relation stated in (2) gives us:

F_n+1               F_n-1

-------  =         ------  +  1

F_n                   F_n

In other words, the ratio of two consecutive Fibonacci numbers (greater is to smaller) is equal to one added to the inverse of the ratio of the smaller number to the Fibonacci number immediately before it.

eg. The Fibonacci numbers 5, 8, 13

13/8 = 1/(8/5) + 1

13/8 = 5/8 + 1

13/8 = (5 + 8)/8

13/8 = 13/8

This relation can be derived in a much simpler way, by considering any sequence of three consecutive Fibonacci numbers.

If the first number is a and the second number is b, the third number must be a + b

i.e. F_n-1 = a

F_n = b

F_n+1 = a + b

Now the ratio of the third to the second is (a + b)/b

And the ratio of the second to the first is b/a

If we invert this second ratio and add 1 to it, we get:

1/(b/a) + 1

= a/b + 1

= (a + b)/b

This is the same as the ratio of the third Fibonacci number to the second Fibonacci number.

i.e. (a+b)/b = 1/(b/a) + 1

Thus we conclude:

F_n+1               F_n-1

-------  =         ------  +  1

F_n                   F_n

This would have been a much shorter method of deriving the proof (don’t ask why I didn’t just use this way).

Addendum: 

Let R_n denote the ratio of the (n+1)^th term to the n^th term of the Fibonacci sequence:

1, 1, 2, 3, 5, 8, 13…

Then, from the equation in (2),

R_n        = 1 + 1/R_n-1

R_n-1      = 1 + 1/R_n-2

R_n-2      = 1 + 1/R_n-3

Etc.

If we were to put them all together,

R_n        = 1 + 1/R_n-1

            = 1 + 1/(1 + 1/R_n-2)

            = 1 + 1/(1 + 1/(1 + 1/R_n-3))

            ……..

            = 1 + 1/(1 + 1/(1 + 1/(1 + 1/(….. + 1/R₁)))))….) 

Further, R₁ = 1/1 = 1

So R_n   = 1 + 1/(1 + 1/(1 + 1/(1 + 1/(….. + 1)))))….)

When n tends to infinity, Rn, as we found out, tends to the golden ratio.

Thus, as n tends to infinity, we get the infinite fraction for the golden ratio:

R         =            1 +            1

                                    ---------------------------------

                                    1 +            1

                                                ------------------------

                                                1 +            1

                                                            ----------------

                                                            1 +            1

                                                                        -------

                                                                        1 + …

An interesting relation

I came across this problem while reading Euler’s Elements of Algebra, and decided to solve it in my own way. The question is as thus:

Find two numbers, whose sum is equal to their product, which in turn is equal to the difference of their squares.

Let the two numbers be x and y, such that x >= y

Then, x + y = xy = x² – y²

The one obvious solution is when both x and y are equal to zero, so we ignore that and look for any other solutions it may have.

Let’s evaluate the following equality:

x + y = x² – y²

x + y = (x + y)(x – y) ----(1)

Now I state that x + y cannot be equal to zero.

If it were, then x + y = xy = 0 so either x or y is zero.

But since x + y = 0, if any one of them is equal to zero, the other has to be zero as well.

And we already overlooked the case where x = y = 0

So we can cancel out (x + y) from equation (1) to get:

1 = x – y

which means that: x = y + 1 ----(2)

Now let us evaluate another equality:

x + y = xy

Substituting x from (2),

y + y + 1 = (y + 1)y

2y + 1 = y² + y

y² = y + 1 ----(3)

Look familiar? Let’s solve it.

y² – y – 1 = 0

Using the quadratic formula,

y = [1 ± √(1 + 4)]/2

= [1 ± √5]/2

Note: Yes, this is equal to the golden ratio. (Look it up on wikipedia if you don’t know it.)

And x = y + 1 = [3 ± √5]/2

So the two numbers could either be:

[1 + √5]/2 and [3 + √5]/2

or [1 – √5]/2 and [3 – √5]/2

Additional tests:

Firstly, as is the case with the golden ratio, the number y obeys the rule y^2 = y + 1

So that, the square of the number is equal to the number itself increased by 1.

And x = y + 1

So y² = x

This equality can be added to the list of other interesting equalities we started out with, namely x + y = xy = x² – y²

Now x + y = xy

y + y + 1 = xy

Inserting x = y²,

2y + 1 = y² * y

y³ = 2y + 1

Thus, the cube of the golden ratio is twice the number itself increased by 1.

This can also be derived by:

y² = y + 1

multiplying both sides by y,

y³ = y² + y --- (4)

replacing the value of y² from before,

y³ = y + 1 + y

so y³ = 2y + 1

We could similarly extend (4) to higher powers

y⁴ = y³ + y²

y⁴ = 2y + 1 + y + 1

y⁴ = 3y + 2

y⁵ = y⁴ + y³

y⁵ = 3y + 2 + 2y + 1

y⁵ = 5y + 3

y⁶ = y⁵ + y⁴
y⁶ = 5y + 3 + 3y + 2
y⁶ = 8y + 5 

and so on…

Upon closer inspection, we see that the coefficient of y and the constant term, in each successive power of y, follows a Fibonacci sequence, in which the constant term is always one term behind the coefficient of y.
Reasoning: the new coefficient of y is always the sum of the previous two coefficients of y, which follows the rule of a Fibonacci sequence, in which each term after the second term is the sum of the two terms before it. The reasoning is similar for the constant term. The Fibonacci sequence for the coefficient of y starts with the first two terms 1 and 2, while the series for the constant starts with the first two terms as 1 and 1. So:
Sequence 1: 1, 2, 3, 5, 8, 13...
Sequence 2: 1, 1, 2, 3, 5, 8, 13...

On the remainder of powers of an integer

There’s a certain rule, which says that, when a number “a” divides different powers of another number N i.e. N¹, N², N³ … the remainders appear in cyclic form i.e. they repeat a fixed pattern.

Eg. 3¹ divided by 5 gives a remainder of 3

3² = 9 divided by 5 gives a remainder of 4

3³ = 27 divided by 5 gives a remainder of 2

3⁴ = 81 divided by 5 gives a remainder of 1

3⁵ = 243 divided by 5 gives a remainder of  3

and that’s when the pattern starts repeating (3, 4, 2, 1, 3, 4, 2, 1, 3, 4, 2, 1…)

The proof of this is what will now follow. Note: I will only work with the domain of positive integers in the whole of this proof. 

Denote the remainder of any number x, divided by the number a, by the function R(x).

Now, first take a number  N, which, when divided by a, gives a remainder of r.

R(N) = r

Then, N = an + r (where n is an integer)

Raise N to the p^th power (p being a positive integer)

N^p = (an + r)^p

= (an)^p + ……… + r^p

(by binomial expansion) ---- (1) 

Here, all the terms before r^p have an “a” in them, and are therefore together a multiple of a.

So, N^p = (multiple of a) + r^p

Therefore, r^p divided by a will give the same remainder as when N^p is divided by a. *

i.e. R(r^p) = R(N^p) ---- (2)

Now let us prove something first:

If R(r^x) = R(r^y)

Then R(r^x+1) = R(r^y+1)

Say R(r^x) = R(r^y) = R' 

r^x = n_xa + R'

r^{x+ 1} = r^x . r 

Thus, r^x+1 = (n_xa + R')r = r n_xa + R'r

Similarly, r^y = n_ya + R'

r^y+1 = r^y . r

r^y+1 = (n_ya + R')r = r n_ya + R'r

Then, both r^x+1 and r^y+1 are in the form (multiple of a) + R'r

So R'r divided by a gives the same remainder as r^x+1 divided by a

R'r divided by a also gives the same remainder as r^y+1  divided by a

=> r^x+1 divided by a gives the same remainder as r^y+1 divided by a

R(r^x+1) = R(r^y+1) Proved.

From (2),

If R(N^x) = R(N^y)

Then R(N^x+1) = R(N^y+1) ---- (3)

Take R(N^p) as R. If R is not equal to 0, then R can go from 1, 2, 3, 4, … upto a-1. That is a maximum of a-1 possibilities for the value of R. If every next R is different, then we can have at most (a-1) different R’s, after which, R will repeat a value already obtained before, and the rule stated in (3) will cause R to cycle among its fixed values.

Therefore, in the series R(N), R(N²), R(N³), R(N⁴) etc., we need only find a single repetition in the value of R to ensure that R will repeat in the same fashion ad infinitum.

* Addendum: We can use the rule stated in (2) to simplify finding the remainder of powers of large numbers, for example: 87²⁵ divided by 7.

We note that 87 = 12*7 + 3

Thus, the remainder gotten when 87²⁵ is divided by 7 is the same as the remainder when 3²⁵ is divided by 7. Then,

1. 3 / 7 -> 3 ---(1)

2. 9 / 7 -> 2 ---(2)

3. 27 / 7 -> 6 ---(3)

4. 81 / 7 -> 4 ---(4)

5. 243 / 7 -> 5 ---(5)

6. 729 / 7 -> 1 ---(6)

7. 2187 / 7 -> 3 ---(1)

That’s where the repetition starts. So it starts at 3 and cycles every 6 powers. 25 = 6*4 + 1. Thus, the remainder when 3²⁵ is divided by 7 is 3, and consequently, the remainder when 87²⁵ is divided by 7 is also 3.

On the reflection of a point over a line

Did some brain-storming to come up with this (even if it is probably already done) formula to find the reflection P'(x₂, y₂) of a point P(x₁, y₁) over a line:

Ax + By + C = 0 --- (1)

 Idea: I will use two equations in x₂ and y₂, containing constants A, B, C, x₁ and y₁, to derive the value of x₂ and y₂ in terms of the said constants. For the first equation, I shall take the help of the equation of the straight line passing through P and P'. For the second equation, I shall use the midpoint formula for the point M(a, b) that lies on line (1) and lies between P and P'.

Ok, let’s look at the figure first. Suffice to say, it represents the reflection of any point over a general straight line.

PP' is a line that is perpendicular to (1)

So the equation of PP’ would be:

Bx – Ay + K = 0 --- (2)

where K is a constant

[reason: the slope of line (1) is found to be –A/B, and since line (2) is perpendicular to line (1), its slope must be B/A (to give a product of –1), which gives us equation (2)]

As P(x₁, y₁) lies on line (2),

Bx₁ – Ay₁ + K = 0

K = Ay₁ – Bx₁

Thus, line (2) can be written as:

Bx – Ay + (Ay₁ – Bx₁) = 0 --- (2)

As P'(x₂, y₂) also lies on this line,

Bx₂ – Ay₂ + (Ay₁ – Bx₁) = 0

=> Ay₂ = Bx₂ + (Ay₁ – Bx₁)

=> y₂ = [Bx₂ + (Ay₁ – Bx₁)]/A --- (A)

Now let us look at the point M(a, b) which lies on line (1) and is half-way between P and P'

(As P' is the reflection of P over line (1), PM = MP')

By the mid-point formula,

(x₁ + x₂)/2 = a

(y₁ + y₂)/2 = b

(a, b) lies on line (1), so:

Aa + Bb + C = 0

=> A(x₁ + x₂)/2 + B(y₁ + y₂)/2 + C = 0

=> [Ax₁ + Ax₂ + By₁ + By₂ + 2C]/2 = 0

=> Ax₂ + By₂ + [Ax₁ + By₁ + 2C] = 0

=> By₂ = -Ax₂ – (Ax₁ + By₁ + 2C)

=> y₂ = [-Ax₂ – Ax₁ – By₁ – 2C]/B --- (B)

Thus from (A) and (B),

Bx₂ + (Ay₁ – Bx₁)     =      -Ax₂ – Ax₁ – By₁ – 2C

A                                         B

B²x₂ + B(Ay₁ – Bx₁) = -A²x₂ – A²x₁ – ABy₁ – 2AC

(A² + B²)x₂ = - ABy₁ + B²x₁ – A²x₁ – ABy₁ – 2AC

x₂ = (B² – A²)x₁ – 2ABy₁ – 2AC

                   (A² + B²)

Therefore, from (A),

y₂ = B[(B² – A²)x₁ – 2ABy₁ – 2AC]/(A² + B²) + Ay₁ – Bx₁

                                                A

= B³x₁ – A²Bx₁ – 2AB²y₁ – 2ABC + A³y₁ + AB²y₁ – A²Bx₁ – B³x₁

                                    A(A² + B²)

= A³y₁ – 2A²Bx₁ – AB²y₁ – 2ABC

                        A(A² + B²)

= A²y₁ – 2ABx₁ – B²y₁ – 2BC

                        (A² + B²)

y₂ = (A² – B²)y₁ – 2ABx₁ – 2BC

                   (A² + B²)

Let’s try this formula for a certain case, when a point is reflected on the line:

y = -x

i.e. x + y = 0

Then, A = 1, B = 1, C = 0

x₂ = 0 – 2y₁ – 0   = -y₁

            1 + 1

y₂ = 0 – 2x₁ – 0   = -x₁

            1 + 1