FIBONACCI AND THE FROG

^{by Albert FRANK, Erik GOOLAERTS, Catherine MARCANDELLA}

Introduction:

Among the puzzles of the quarter finals 2001 of the “Championnat International des Jeux Mathématiques et Logiques”, organised by the FFJM (Fédération française des jeux mathématiques), the next question was asked:

A small frog has to travel from point A to point B. Between A and B are situated twenty tiles (A and B are not considered as a tile). The little frog must at all times jump forward, and can jump immediately from point A to point B. She may also land on one or more tiles. However, she can never make use of two consecutive tiles on her way from A to B (jumping from A to the first tile is allowed, as is jumping from the last tile to B). In how many ways can the little frog travel from A to B?

A  B

Solution of the basic problem :

The solution is given by the sum _C = 17.711 (1)

A complete elaboration of this formula is not necessary for our purpose. Indeed a more elegant approach (which is explained in the appendix) shows that the solution to this puzzle is also given by the 22-nd number of Fibonacci. The equivalence of these two approaches (see properties * of the Fibonacci numbers) serves as proof.

The Fibonacci numbers are constructed as follows: F₁ = F₂ = 1. Then by recurrence the other numbers are found : F_n = F_n-2 + F_n-1 .

Who was Leonardo Fibonacci ?

An Italian mathematician, also known as Leonardo of Pisa, born in 1170 in the town of Pisa (one of the major commercial centres in Italy, in those times of the same importance as Venice and Genoa). He studied the algebraic publications of Al-Khuwarizmi. Afterwards Fibonacci travelled the entire mediterranean world, meeting numerous scientists and studiing different systems of arithmetic used at the time. After his return to Pisa, he published in 1202 his manuscript Liber Abbaci, presenting the Indo-Arabe way of numbering and comparing it to the Roman system. He was the first great mathematician in the scientific world to adopt this system and vulgarise it. His work also contains most of the results discovered by the Arabs in algebra and arithmetics (square roots, cubic roots, linear and quadratic equations). In 1220 he published Practica Geometriae, which summed up all the knowledge in geometry and trigonometry in those days. Fibonacci also continues his own research. He is at the origin, among others things, of the solution of famous problems: to find a number x in order that x² + 5 and x² - 5 are both square numbers; solve the cubic equation x³ + 2 x² + 10 x = 20. These and other problems of the same nature are published in his Liber Quadratorum (1225). Fibonacci is also at the origin of the series that carries his name, of which the first two numbers are equal to 1, and the n-th number (n > 2) is the sum of the two preceding numbers in the series. This series has a great number of properties. Among the best known are:

- The sums of the “diagonals” of the Pascal triangle result in the Fibonacci numbers (which explains the equivalence between the two solutions - formula (1) or the 22-nd number of Fibonacci) (*)

- The n-th Fibonacci number is prime if n is prime or n = 4.

- The sum of ten consecutive Fibonacci numbers equals the product of the seventh number by eleven.

- The sum of the squares of the Fibonacci numbers of n-th and (n+1)-th order is equal to the Fibonacci number of order 2n+1.

- The proportion F _n+1 / F _n will converge (rapidely) to the golden ratio f = (1 + ) / 2.

- F_n = [ (1 +)ⁿ - (1 - )ⁿ ] / 2ⁿ (Binet’s formula, 1843)

Generalisation of the problem :

The generalisation of the problem involves two parameters: the number of tiles and the restrictions placed on the movements of the frog. Instead of not being allowed to land on two consecutive tiles, the condition can be omitted or changed to jumping over a minimum of k free tiles with each jump (jumping from A to any tile is still allowed, as is jumping from any tile to B, since A and B are not considered as tiles).

Under the initial condition (the frog can’t land on two consecutive tiles), the generalisation of the problem to n tiles immediately becomes: the possible number of different ways to travel from A to B is given by the (n+2)-th Fibonacci number. It’s also possible to generalise the formula (1), distinguishing between even and odd numbers of tiles.

Let’s examine the general problem : we have n tiles and the frog has to jump over at least K tiles between two stops (K ≥ 0).

K = 0 The number of possible ways equals 2ⁿ.

