1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.