Fibonacci Number

The sequence of numbers defined by the $U_n$ in the Lucas Sequence. They are companions to the Lucas Numbers and satisfy the same Recurrence Relation,

$$F_n \equiv F_{n-2}+F_{n-1}$$ (1)

for $n=3$, 4, ..., with $F_1=F_2=1$. The first few Fibonacci numbers are 1, 1, 2, 3, 5, 8, 13, 21, ... (Sloane's A000045). The Fibonacci numbers give the number of pairs of rabbits $n$ months after a single pair begins breeding (and newly born bunnies are assumed to begin breeding when they are two months old).

The ratios of alternate Fibonacci numbers are given by the convergents to $\phi^{-2}$, where $\phi$ is the Golden Ratio, and are said to measure the fraction of a turn between successive leaves on the stalk of a plant (Phyllotaxis): 1/2 for elm and linden, 1/3 for beech and hazel, 2/5 for oak and apple, 3/8 for poplar and rose, 5/13 for willow and almond, etc. (Coxeter 1969, Ball and Coxeter 1987). The Fibonacci numbers are sometimes called Pine Cone Numbers (Pappas 1989, p. 224).

Another Recurrence Relation for the Fibonacci numbers is

$$F_{n+1} = \left\lfloor{F_n(1+\sqrt{5})+1\over 2}\right\rfloor =\left\lfloor{\phi F_n+{\textstyle{1\over 2}}}\right\rfloor ,$$ (2)

where $\left\lfloor{x}\right\rfloor$ is the Floor Function and $\phi$ is the Golden Ratio. This expression follows from the more general Recurrence Relation that

$$\left\vert\matrix{ F_{n+1} & F_{n+2} & \cdots & F_{n+k}\cr ... ...-1)+1} & F_{n+k(k-1)+2} & \cdots & F_{n+k^2}\cr}\right\vert=0.$$ (3)

The Generating Function for the Fibonacci numbers is

$$g(x)=\sum_{n=0}^\infty F_n x^n={x\over 1-x-x^2} =x+x^2+2x^3+3x^4+5x^5+\ldots.$$ (4)

Yuri Matijasevic (1970) proved that the equation $n=F_{2m}$ is a Diophantine Equation. This led to the proof of the impossibility of the tenth of Hilbert's Problems (does there exist a general method for solving Diophantine Equations?) by Julia Robinson and Martin Davis in 1970.

The Fibonacci number $F_{n+1}$ gives the number of ways for $2\times 1$ Dominoes to cover a $2\times n$ Checkerboard, as illustrated in the following diagrams (Dickau).

The number of ways of picking a Set (including the Empty Set) from the numbers 1, 2, ..., $n$ without picking two consecutive numbers is $F_{n+2}$. The number of ways of picking a set (including the Empty Set) from the numbers 1, 2, ..., $n$ without picking two consecutive numbers (where 1 and $n$ are now consecutive) is $L_n=F_{n+1}+F_{n-1}$, where $L_n$ is a Lucas Number. The probability of not getting two heads in a row in $n$ tosses of a Coin is $F_{n+2}/2^n$ (Honsberger 1985, pp. 120-122). Fibonacci numbers are also related to the number of ways in which $n$ Coin Tosses can be made such that there are not three consecutive heads or tails. The number of ideals of an $n$-element Fence Poset is the Fibonacci number $F_n$.

Sum identities are

$$\sum_{k=1}^n F_k = F_{n+2}-1.$$ (5)

$$F_1+F_3+F_5+\ldots+F_{2k+1}=F_{2k+2}$$ (6)

$$1+F_2+F_4+F_6+\ldots+F_{2k}=F_{2k+1}$$ (7)

$$\sum_{k=1}^n {F_k}^2 = F_nF_{n+1}$$ (8)

$$F_{2n}={F_{n+1}}^2-{F_{n-1}}^2$$ (9)

$$F_{3n}={F_{n+1}}^3+{F_n}^3+{F_{n-1}}^3.$$ (10)

Additional Recurrence Relations are Cassini's Identity

$$F_{n-1}F_{n+1}-{F_n}^2=(-1)^n$$ (11)

and the relations

$${F_{n+1}}^2=4F_n F_{n-1}+{F_{n-2}}^2$$ (12)

