Recursions, Trains, Trees, and Combinatorial Rod Set Algebra

We explore a physical model of ordered sums of integers as trains of rods. The trains for a fixed, possibly infinite, set of rods naturally correspond to nodes in a tree; relations among finite linear recursions encoded in the subtrees define algebraic operations on sets of rods. We use this algebra to prove classic identities for recursively defined sequences, to show that some Lucas sequences are divisibility sequences, to characterize two-term linear Fibonacci identities, and to find the cyclotomic polynomial factors of Borwein trinomials. We complement abstractions with lots of examples.