More elegant way of finding generating function coefficient

Question

I am looking to find the number of ways to pay a £50 bill in £1 and £2 coins. The generating function for this is $g(x)=(1+x+...)(1+x^2+...)$, which after a few lines of algebra becomes

$g(x) = \sum_{i=0}^{\infty}(1+i)x^i\sum_{j=0}^{\infty}(-1)^jx^j$.

The following is the only formula I can think of for finding the coefficient $\alpha$ of $x^{50}$ in $g(x)$

$\alpha = \sum_{k=0}^{50}(-1)^k(51-k) = 26$,

but this feels quite tedious. My first question is whether or not this answer is correct. The second is whether there is another, more elegant way to find this coefficient $\alpha$.

Answer 1

The number of ways to pay for a £50 bill is equivalent to the number of £2 coins that can be used to make an amount less than or equal to 50 as the rest of the bill can be paid with £1 coins. This leaves 26 options for the number of £2 coins: 0, 1, ... 25.

Answer 2

We need to find the number of ways to obtain $n$ from summing $1$ and $2$ (assuming order is unimportant, i.e. the $1$s are indistinguishable, as with the $2$s).

Note that the number of $2$s we can choose is anywhere from $0$ to $\lfloor {\frac{n}{2}} \rfloor$, and the number of $1$s is uniquely defined from the number of $2$s we choose. So the number of ways is $\lfloor \frac{n}{2} \rfloor + 1$, and this is the coefficient of $x^n$ in the generating function. So in the case of $n=50$, the coefficient is simply $26$.

Answer 3

The solution using generating series, as started in the OP, may go along the following lines:

We work in the power series ring $\Bbb Q[[x]]$, then the expression $E$ we want to expand around zero is $$ \begin{aligned} E &=(1+x+x^2+\dots)(1+x^2+x^4+\dots) \\ &=\frac 1{1-x}\cdot\frac 1{1-x^2} \\ &=\frac {1+x}{(1-x^2)^2} \\ &=(1+x)\left(1+2x^2+3x^4+4x^6+\dots+(k+1)x^{2k}+\dots\right) \ . \end{aligned} $$ The coefficient of $x^{50}=x^{2\cdot 25}$ in the last factor is the only one contributing to the product, this is $(25+1)$.

---

Computer check:

sage: R.<x> = PowerSeriesRing(QQ)
sage: 1/(1-x)/(1-x^2)
1 + x + 2*x^2 + 2*x^3 + 3*x^4 + 3*x^5 + 4*x^6 + 4*x^7 
  + 5*x^8 + 5*x^9 + 6*x^10 + 6*x^11 + 7*x^12 + 7*x^13 
  + 8*x^14 + 8*x^15 + 9*x^16 + 9*x^17 + 10*x^18 + 10*x^19 
  + O(x^20)

(Output was manually broken to fit in page.)

---

Note that in general, one has to use partial fraction decompositions (over $\Bbb C$) and for the pieces use as here the binomial coefficients from $(1+h)^{-N}=\sum_{k\ge 0}\binom{-N}kh^k$ for $h$ being a (complex) constant times a power of $x$. See also the comment of Gerry Myerson.

Answer 4

We use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series.

We obtain \begin{align*} \color{blue}{[x^{50}]g(x)}&=[x^{50}]\left(1+x+x^2+\cdots\right)\left(1+x^2+x^4+\cdots\right)\\ &=[x^{50}]\frac{1}{1-x}\cdot\frac{1}{1-x^2}\tag{1}\\ &=[x^{50}]\frac{1+x}{\left(1-x^2\right)^2}\\ &=\left([x^{50}]+[x^{49}]\right)\sum_{j=0}^\infty\binom{-2}{j}(-x^2)^j\tag{2}\\ &=\left([x^{50}]+[x^{49}]\right)\sum_{j=0}^\infty(j+1)x^{2j}\tag{3}\\ &\,\,\color{blue}{=26}\tag{4} \end{align*}

Comment:

• In (1) we use the geometric series expansion twice.

• In (2) we apply the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$ and use the binomial series expansion.

• In (3) we apply the rule $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.

• In (4) we select the coefficient of $x^{50}$ noting that the coefficient of $x^{49}$ does not contribute.