(Brousseau 1972),

$$F_{n+m}=F_{n-1}F_m+F_nF_{m+1}$$ (13)

$$F_{(k+1)n}=F_{n-1}F_{kn}+F_nF_{kn+1}$$ (14)

(Honsberger 1985, p. 107),

$$F_n=F_{l}F_{n-l+1}+F_{l-1}F_{n-l},$$ (15)

so if $l=n-l+1$, then $2l=n+1$ and $l=(n+1)/2$

$$F_n={F_{(n+1)/2}}^2+{F_{(n-1)/2}}^2.$$ (16)

Letting $k\equiv (n-1)/2$,

$$F_{2k+1} = {F_{k+1}}^2+{F_k}^2$$ (17)

$${F_{n+2}}^2-{F_{n+1}}^2=F_n F_{n+3}$$ (18)

$${F_n}^2={F_{n-1}}^2+3{F_{n-2}}^2+2F_{n-2}F_{n-3}.$$ (19)

Sum Formulas for $F_n$ include

$$F_n={1\over 2^{n-1}} \left[{{n \choose 1}+5{n\choose 3}+5^2{n\choose 5}+\ldots}\right]$$ (20)

$$F_{n+1}={n\choose 0}+{n-1\choose 1}+{n-2\choose 2}+\ldots.$$ (21)

Cesàro derived the Formulas

$$\sum_{k=0}^n {n\choose k} F_k = F_{2n}$$ (22)

$$\sum_{k=0}^n {n\choose k}2^k F_k = F_{3n}$$ (23)

(Honsberger 1985, pp. 109-110). Additional identities can be found throughout the Fibonacci Quarterly journal. A list of 47 generalized identities are given by Halton (1965).

In terms of the Lucas Number $L_n$,

$$F_{2n}=F_n L_n$$ (24)

$$F_{2n}({L_{2n}}^2-1)=F_{6n}$$ (25)

$$F_{m+p}+(-1)^{p+1}F_{m-p}=F_pL_m$$ (26)

$$\sum_{k=a+1}^{a+4n} F_k=F_{a+4n+2}-F_{a+2}=F_{2n}L_{a+2n+2}$$ (27)

(Honsberger 1985, pp. 111-113). A remarkable identity is

$$\mathop{\rm exp}\nolimits (L_1 x+{\textstyle{1\over 2}}L_2 x... ...extstyle{1\over 3}} L_3 x^3+\ldots) = F_1+F_2 x+F_3 x^2+\ldots$$ (28)

(Honsberger 1985, pp. 118-119). It is also true that

$$5{F_n}^2={L_n}^2-4(-1)^n$$ (29)

and

$${{L_n}^2-(-1)^a{L_{n+a}}^2\over{F_n}^2-(-1)^a{F_{n+a}}^2}=5$$ (30)

for $a$ Odd, and

$${{L_n}^2+{L_{n+a}}^2-8(-1)^n\over{F_n}^2+{F_{n+a}}^2}=5$$ (31)

for $a$ Even (Freitag 1996).

The equation (1) is a Linear Recurrence Sequence

$$x_n=Ax_{x-1}+Bx_{n-2} \qquad n\geq 3,$$ (32)

so the closed form for $F_n$ is given by

$$F_n={\alpha ^n-\beta ^n\over \alpha -\beta},$$ (33)

where $\alpha$ and $\beta$ are the roots of $x^2=Ax+B$. Here, $A=B=1$, so the equation becomes

$$x^2-x-1=0,$$ (34)

which has Roots

$$x= {\textstyle{1\over 2}}(1\pm\sqrt{5}\,).$$ (35)

The closed form is therefore given by

$$F_n = {(1+\sqrt{5}\,)^n-(1-\sqrt{5}\,)^n\over 2^n\sqrt{5}}.$$ (36)

This is known as Binet's Formula. Another closed form is

$$F_n = \left[{{1\over\sqrt{5}}\left({1+\sqrt{5}\over 2}\right)^n}\right]=\left[{\phi^n\over\sqrt{5}}\right],$$ (37)

where $[x]$ is the Nint function.

From (1), the Ratio of consecutive terms is

