The combinatorialization of linear recurrences

04/27/2010 - 12:15pm
04/27/2010 - 1:10pm
Art Benjamin (HMC)

We provide an original combinatorial proof of Binet's formula for Fibonacci numbers:

$$ F_n = (a^n - b^n)/\sqrt{5}, $$

where $a = (1 + \sqrt{5})/2$ and $b = (1 - \sqrt{5})/2$. Naturally, any k-th order linear recurrence with constant coefficients has a closed form solution, obtainable by factoring its (k-th degree) characteristic polynomial. We extend our proof of Binet's formula to show that these closed form solutions can also be given a combinatorial interpretation, even in the repeated roots situation. Based on joint work with Halcyon Derks and Jennifer Quinn.

Millikan 208 (Pomona College)