Editing Fibonacci sequence (section)

=== Mathematics ===

[[File:Pascal triangle fibonacci.svg|thumb|upright=1.2|The Fibonacci numbers are the sums of the diagonals (shown in red) of a left-justified [[Pascal's triangle]].]]
The Fibonacci numbers occur as the sums of [[binomial coefficient]]s in the "shallow" diagonals of [[Pascal's triangle]]:{{Sfn | Lucas | 1891 | p = 7}}
<math display=block>F_n = \sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor} \binom{n-k-1}{k}.</math>
This can be proved by expanding the generating function
<math display=block>\frac{x}{1-x-x^2} = x + x^2(1+x) + x^3(1+x)^2 + \dots + x^{k+1}(1+x)^k + \dots = \sum\limits_{n=0}^\infty F_n x^n</math>
and collecting like terms of <math>x^n</math>.

To see how the formula is used, we can arrange the sums by the number of terms present:
:{|
| {{math|5}}
| {{math|1== 1+1+1+1+1}}
|-
|
| {{math|1== 2+1+1+1}}
| {{math|1== 1+2+1+1}}
| {{math|1== 1+1+2+1}}
| {{math|1== 1+1+1+2}}
|-
|
| {{math|1== 2+2+1}}
| {{math|1== 2+1+2}}
| {{math|1== 1+2+2}}
|}

which is <math>\textstyle \binom{5}{0}+\binom{4}{1}+\binom{3}{2}</math>, where we are choosing the positions of {{mvar|k}} twos from {{math|''n''−''k''−1}} terms.

[[File:Fibonacci climbing stairs.svg|thumb|right|Use of the Fibonacci sequence to count {{nowrap|{1,&thinsp;2}-restricted}} compositions]]
These numbers also give the solution to certain enumerative problems,<ref>{{citation|last=Stanley|first=Richard|title=Enumerative Combinatorics I (2nd ed.)|year=2011|publisher=Cambridge Univ. Press|isbn=978-1-107-60262-5|page=121, Ex 1.35}}</ref> the most common of which is that of counting the number of ways of writing a given number {{mvar|n}} as an ordered sum of 1s and 2s (called [[composition (combinatorics)#Number of compositions|compositions]]); there are {{math|''F''<sub>''n''+1</sub>}} ways to do this (equivalently, it's also the number of [[domino tiling]]s of the <math>2\times n</math> rectangle). For example, there are {{math|1=''F''<sub>5+1</sub> = ''F''<sub>6</sub> = 8}} ways one can climb a staircase of 5 steps, taking one or two steps at a time:
:{|
| {{math|5}}
| {{math|1== 1+1+1+1+1}}
| {{math|1== 2+1+1+1}}
| {{math|1== 1+2+1+1}}
| {{math|1== 1+1+2+1}}
| {{math|1== 2+2+1}}
|-
|
| {{math|1== 1+1+1+2}}
| {{math|1== 2+1+2}}
| {{math|1== 1+2+2}}
|}
The figure shows that 8 can be decomposed into 5 (the number of ways to climb 4 steps, followed by a single-step) plus 3 (the number of ways to climb 3 steps, followed by a double-step). The same reasoning is applied [[recursion|recursively]] until a single step, of which there is only one way to climb.

The Fibonacci numbers can be found in different ways among the set of [[binary numeral system|binary]] [[String (computer science)|strings]], or equivalently, among the [[subset]]s of a given set.
* The number of binary strings of length {{mvar|n}} without consecutive {{math|1}}s is the Fibonacci number {{math|''F''<sub>''n''+2</sub>}}. For example, out of the 16 binary strings of length 4, there are {{math|1=''F''<sub>6</sub> = 8}} without consecutive {{math|1}}s—they are 0000, 0001, 0010, 0100, 0101, 1000, 1001, and 1010.  Such strings are the binary representations of [[Fibbinary number]]s.  Equivalently, {{math|''F''<sub>''n''+2</sub>}} is the number of subsets {{mvar|S}} of {{math|{{mset|1, ..., ''n''}}}} without consecutive integers, that is, those {{mvar|S}} for which {{math|{{mset|''i'', ''i'' + 1}} ⊈ ''S''}} for every {{mvar|i}}. A [[bijection]] with the sums to {{math|''n''+1}} is to replace 1 with 0 and 2 with 10, and drop the last zero.
* The number of binary strings of length {{mvar|n}} without an odd number of consecutive {{math|1}}s is the Fibonacci number {{math|''F''<sub>''n''+1</sub>}}. For example, out of the 16 binary strings of length 4, there are {{math|1=''F''<sub>5</sub> = 5}} without an odd number of consecutive {{math|1}}s—they are 0000, 0011, 0110, 1100, 1111. Equivalently, the number of subsets {{mvar|S}} of {{math|{{mset|1, ..., ''n''}}}} without an odd number of consecutive integers is {{math|''F''<sub>''n''+1</sub>}}. A bijection with the sums to {{mvar|n}} is to replace 1 with 0 and 2 with 11.
* The number of binary strings of length {{mvar|n}} without an even number of consecutive {{math|0}}s or {{math|1}}s is {{math|2''F''<sub>''n''</sub>}}. For example, out of the 16 binary strings of length 4, there are {{math|1=2''F''<sub>4</sub> = 6}} without an even number of consecutive {{math|0}}s or {{math|1}}s—they are 0001, 0111, 0101, 1000, 1010, 1110. There is an equivalent statement about subsets.
* [[Yuri Matiyasevich]] was able to show that the Fibonacci numbers can be defined by a [[Diophantine equation]], which led to [[Matiyasevich's theorem|his solving]] [[Hilbert's tenth problem]].<ref>{{citation|title=Review of Yuri V. Matiyasevich, ''Hibert's Tenth Problem''|journal=Modern Logic|first=Valentina|last=Harizanov|author-link=Valentina Harizanov|volume=5|issue=3|year=1995|pages=345–55|url=https://projecteuclid.org/euclid.rml/1204900767}}</ref>
* The Fibonacci numbers are also an example of a [[complete sequence]]. This means that every positive integer can be written as a sum of Fibonacci numbers, where any one number is used once at most.
* Moreover, every positive integer can be written in a unique way as the sum of ''one or more'' distinct Fibonacci numbers in such a way that the sum does not include any two consecutive Fibonacci numbers. This is known as [[Zeckendorf's theorem]], and a sum of Fibonacci numbers that satisfies these conditions is called a Zeckendorf representation. The Zeckendorf representation of a number can be used to derive its [[Fibonacci coding]].
* Starting with 5, every second Fibonacci number is the length of the [[hypotenuse]] of a [[right triangle]] with integer sides, or in other words, the largest number in a [[Pythagorean triple]], obtained from the formula <math display=block>(F_n F_{n+3})^2 + (2 F_{n+1}F_{n+2})^2 = {F_{2 n+3}}^2.</math> The sequence of Pythagorean triangles obtained from this formula has sides of lengths (3,4,5), (5,12,13), (16,30,34), (39,80,89), ...&thinsp;. The middle side of each of these triangles is the sum of the three sides of the preceding triangle.<ref>{{citation
 | last = Pagni | first = David
 | date = September 2001
 | issue = 4
 | journal = Mathematics in School
 | jstor = 30215477
 | pages = 39–40
 | title = Fibonacci Meets Pythagoras
 | volume = 30}}</ref>
* The [[Fibonacci cube]] is an [[undirected graph]] with a Fibonacci number of nodes that has been proposed as a [[network topology]] for [[parallel computing]].
* Fibonacci numbers appear in the [[ring lemma]], used to prove connections between the [[circle packing theorem]] and [[conformal map]]s.<ref>{{citation|last=Stephenson|first=Kenneth|isbn=978-0-521-82356-2|mr=2131318|publisher=Cambridge University Press|title=Introduction to Circle Packing: The Theory of Discrete Analytic Functions|title-link=Introduction to Circle Packing|year=2005}}; see especially Lemma 8.2 (Ring Lemma), [https://books.google.com/books?id=38PxEmKKhysC&pg=PA73 pp. 73–74], and Appendix B, The Ring Lemma, pp. 318–321.</ref>