$${F_n\over F_{n-1}} = 1+{F_{n-2}\over F_{n-1}} = 1+{1\over {F_{n-1}\over F_{n-2}}}$$

$$= 1+{1\over {\strut 1+{\strut 1\over \strut {F_{n-3}\over F_{n-2}}}}} = \left[{1, 1, \ldots, {F_{2}\over F_1}}\right]$$

$$= [\underbrace{1, 1, \ldots, 1}_{n-1}],$$ (38)

which is just the first few terms of the Continued Fraction for the Golden Ratio $\phi$. Therefore,

$$\lim_{n\to \infty} {F_n\over F_{n-1}} = \phi.$$ (39)

The ``Shallow Diagonals'' of Pascal's Triangle sum to Fibonacci numbers (Pappas 1989),

$$\sum_{k=1}^n {k\choose n-k} ={(-1)^n {}_3F_2(1,2,1-n; {\text... ...ver 2}}n; -{\textstyle{1\over 4}})\over\pi(2-3n+n^2)}=F_{n+1},$$ (40)

where ${}_3F_2(a,b,c;d,e;z)$ is a Generalized Hypergeometric Function.

The sequence of final digits in Fibonacci numbers repeats in cycles of 60. The last two digits repeat in 300, the last three in 1500, the last four in 15,000, etc.

$$\sum_{n=1}^\infty {(-1)^n\over F_nF_{n+2}}=2-\sqrt{5}$$ (41)

(Clark 1995). A very curious addition of the Fibonacci numbers is the following addition tree,

which is equal to the fractional digits of $1/89$,

$$\sum_{n=0}^\infty {F_n\over 10^{n+1}}={1\over 89}.$$ (42)

For $n\geq 3$, $F_n\vert F_m$ Iff $n\vert m$. $L_n\vert L_m$ Iff $n$ divides into $m$ an Even number of times. $(F_m,F_n)= F_{(m,n)}$ (Michael 1964; Honsberger 1985, pp. 131-132). No Odd Fibonacci number is divisible by 17 (Honsberger 1985, pp. 132 and 242). No Fibonacci number $>8$ is ever of the form $p-1$ or $p+1$ where $p$ is a Prime number (Honsberger 1985, p. 133).

Consider the sum

$$s_k=\sum_{n=2}^k {1\over F_{n-1}F_{n+1}}=\sum_{n=2}^k \left({{1\over F_{n-1}F_n}-{1\over F_nF_{n+1}}}\right).$$ (43)

This is a Telescoping Sum, so

$$s_k=1-{1\over F_{k+1}F_{k+2}},$$ (44)

thus

$$S\equiv \lim_{k\to\infty} s_k = 1$$ (45)

(Honsberger 1985, pp. 134-135). Using Binet's Formula, it also follows that

$${F_{n+r}\over F_n}={\alpha^{n+r}-\beta^{n+r}\over\alpha^n-\b... ...alpha}\right)^{n+r}\over 1-\left({\beta\over\alpha}\right)^n},$$ (46)

where

$$\alpha = {\textstyle{1\over 2}}(1+\sqrt{5}\,)$$ (47)

$$\beta = {\textstyle{1\over 2}}(1-\sqrt{5}\,)$$ (48)

so

$${F_{n+r}\over F_n}=\alpha^r.$$ (49)

$$S'=\sum_{n=1}^\infty {F_n\over F_{n+1}F_{n+2}} = 1$$ (50)

(Honsberger 1985, pp. 138 and 242-243). The Millin Series has sum

$$S''\equiv \sum_{n=0}^\infty {1\over F_{2^n}}={\textstyle{1\over 2}}(7-\sqrt{5}\,)$$ (51)

(Honsberger 1985, pp. 135-137).

The Fibonacci numbers are Complete. In fact, dropping one number still leaves a Complete Sequence, although dropping two numbers does not (Honsberger 1985, pp. 123 and 126). Dropping two terms from the Fibonacci numbers produces a sequence which is not even Weakly Complete (Honsberger 1985, p. 128). However, the sequence

$$F_n'\equiv F_n-(-1)^n$$ (52)

