Problems

Age
Difficulty
Found: 1970

In a parallelogram \(ABCD\), point \(E\) belongs to the side \(CD\) and point \(F\) belongs to the side \(BC\). Show that the total red area is the same as the total blue area:

image

The figure below is a regular pentagram. What is larger, the black area or the blue area?

image

What’s the sum of the Fibonacci numbers \(F_0+F_1+F_2+...+F_n\)?

What’s the sum \(\frac{F_2}{F_1}+\frac{F_4}{F_2}+\frac{F_6}{F_3}+...+\frac{F_{18}}{F_9}+\frac{F_{20}}{F_{10}}\)?

This week we’re looking at Fibonacci numbers, and other sequences of numbers.

We say that the ‘zeroth’ Fibonacci number is \(0\) and the first Fibonacci number is \(1\). Then, from that point, every Fibonacci number is found by adding the two previous Fibonacci numbers. This means that the sequence begins \(0,1,1,2,3,5,8,13,21,34,55,89,144,...\)

The Fibonacci numbers hide lots of patterns which we’ll explore today, for example snail’s spiral.

image

We have a sequence where the first term (\(x_1\)) is equal to \(2\), and each term is \(1\) minus the reciprocal of the previous term (which we can write as \(x_{n+1}=1-\frac{1}{x_n}\)).

What’s \(x_{57}\)?

Let \(n\) be a positive integer. Can \(n^7-77\) ever be a Fibonacci number?

There is a very, very fast way of computing the greatest common divisor of two positive integers. It was in fact known even to the Greeks two thousand years ago. This procedure is called the Euclidean algorithm, named after Euclid, a famous ancient Greek mathematician.

The algorithm works as follows. Take two positive integers \(a,b\). Let’s say \(a\geq b\).

  1. Calculate the remainder of \(a\) when divided by \(b\). Call it \(r_1\).

  2. Calculate the remainder of \(b\) when divided by \(r_1\). Call it \(r_2\).

  3. Calculate the remainder of \(r_1\) when divided by \(r_2\). Call it \(r_3\).

  4. Continue to divide the remainder from two steps prior by the remainder from the last step, until...

  5. The remainder \(r_n\) is divisible by \(r_{n+1}\). The Euclidean algorithm stops now and \(r_{n+1}\) is \(\gcd(a,b)\).

Show that there is indeed some natural number \(n\) such that \(r_n\) is divisible by \(r_{n+1}\), so that the Euclidean algorithm must stop eventually. Furthermore, show that \(r_{n+1}\) is actually \(\gcd(a,b)\) (otherwise it is all in vain!).