Linear Recurrences Give Rational Generating Functions