A Tale of Two Sequences

Last week I came home happy one day because of a simple little math expression.  The Fibonacci sequence has the cool property that for each term, if a prior term's index is a divisor of the current index, then that term is also a divisor of the current term.  So, for example, F₁₅ is divisible by F₃ and F₅ (and an additional factor).  More formally, a divides b implies F_a divides F_b.  There are other sequences with this property, including 10ⁿ − 1 (or any bⁿ − 1).  But the Fibonacci sequence is a linear recurrence relation (each term is the sum of the two previous terms) and the sequence of one less than powers of ten is exponential.  I figured there must be some way to characterize what types of sequences can have this property.

Well, I still don't know if there are other types of sequences with this property, but I do now know why these two types share it.  I came across this relationship in a paper I found online, and as soon as I saw it I realized it could be generalized.  They are actually the same type, and can each be expressed as the other.  For instance, 10ⁿ − 1 can also be obtained using F_n = 11·F_n-1 − 10·F_n-2, and each linear recurrence sequence can also be made into a difference-of-powers sequence, though the base "b" may not be rational.

As with many techniques in math and physics, once you know there is an equivalence, it is trivial to set up a set of equations in that form and figure out the coefficients.  So, one the one hand I feel that I should have tried it sooner, but on the other I feel that if it were widely known then I would have run across mention of it sooner.  Regardless, I am happy to know a little bit more about a set of sequences which I find fascinating (more properties will get their own post one day).