I am at the Southeastern Conference this week; I will say more about this later. Now, I simply want to add a post to my sequence on Fibonacci numbers, based on a lovely talk by Bruce Sagan. What I have to say here is a small subset of Bruce’s talk; you can find the slides on his website.
As everybody knows, the factorial function is defined for positive integers n by the rule that n! is the product of the integers from 1 to n. (By convention, 0!, which is an empty product, is taken to be 1.) Then the binomial coefficient, which I will write here as Bin(n,k), is defined for 0 ≤ k ≤ to be n!/k!(n−k)!.
In passing, although this is the definition that students prefer (it is compact and doesn’t take up too much space in the brain), I consider it to be a lousy definition, for various reasons, including computational. Try computing Bin(1000,2) on your calculator using this definition!
It is not clear à priori that the value defined in this way is necessarily a positive integer! Bruce pointed out that there are two standard ways to demonstrate this:
- by proving the recurrence relation Bin(n,0) = Bin(n,n) = 1 and Bin(n,k) = Bin(n−1,k−1)+Bin(n−1,k) for 0 < k < n;
- by giving an interpretation of the binomial coefficient as counting the size of a finite set (the example I will use here, not the first you would think of, is that Bin(n,k) is the number of lattice paths from the origin to the point (n−k,k) using unit steps in either the easterly or the northerly direction). [Exercise: match this up with your preferred interpretation!]
Now we are going to play a game, which involves taking the above definitions, and replacing the positive integer n by a term in some other sequence. The game is to find proofs (if it is true) that the terms in the sequence are positive integers.
First up are the Gaussian or q-binomial coefficients. We replace the positive integer n by the q-integer [n] = 1+q+…+qn−1. Now the q-factorial q-Fact(n) is the product of , , … [n]; the q-binomial coefficient (or Gaussian coefficient) is given by
q-Bin(n,k) = q-Fact(n)/q-Fact(k)q-Fact(n−k).
This is an integer for integral values of k, indeed it is a polynomial of degree k(n−k) with positive integer coefficients. Again, this is not immediately obvious. But it can be proved by analogues of the two methods above:
- by proving the recurrence relation q-Bin(n,0) = q-Bin(n,n) = 1 and q-Bin(n,k) = qk−1q-Bin(n−1,k−1)+q-Bin(n−1,k) for 0 < k < n;
- by giving a generating function interpretation: each lattice path counted by the binomial coefficient sits inside a n−k-by-k rectangle; weight it with qA, where A is the area above the path.
So far, so well-known (or at least it should be!) But what if we replace n by the Fibonacci number Fn? (We have to worry about the initial conditions of the recurrence, which we take to be F1 = F2 = 1. Other choices, as described here, don’t work!) Now we define the Fibonacci factorial or Fibotorial, by taking FibFact(n) to be the product of the Fibonacci numbers from F1 to Fn; and the Fibonacci binomial or Fibonomial coefficients by
FibBin(n,k) = FibFact(n)/FibFact(k)FibFact(n−k).
For example, FibFact(6) = 22.214.171.124.5.8 = 240, and FibBin(6,3) = 240/2.2 = 60.
As usual, we have the question, why are the Fibonomial coefficients integers? Again, as usual, there are two approaches.
The recurrence relation is FibBin(n,0) = FibBin(n,n) = 1 and
FibBin(n,k) = Fn−k−1FibBin(n−1,k−1)+Fk+1FibBin(n−1,k)
for 1 < k < n. (The proof is a nice exercise in Fibonacci number manipulation.)
The counting interpretation is more obscure. There are three of these, the simplest due to Bruce Sagan and Carla Savage. Take, as before, a lattice path inside the n−k-by-k rectangle. We weight this configuration by the number of ways that the rectangle can be tiled according to the following rules:
- The tiles are monominoes and dominoes, that is, 1-by-1 and 1-by-2 rectangles.
- In the part of the diagram above the lattice path, all dominoes are horizontal.
- In the part of the diagram below the lattice path, all dominoes are vertical; and the bottom tile in each column is a domino. (If this condition cannot be satisfied, then the number of tilings is zero.)
Now the theorem is that if we sum the weights of all the configurations inside the n−k-by-k rectangle, we obtain FibBin(n,k).
The implicit question here is, what other sequences of integers give integral values for the corresponding binomial coefficients, and can we find counting interpretations of them?