Fibonacci numbers

The Fibonacci numbers Fibonacci[n]

Fibonacci[n] (f[n]

✖

f[n] for short) can be generated by the recurrence relation

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

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

f[1] = f[2] = 1

f[1] = f[2] = 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]

f[n]/f[n - 1] approaches GoldenRatio

✖

GoldenRatio or (1 + √5)/2 ≃ 1.618

✖

(1+\!\(\*SqrtBox[\(5\)]\))/2\[TildeEqual]1.618.

Fibonacci[n]

Fibonacci[n] can be obtained in many ways:

• (GoldenRatioⁿ - (-GoldenRatio)^-n)/√5

(\!\(\*SuperscriptBox[\(GoldenRatio\),\(n\)]\)-\!\(\*SuperscriptBox[\((-GoldenRatio)\),\(-n\)]\))/\!\(\*SqrtBox[\(5\)]\)

• Round[GoldenRatioⁿ/√5]

Round[\!\(\*SuperscriptBox[\(GoldenRatio\),\(n\)]\)/\!\(\*SqrtBox[\(5\)]\)]

• 2^{1 - n} Coefficient[(1 + √5)ⁿ, √5]

\!\(\*SuperscriptBox[\(2\),\(1-n\)]\)Coefficient[(1+\!\(\*SuperscriptBox[\(\!\(\*SqrtBox[\(5\)]\))\),\(n\)]\),\!\(\*SqrtBox[\(5\)]\)]

• MatrixPower[{{1, 1}, {1, 0}}, n - 1]〚1, 1〛

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

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

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

• Coefficient[Series[1/(1 - t - t²), {t, 0, n}], t^{n - 1}]

Coefficient[Series[1/(1-t-\!\(\*SuperscriptBox[\(t\),\(2\)]\)),{t,0,n}],\!\(\*SuperscriptBox[\(t\),\(n-1\)]\)]

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

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

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

\!\(\*SuperscriptBox[\(2\),\(n-2\)]\)-Count[IntegerDigits[Range[0,\!\(\*SuperscriptBox[\(2\),\(n-2\)]\)],2],{___,1,1,___}]

A fast method for evaluating Fibonacci[n]

Fibonacci[n] is

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

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_}, 0] = {a (a + 2b), s + a (2a - b), 1}

f[{a_, b_, s_}, 1] = {-s + (a + b) (a + 2b), a (a + 2b), -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

m > 1, the value of n for which m  Fibonacci[n]

✖

m  Fibonacci[n] is Round[Log[GoldenRatio, √5 m]]

✖

Round[Log[GoldenRatio,\!\(\*SqrtBox[\(5\)]\)m]].

The sequence Mod[Fibonacci[n], k]

Mod[Fibonacci[n], k] is always purely repetitive; the maximum period is 6k

✖

6k, achieved when k = 10 5^m

✖

k=10 \!\(\*SuperscriptBox[\(5\),\(m\)]\) (compare page 975).

Mod[Fibonacci[n], n]

Mod[Fibonacci[n], n] has the fairly complicated form shown below. It appears to be zero only when n is of the form 5^m

✖

\!\(\*SuperscriptBox[\(5\),\(m\)]\) or 12q

✖

12q, where q is not prime (q > 5

✖

q > 5).

The number GoldenRatio

GoldenRatio appears to have been used in art and architecture since antiquity. 1/GoldenRatio

✖

1/GoldenRatio is the default AspectRatio

✖

AspectRatio for Mathematica graphics. In addition:

• GoldenRatio

GoldenRatio is the solution to x  1 + 1/x

✖

x  1 + 1/x or x²  x + 1

✖

\!\(\*SuperscriptBox[\(x\),\(2\)]\)==x+1

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

GoldenRatio

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

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

GoldenRatio

• The corners of an icosahedron are at coordinates

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

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

• 1 + FixedPoint[N[1/(1 + #), k] &, 1]

1 + FixedPoint[N[1/(1 + #), k] &, 1] approximates GoldenRatio

✖

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

✖

FixedPoint[N[Sqrt[1 + #],k]&, 1]

• A successive angle difference of GoldenRatio

GoldenRatio radians yields points maximally separated around a circle (see page 1006).