Jump to content

Fibonacci numbers: Difference between revisions

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''<sub>''n''+1</sub></math> ways to do this.  For example, if {{math|1=''n'' = 5}}, then {{math|1=''F''<sub>''n''+1</sub> = ''F''<sub>6</sub> = 8}} counts the eight compositions summing to 5:
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|1=''n'' = 5}}, then {{math|1=''F''<sub>''n''+1</sub> = ''F''<sub>6</sub> = 8}} counts the eight compositions summing to 5:


:{{math|1=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}}.
:{{math|1=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}}.
22

edits