computed Fibonacci number (recursion with memoization).

Combinatorial identities

Combinatorial proofs

Most identities involving Fibonacci numbers can be proved using combinatorial arguments using the fact that can be interpreted as the number of (possibly empty) sequences of 1s and 2s whose sum is . This can be taken as the definition of with the conventions , meaning no such sequence exists whose sum is -1, and , meaning

1.Previous
3.Next