Linear order of a recurrence relation
The statement says : A regular d-decimation doesn't change the order of a constant coefficient, linear, homogeneous recurrence relation.
The facts that i know are the generating functions of linear rec. relations are rational functions and they can be written as q(x)/p(x), where p(x) is the reciprocal of the characteristic equation of the relation. Then in order to obtain the generating functions of a d-decimation, I know that we should use the n-th roots of unity. But i can't prove that the order(complexity) is not effected by the decimation. Can you help me with this? Or at least do you know good combinatorics books which explain this topic in proof-first way?