Combinatorial interpretation of convergent series

Question

Given a series $$ \sum_{n=0}^\infty c_n x^n$$ that converges to $$ {1\over (1-x-x^{17}+x^{18})}$$ I am asked to give a combinatorical interpretation of $c_{10}$, more specifically in regards to a counting coin problem. I am having difficulty even starting an approach to this problem.

Answer 1

HINT

your RHS is a generating function of a certain power series. You have to simplify that generating function and try to understand what counting process results in having this generating function as a result.

Note in particular that $$1-x-x^{17}+x^{18} = (1-x) - x^{17}(1-x) = (1-x)\left(1-x^{17}\right),$$ so your GF is a product of two. What series generates each one? Can you interpret them combinatorially?

Then, $c_{10}$ is the coefficient of $x^{10}$ in the power expansion.

Answer 2

If you don’t see the factorization, you can still solve the problem. Let $g(x)=\sum_{n\ge 0}c_nx^n$. Then

$$\left(1-x-x^{17}+x^{18}\right)g(x)=1\;,$$

so

$$\begin{align*} \sum_{n\ge 0}c_nx^n&=g(x)\\ &=xg(x)+x^{17}g(x)-x^{18}g(x)+1\\\\ &=x\sum_{n\ge 0}c_nx^n+x^{17}\sum_{n\ge 0}c_nx^n-x^{18}\sum_{n\ge 0}c_nx^n+1\\\\ &=\sum_{n\ge 0}c_nx^{n+1}+\sum_{n\ge 0}c_nx^{n+17}-\sum_{n\ge 0}c_nx^{18}+1\\\\ &=\sum_{n\ge 1}c_{n-1}x^n+\sum_{n\ge 17}c_{n-17}x^n-\sum_{n\ge 18}c_{n-18}x^n+1\;. \end{align*}$$

Now equate coefficients of $x^n$ for each $n\ge 0$. For $n=0$, for instance, on the left we have $c_0$, and on the right we have only the trailing $1$, since the three summations all start at some $n>0$, so $c_0=1$. For $n=1$ we have $c_1$ on the left and $c_0$ on the right, so $c_1=c_0=1$. Continue in this fashion to see what happens for $1\le n\le 16$, for $n=17$, and for $n\ge 18$. When you’ve done this, you’ll have a recurrence for $c_n$ with initial conditions; try to interpret it in terms of a coin problem with two values of coin.

(This is essentially the reverse of the process for converting a recurrence into a generating function.)