Difference between revisions of "Fibonacci numbers"

Jump to navigation Jump to search
40 bytes removed ,  00:42, 20 October 2022
no edit summary
 
Line 15: Line 15:


==Mathematics==
==Mathematics==
The ratio \( \frac {F_n}{F_{n+1}} \ \) approaches the [[golden ratio]] as \(n\) approaches infinity.
The ratio \( \frac {F_n}{F_{n+1}} \ \) approaches the golden ratio as \(n\) approaches infinity.
[[File:PascalTriangleFibanacci.png|thumb|right|360px|The Fibonacci numbers are the sums of the "shallow" diagonals (shown in red) of [[Pascal's triangle]].]]
[[File:PascalTriangleFibanacci.png|thumb|right|360px|The Fibonacci numbers are the sums of the "shallow" diagonals (shown in red) of [[Pascal's triangle]].]]
The Fibonacci numbers occur in the sums of "shallow" diagonals in [[Pascal's triangle]].
The Fibonacci numbers occur in the sums of "shallow" diagonals in Pascal's triangle.
:$$F_n = \sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor} \binom{n-k-1}{k}$$
:$$F_n = \sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor} \binom{n-k-1}{k}$$


Counting the number of ways of writing a given number \(n\) as an ordered sum of 1s and 2s (called [[Composition (combinatorics)|compositions]]); there are \(F_{n+1}\) ways to do this.  For example, if \(n = 5\), then \(F_{n+1} = F_{6} = 8\) counts the eight compositions summing to 5:
Counting the number of ways of writing a given number \(n\) as an ordered sum of 1s and 2s (called compositions); there are \(F_{n+1}\) ways to do this.  For example, if \(n = 5\), then \(F_{n+1} = F_{6} = 8\) counts the eight compositions summing to 5:


$$1+1+1+1+1 = 1+1+1+2 = 1+1+2+1 = 1+2+1+1 = 2+1+1+1 = 2+2+1 = 2+1+2 = 1+2+2$$
$$1+1+1+1+1 = 1+1+1+2 = 1+1+2+1 = 1+2+1+1 = 2+1+1+1 = 2+2+1 = 2+1+2 = 1+2+2$$

Navigation menu