is Weakly Complete, even with any finite subsequence deleted (Graham 1964). $\{{F_n}^2\}$ is not Complete, but $\{{F_n}^2\}+\{{F_n}^2\}$ are. $2^{N-1}$ copies of $\{{F_n}^N\}$ are Complete.

For a discussion of Square Fibonacci numbers, see Cohn (1964), who proved that the only Square Number Fibonacci numbers are 1 and $F_{12}=144$ (Cohn 1964, Guy 1994). Ming (1989) proved that the only Triangular Fibonacci numbers are 1, 3, 21, and 55. The Fibonacci and Lucas Numbers have no common terms except 1 and 3. The only Cubic Fibonacci numbers are 1 and 8.

$$(F_nF_{n+3}, 2F_{n+1}F_{n+2}, F_{2n+3}={F_{n+1}}^2+{F_{n+2}}^2)$$ (53)

is a Pythagorean Triple.

$${F_{4n}}^2+8F_{2n}(F_{2n}+F_{6n})=(3F_{4n})^2$$ (54)

is always a Square Number (Honsberger 1985, p. 243).

In 1975, James P. Jones showed that the Fibonacci numbers are the Positive Integer values of the Polynomial

$$P(x,y)=-y^5+2y^4x+y^3x^2-2y^2x^3-y(x^4-2)$$ (55)

for Gaussian Integers $x$ and $y$ (Le Lionnais 1983). If $n$ and $k$ are two Positive Integers, then between $n^k$ and $n^{k+1}$, there can never occur more than $n$ Fibonacci numbers (Honsberger 1985, pp. 104-105).

