  We show that any graph polynomial from a wide class of graph polynomials
yields a recurrence relation on an infinite class of families of graphs. The
recurrence relations we obtain have coefficients which themselves satisfy
linear recurrence relations. We give explicit applications to the Tutte
polynomial and the independence polynomial. Furthermore, we get that for any
sequence $a_{n}$ satisfying a linear recurrence with constant coefficients, the
sub-sequence corresponding to square indices $a_{n^{2}}$ and related
sub-sequences satisfy recurrences with recurrent coefficients.
