Sidebar: the golden ratio

Loading...

From the course by National Research University Higher School of Economics

Introduction to Enumerative Combinatorics

51 ratings

National Research University Higher School of Economics

Introduction to Enumerative Combinatorics

51 ratings

Enumerative combinatorics deals with finite sets and their cardinalities. In other words, a typical problem of enumerative combinatorics is to find the number of ways a certain pattern can be formed. In the first part of our course we will be dealing with elementary combinatorial objects and notions: permutations, combinations, compositions, Fibonacci and Catalan numbers etc. In the second part of the course we introduce the notion of generating functions and use it to study recurrence relations and partition numbers. The course is mostly self-contained. However, some acquaintance with basic linear algebra and analysis (including Taylor series expansion) may be very helpful.

From the lesson

Linear recurrences. The Fibonacci sequence

We start with a well-known "rabbit problem", which dates back to Fibonacci. Using the Fibonacci sequence as our main example, we discuss a general method of solving linear recurrences with constant coefficients.

Fibonacci’s rabbit problem9:36

Fibonacci numbers and the Pascal triangle7:56

Domino tilings8:26

Vending machine problem10:07

Linear recurrence relations: definition7:53

The characteristic equation8:43

Linear recurrence relations of order 211:02

The Binet formula11:21

Sidebar: the golden ratio9:12

Linear recurrence relations of arbitrary order8:44

The case of roots with multiplicities12:10

Meet the Instructors

Evgeny Smirnov
Associate Professor
Faculty of Mathematics

Sidebar, the golden ratio.

We are dealing with the number phi,

which was one plus square root of five over two and

it is approximately equal to 1.6180.3 etc.

And the other root of the characteristic

equation was equal to one minus

the square root of five over two,

and this is equal to minus one

over phi or one minus phi.

Okay.

These numbers were already known to ancient Greeks and

these number phi is known as the golden ratio.

What makes it so special?

Okay, let's consider

our Fibonacci Sequence.

1, 1, 2, 3, 5, 8,

13, 21, etc.

And let us consider the ratios of two consecutive numbers.

fn divided by fn minus one.

So, we obtain 1,

2 over 1 makes 2.

This is 1.5.

Five thirds are 1.66..etc,

8 over 5 makes 1.6,

13 divided by 8 is 1.625.

And so, you see that these, well, this is say the next one is,

1.615, etc.

So you see that these sequence of ratios

converges rather quickly to this value phi.

And, indeed, this is clear from Benes formula.

We see that if fn is equal to

1 over square root of 5,

1 plus square root of 5 over 2,

to the power n minus 1 minus

square root of 5 over 2 over n.

Then for n sufficiently large and this is pretty close to this sum,

because this number is, its absolute value is less than one.

It is between zero and one.

And it's nth powers converge towards zero.

So fn is approximate, well let me put it like this,

is approximately equal to 1 over the square root of 5,

(1 + square root of 5 over 2) to the power n.

So the ratio of, fn over fn-

1 converges towards phi.

Okay, what is so special about this number?

The ancient Greeks called this number the golden proportion or

sometimes it was called the divine proportion for the following reason.

Let's take an interval,

divided into two parts such that their ratio

is, Phi.

So a the larger part,

Over the small part is phi.

We say that a divided by b is the golden ration if the larger part,

Divided by the length of the small part is equal to,

The length of the whole segment divided by the larger part.

So this means that if a over

b is (a+b) over a.

So if a over b is equal to a + b over a,

we say that a and b form a golden ratio.

Well, what does it mean?

We see that this means

that a squared is equal

to ab plus b squared or

a over b squared is a over b plus 1.

And we see the equation which is already familiar to us.

This is a quadratic equation with a over b as a variable and

its solutions are exactly phi and psi.

The golden ratio and 1 minus phi.

So, if you take a rectangle with sides a and

a plus b, Like this,

And if you divide it into a square with side a,

and a rectangle with sides a and b,

you see that this smaller rectangle

is similar to the whole one.

So, if you proceed again and if you take this

smaller rectangle and if you cut a square,

then you are left with a third rectangle which is

similar to both of these two and so on and so on.

You can then draw this small triangle,

add a small rectangle, and proceed in this way.

So, sometimes, in some pictures,

you can see a spiral of this form.

Let's draw a quarter of a circle in each of these rectangles,

in each of these squares, so they will form something like this.

This rectangle was considered to be the most pleasant for our mind, for our eye.

And this golden ratio is said to be found in many

proportions appearing in nature and human body.

And it was used very intensively by artists and

architects starting from the time of ancient Greece

where it appears in kinds of many Greek temples

until our time until Salvador Dali and [FOREIGN].

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play