Every $F_n$ that is Prime has a Prime index $n$, with the exception of $F_4=3$. However, the converse is not true (i.e., not every prime index $p$ gives a Prime $F_p$). The first few Prime Fibonacci numbers are for $n=3$, 4, 5, 7, 11, 13, 17, 23, 29, 43, 47, 83, 131, 137, 359, 431, 433, 449, 509, 569, 571, ... (Sloane's A001605; Dubner and Keller 1999). Gardner's statement that $F_{531}$ is prime is incorrect, especially since 531 is not even Prime (Gardner 1979, p. 161). It is not known if there are an Infinite number of Fibonacci primes.

The Fibonacci numbers $F_n$, are Squareful for $n=6$, 12, 18, 24, 25, 30, 36, 42, 48, 50, 54, 56, 60, 66, ..., 372, 375, 378, 384, ... (Sloane's A037917) and Squarefree for $n=1$, 2, 3, 4, 5, 7, 8, 9, 10, 11, 13, ... (Sloane's A037918). $4\vert F_{6n}$ and $25\vert F_{25n}$ for all $n$, but no Squareful Fibonacci numbers $F_p$ are known with $p$ Prime.

See also Cassini's Identity, Fast Fibonacci Transform, Fibonacci Dual Theorem, Fibonacci n-Step Number, Fibonacci Q-Matrix, Generalized Fibonacci Number, Inverse Tangent, Linear Recurrence Sequence, Lucas Sequence, Near Noble Number, Pell Sequence, Rabbit Constant, Stolarsky Array, Tetranacci Number, Tribonacci Number, Wythoff Array, Zeckendorf Representation, Zeckendorf's Theorem

References

Fibonacci Numbers

Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 56-57, 1987.

Basin, S. L. and Hoggatt, V. E. Jr. ``A Primer on the Fibonacci Sequence.'' Fib. Quart. 1, 1963.

Basin, S. L. and Hoggatt, V. E. Jr. ``A Primer on the Fibonacci Sequence--Part II.'' Fib. Quart. 1, 61-68, 1963.

Borwein, J. M. and Borwein, P. B. Pi & the AGM: A Study in Analytic Number Theory and Computational Complexity. New York: Wiley, pp. 94-101, 1987.

Brillhart, J.; Montgomery, P. L.; and Silverman, R. D. ``Tables of Fibonacci and Lucas Factorizations.'' Math. Comput. 50, 251-260 and S1-S15, 1988.

Brook, M. ``Fibonacci Formulas.'' Fib. Quart. 1, 60, 1963.

Brousseau, A. ``Fibonacci Numbers and Geometry.'' Fib. Quart. 10, 303-318, 1972.

Clark, D. Solution to Problem 10262. Amer. Math. Monthly 102, 467, 1995.

Cohn, J. H. E. ``On Square Fibonacci Numbers.'' J. London Math. Soc. 39, 537-541, 1964.

Conway, J. H. and Guy, R. K. ``Fibonacci Numbers.'' In The Book of Numbers. New York: Springer-Verlag, pp. 111-113, 1996.

Coxeter, H. S. M. ``The Golden Section and Phyllotaxis.'' Ch. 11 in Introduction to Geometry, 2nd ed. New York: Wiley, 1969.

Dickau, R. M. ``Fibonacci Numbers.'' http://www.prairienet.org/~pops/fibboard.html.

Dubner, H. and Keller, W. ``New Fibonacci and Lucas Primes.'' Math. Comput. 68, 417-427 and S1-S12, 1999.

Freitag, H. Solution to Problem B-772. ``An Integral Ratio.'' Fib. Quart. 34, 82, 1996.

Gardner, M. Mathematical Circus: More Puzzles, Games, Paradoxes and Other Mathematical Entertainments from Scientific American. New York: Knopf, 1979.

Graham, R. ``A Property of Fibonacci Numbers.'' Fib. Quart. 2, 1-10, 1964.

Guy, R. K. ``Fibonacci Numbers of Various Shapes.'' §D26 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 194-195, 1994.

Halton, J. H. ``On a General Fibonacci Identity.'' Fib. Quart. 3, 31-43, 1965.

Hoggatt, V. E. Jr. The Fibonacci and Lucas Numbers. Boston, MA: Houghton Mifflin, 1969.

Hoggatt, V. E. Jr. and Ruggles, I. D. ``A Primer on the Fibonacci Sequence--Part III.'' Fib. Quart. 1, 61-65, 1963.

Hoggatt, V. E. Jr. and Ruggles, I. D. ``A Primer on the Fibonacci Sequence--Part IV.'' Fib. Quart. 1, 65-71, 1963.

Hoggatt, V. E. Jr. and Ruggles, I. D. ``A Primer on the Fibonacci Sequence--Part V.'' Fib. Quart. 2, 59-66, 1964.

Hoggatt, V. E. Jr.; Cox, N.; and Bicknell, M. ``A Primer for the Fibonacci Numbers: Part XII.'' Fib. Quart. 11, 317-331, 1973.

Honsberger, R. ``A Second Look at the Fibonacci and Lucas Numbers.'' Ch. 8 in Mathematical Gems III. Washington, DC: Math. Assoc. Amer., 1985.

Knott, R. ``Fibonacci Numbers and the Golden Section.'' http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fib.html.

Le Lionnais, F. Les nombres remarquables. Paris: Hermann, p. 146, 1983.

Leyland, P. ftp://sable.ox.ac.uk/pub/math/factors/fibonacci.Z.

Matijasevic, Yu. V. ``Solution to of the Tenth Problem of Hilbert.'' Mat. Lapok 21, 83-87, 1970.

Matijasevich, Yu. V. Hilbert's Tenth Problem. Cambridge, MA: MIT Press, 1993.

Michael, G. ``A New Proof for an Old Property.'' Fib. Quart. 2, 57-58, 1964.

Ming, L. ``On Triangular Fibonacci Numbers.'' Fib. Quart. 27, 98-108, 1989.

Ogilvy, C. S. and Anderson, J. T. ``Fibonacci Numbers.'' Ch. 11 in Excursions in Number Theory. New York: Dover, pp. 133-144, 1988.

Pappas, T. ``Fibonacci Sequence,'' ``Pascal's Triangle, the Fibonacci Sequence & Binomial Formula,'' ``The Fibonacci Trick,'' and ``The Fibonacci Sequence & Nature.'' The Joy of Mathematics. San Carlos, CA: Wide World Publ./Tetra, pp. 28-29, 40-41, 51, 106, and 222-225, 1989.

Schroeder, M. Fractals, Chaos, Power Laws: Minutes from an Infinite Paradise. New York: W. H. Freeman, pp. 49-57, 1991.

Sloane, N. J. A. A037917, A037918 A000045/M0692, and A001605/M2309 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html.

Vorob'ev, N. N. Fibonacci Numbers. New York: Blaisdell, 1961.