I've been looking through my books on number theory and combinatorics, but none of them seem to mention anywhere the following simple relationship of Fibonacci sequence to combinations. In the following I use the notation nCr = n!/(n-r)!r! for the number of ways of choosing r from n.
An explicit sum for F(n) can be found by summing the upward diagonals of the combination table that lists n against r and is sometimes presented in the form of Pascal's Triangle.
It can be expressed in the general form:
F(n) = (n-1)C0 + (n-2)C1 + (n-3)C2 + (n-4)C3 + ... + (n-k)C(k-1)
= Summation (r=1 to k) (n-r)C(r-1).
Where k = n/2 or (n+1)/ when n is even or odd respectively.
In the symmetric form of Pascal's Triangle the upward diagonals are transformed into knight-lines.
Instead of the above elementary formula for F(n) that uses only addition, subtraction, multiplication and division of whole numbers, the mathematical texts focus on the exotic Binet formula that expresses F(n) in terms of root five, or root five and the golden ratios, which are irrational numbers that all cancel each other out.
A First Course of Combinatorial Mathematics by Ian Anderson (Oxford University Clarendon Press (1979) page 43 derives from the Binet formula a more complicated relationship involving the summation of expressions 5^r.(n+1)Cr divided by 2^n, but does not simplify it to the above form. This is the nearest I have found in my limited sources.
Of course there is also a simple relationship of 2^n to the combinations:
2^n = nC0 + nC1 + nC2 + ... + nCn.
Does anyone have other sources they could direct me to? (see my Knight's Tour pages for my email)
Does anyone have a concrete combinatorial explanation for the formula?
CORRECTION: I have since noticed that Anderson does mention the above expression briefly, without further explanation, in Exercises 4.2 (4) on page 44.
FURTHER: I have found another reference in Principles of Combinatorics by Claude Berge (Academic Press 1971) page 31, though it has n+1 instead of n. It implies that (n-k)Ck counts the number of ways of choosing k items from a row of n, but with no two items being adjacent.
FURTHER: I have modified the equation, since there seems to be some divergence in the way that the Fibonacci numbers are labelled. I take F(0) = 0 and F(1) = 1, so that F(2) = 1 and F(3) = 2 and so on, whereas other sources start from F(0) = 1, F(1) = 1, F(2) = 2, etc. I hope it is now correct!
