# Obtaining a recurrence from a rational generating function

Looking at some Generating functions of a series, I have conjectured -

If $G(x) \ =\ \frac{1}{1-x^{t_1}-x^{t_2}-...-x^{t_n}}$, then the recurrence equation of the the series is -

$a_n = a_{n-t_1}+a_{n-t_2}+...+a_{n-t_n}$

How can I prove or disprove this?

## 1 Answer

Suppose that $$G(x) = \sum_{n=0}^\infty g_n x^n.$$ Using the given equation (ending at $i_m$, a better choice of variables), we have $$1 = (1-x^{i_1}-\cdots-x^{i_m}) G(x) = \sum_{n=0}^\infty (1-x^{i_1}-\cdots-x^{i_m}) g_n x^n = \\ \sum_{n=0}^\infty g_n x^n - \sum_{n=i_1}^\infty g_{n-i_1} x^n - \cdots - \sum_{n=i_m}^\infty g_{n-i_m} x^n = \\ \sum_{n=i_m}^\infty (g_n - g_{n-i_1} - \cdots - g_{n-i_m}) x^n - H(x),$$ where $\deg H(x) < i_m$. Comparing coefficients, we find out that for $n \geq i_m$, $$g_n = g_{n-i_1} + \cdots + g_{n-i_m}.$$

More generally, you could have allowed coefficients in front of the monomials.

• Can you tell comparing coefficients with what? – Mr. Sigma. Feb 9 '18 at 4:58
• Comparing coefficients of both sides of the equation. – Yuval Filmus Feb 9 '18 at 11:25