Finding the generating function of a sequence for $n$ pennies

Question

Let $a_n$ count the number of different ways you can pay a sum of n pennies with 1p and 2p coins. Find the generating function and closed formula for $a_n$. I have attempted this question, finding $a_n$ to be $(1, 1, 2, 2, 3, 3, \ldots)$, and have started calculating the generating function $1 + x + 2 x^2 + 2 x^3 + \ldots$ but am not sure how to proceed from here? Hope someone can help me.

Answer 1

A direct way of thinking about the generating function is $(1+x+x^2+...)(1+x^2+x^4+x^6+...)={1\over1-x}\times{1\over1-x^2}$ where the first sequence represents the $1$ pennies and the second represents the $2$ pennies.

Now to find the closed form formula for $a_n$ basically you use the partial sum method to split ${1\over1-x}\times{1\over1-x^2}= {a\over 1-x}+{b\over(1-x)^2}+{c\over 1+x}$ and solve for $a,b$ to get $a+b+c=1,-a+c=0,b-2c=0$ and therefore $b={1\over 2},c={1\over 4},a={1\over 4}$ so the sequence is equal to ${1\over 4}(1+x+x^2+...)+{1\over 2}(1+2x+3x^2+4x^3+...)+{1\over 4}(1-x+x^2-x^3+...)$

When you look at the coefficient of $x^n$ you get ${1\over 4}+{1\over2}(n+1)+{1\over 4}(-1)^n$

Answer 2

You have already figured out, that the closed formula for $a_n$ is $\lceil \frac{n + 1}{2} \rceil$. So, the generating function for it is $\Sigma_{n = 1}^{\infty} a_nx^n = \Sigma_{n = 0}^{\infty} (n + 1)x^{2n}(1 + x) = (1 + x)\Sigma_{n = 0}^{\infty} (n + 1){(x^2)}^n = (1 + x)f(x^2)$, where $f(x) = (\frac{1}{1 - x})' = \frac{1}{(1 - x)^2}$. That means that your generating function is actually $\frac{1 + x}{(1 - x^2)^2} = \frac{1}{(1 - x^2)(1 - x)}$.