K = 1 The number of possible ways equals F _n+2 .

K = 2 Lets make the recurrent series :

M₁ = M₂ = M₃ = 1. M_n = M _n-1 + M _n-3. The number of possible ways equals M _n+3 .

K = 3 Lets make the recurrent series :

V₁ = V₂ = V₃ = V₄ = 1. V_n = V _n-1 + V _n-4. The number of possible ways equals V _n+4 .

K any given number (< n) Lets make the recurrent series :

R₁ = ^… = R _K+1 = 1. R_n = R _n-1 + R _n-K-1 . The number of possible ways equals R _n+K+1 .

Convergency of the proportion R _{n+ K+2} / R _{n+K+1 ,}related to the number of tiles n :

If the frog has to jump over at least K tiles between two stops, this proportion (rapidly) converges as n becomes higher.

Experimentally we noticed that the value of this ratio is given by the highest positive real root of the equation x ^K+1 - x ^K - 1 = 0. A general solution to this equation has still to be found. Here are some results :

K	Equation	Value of x
0	x – 2 = 0	2
1	x ^2 – x – 1 = 0	φ (≈ 1.61803)
2	x ^3 – x ^2 – 1 = 0	≈ 1.46557
3	x ^4 – x ^3 – 1 = 0	≈ 1.38028
5	x^6 – x^5 – 1 = 0	≈ 1.32472
100	x^101 – x^100 – 1 = 0	≈ 1.03457
500	x^501 – x^500 – 1 = 0	≈ 1.0094
→ ∞		→ 1

Conclusion :

As so often happens, commencing from a nice puzzle about a little frog that jumps from A to B, some unexpected developments have presented themselves. And once again it’s remarkable that Fibonacci shows up.

Appendix : Direct approach of the problem (drawn up by Catherine).

1. The frog can’t land on two consecutive tiles (as put in the basic problem). The number of tiles is a parameter of the problem.

Number of tiles.
x					1 + 1 = 2	(+1 for the
x						direct route)
	x				2 +1 = 3
x		x
x
	x
		x			4 + 1 = 5
x		x
x			x
x
	x		x
	x
		x
			x		7 + 1 = 8
x		x		x
x		x
x			x
x				x
x
	x		x
	x			x
	x
		x		x
		x
			x
				x	12 + 1 = 13

The Fibonacci numbers appear.

2. The frog has to jump over at least two free tiles. The number of tiles is a parameter again.

Number of tiles.
x						1 + 1 = 2	(+1 for the
x							direct route)
	x					2 +1 = 3
x
	x
		x				3 + 1 = 4
x			x
x
	x
		x
			x			5 + 1 = 6
x			x
x				x
x
	x			x
	x
		x
			x
				x		8 + 1 = 9
x			x
x				x
x					x
x
	x			x
	x				x
	x
		x			x
		x
			x
				x
					x	12 + 1 = 13

Now we find a series where you don’t add up the two preceding numbers, but skip one: add the preceding and third preceding number.

3. The frog has to jump over at least 3 free tiles between two landings. The number of tiles is a parameter.

Number of tiles.
x							1 + 1 = 2	(+1 for the
x								direct route)
	x						2 +1 = 3
x
	x
		x					3 + 1 = 4
x
	x
		x
			x				4 + 1 = 5
x				x
x
	x
		x
			x
				x			6 + 1 = 7
x				x
x					x
x
	x				x
	x
		x
			x
				x
					x		9 + 1 = 10
x				x
x					x
x						x
x
	x				x
	x					x
	x
		x				x
		x
			x
				x
					x
						x	13 + 1 = 14

Here we find a series where you don’t add up the two preceding numbers, but skip two: add the preceding and fourth preceding number.

4. The frog has no restrictions.

Number of tiles.
X				1 + 1 = 2	(+1 for the
X	x				direct route)
X
	x			3 + 1 = 4
X	x	x
X	x
X		x
X
	x	x
	x
		x		7 + 1 = 8
X	x	x	x
X	x	x
X	x		x
X		x	x
X	x
X		x
X			x
X
	x	x	x
	x		x
	x	x
	x
		x	x
		x
			x	15 + 1 = 16

And we find the positive powers of 2.