# Notes

## Section 5: Substitution Systems

Fibonacci numbers

The Fibonacci numbers Fibonacci[n] (f[n] for short) can be generated by the recurrence relation

f[n_] := f[n] = f[n-1] + f[n - 2]

f = f = 1

The first few Fibonacci numbers are: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377. For large n the ratio f[n]/f[n - 1] approaches GoldenRatio or (1 + 5)/2 1.618.

Fibonacci[n] can be obtained in many ways:

(GoldenRation - (-GoldenRatio)-n)/5

Round[GoldenRation/5]

21 - n Coefficient[(1 + 5)n, 5]

MatrixPower[{{1, 1}, {1, 0}}, n - 1]1, 1

Numerator[NestList[1/(1 + #)&, 1, n]]

Coefficient[Series[1/(1 - t - t2), {t, 0, n}], tn - 1]

Sum[Binomial[n - i - 1, i], {i, 0, (n - 1)/2}]

2n - 2 - Count[IntegerDigits[Range[0, 2n - 2], 2], {___, 1, 1, ___}]

A fast method for evaluating Fibonacci[n] is

First[Fold[f, {1, 0, -1}, Rest[IntegerDigits[n, 2]]]]

f[{a_, b_, s_}, 0] = {a (a + 2b), s + a (2a - b), 1}

f[{a_, b_, s_}, 1] = {-s + (a + b) (a + 2b), a (a + 2b), -1}

Fibonacci numbers appear to have first arisen in perhaps 200 BC in work by Pingala on enumerating possible patterns of poetry formed from syllables of two lengths. They were independently discussed by Leonardo Fibonacci in 1202 as solutions to a mathematical puzzle concerning rabbit breeding, and by Johannes Kepler in 1611 in connection with approximations to the pentagon. Their recurrence relation appears to have been understood from the early 1600s, but it has only been in the past very few decades that they have in general become widely discussed.

For m > 1, the value of n for which m Fibonacci[n] is Round[Log[GoldenRatio, 5 m]].

The sequence Mod[Fibonacci[n], k] is always purely repetitive; the maximum period is 6k, achieved when k = 10 5m (compare page 975).

Mod[Fibonacci[n], n] has the fairly complicated form shown below. It appears to be zero only when n is of the form 5m or 12q, where q is not prime (q > 5). The number GoldenRatio appears to have been used in art and architecture since antiquity. 1/GoldenRatio is the default AspectRatio for Mathematica graphics. In addition:

GoldenRatio is the solution to x 1 + 1/x or x2 x + 1

• The right-hand rectangle in is similar to the whole rectangle when the aspect ratio is GoldenRatio

Cos[π/5] Cos[36°] GoldenRatio/2

• The ratio of the length of the diagonal to the length of a side in a regular pentagon is GoldenRatio

• The corners of an icosahedron are at coordinates

Flatten[Array[NestList[RotateRight, {0, (-1)#1 GoldenRatio, (-1)#2}, 3]&, {2, 2}], 2]

1 + FixedPoint[N[1/(1 + #), k] &, 1] approximates GoldenRatio to k digits, as does FixedPoint[N[Sqrt[1 + #],k]&, 1]

• A successive angle difference of GoldenRatio radians yields points maximally separated around a circle (see page 1006).

From Stephen Wolfram: A New Kind of Science [citation]