Compute the generating function f(x) = sum_n f_n x^n where f_n satisfies your favorite recursion. Compute f(b^-1) where b is your base. For fibonacci f(x) = x / (1 - x - x^2).