22
edits
Difference between revisions of "Fibonacci numbers"
→Mathematics
| Line 20: | Line 20: | ||
:<math>F_n = \sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor} \binom{n-k-1}{k}</math> | :<math>F_n = \sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor} \binom{n-k-1}{k}</math> | ||
Counting the number of ways of writing a given number <math>n</math> as an ordered sum of 1s and 2s (called [[Composition (combinatorics)|compositions]]); there are <math>F_{n+1}</math> ways to do this. For example, if | Counting the number of ways of writing a given number <math>n</math> as an ordered sum of 1s and 2s (called [[Composition (combinatorics)|compositions]]); there are <math>F_{n+1}</math> ways to do this. For example, if <math>n = 5</math>, then <math>F_{n+1} = F_{6} = 8</math> counts the eight compositions summing to 5: | ||
<math>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</math> | |||
== Resources: == | == Resources: == | ||