<s>[INST] Finding the generating function of a sequence for $n$ pennies 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.
 [/INST] 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$
</s>