|
en.wikipedia.org/wiki/Fibonacci_sequence#Combinatorial_proofs
$ F_{n} $ can be interpreted as the number of (possibly empty) sequences of 1s and 2s whose sum is $ n-1 $. This can be taken as the definition of $ F_{n} $ with the conventions $ F_{0}=0 $, meaning no such sequence exists whose sum is −1, and $ F_{1}=1 $, meaning the empty sequence "adds up" to 0. In the following, $ |{...}| $ is the cardinality of a set:
$ F_{0}=0=|\{\}| $
$ F_{1}=1=|\{\{\}\}| $
$ F_{2}=1=|\{\{1\}\}| $
$ F_{3}=2=|\{\{1,1\},\{2\}\}| $
$ F_{4}=3=|\{\{1,1,1\},\{1,2\},\{2,1\}\}| $
$ F_{5}=5=|\{\{1,1,1,1\},\{1,1,2\},\{1,2,1\},\{2,1,1\},\{2,2\}\}| $ |
|