1. ## Proving Generating Functions

Let an denote the solutions of n = x1 + x2 where x1, x2 are natural numbers and x2 is an even number.

I need to show that the generating function of an is of the form:
(1 + x + x^2 + x^3 + ...)(1 + x^2 + x^4 + x^6 + ...) = 1/[(1-x)(1-x^2)]

I ultimately want to find a closed formula for an. However I would like to prove the above first before I go about doing that. Any ideas would be great. Thanks!

2. So $a_n$ is the *number* of solutions to $n = x_1 + x_2$? Are $x_1$ and $x_2$ distinct? For example for $a_6$, are 6=4+2 and 6=2+4 two separate solutions, so $a_6 = 2$, or is $a_6 = 1$?

3. Originally Posted by mathmaniac234
Let an denote the solutions of n = x1 + x2 where x1, x2 are natural numbers and x2 is an even number.

I need to show that the generating function of an is of the form:
(1 + x + x^2 + x^3 + ...)(1 + x^2 + x^4 + x^6 + ...) = 1/[(1-x)(1-x^2)]

I ultimately want to find a closed formula for an. However I would like to prove the above first before I go about doing that. Any ideas would be great. Thanks!
Hi mathmaniac,

You just have to think about the coefficient of $x^n$ in the product
$(1 + x + x^2 + x^3 + \dots)(1 + x^2 + x^4 + x^6 + \dots)$.
In order to get an $x^n$, you need one term from
$1 + x + x^2 + x^3 + \dots$
which can be any power of x, say $x^i$
and one term from
$1 + x^2 + x^4 + x^6 + \dots$
which can be any even power of x, say $x^{2j}$.
Then you must have $x^i \cdot x^{2j} = x^n$,
i.e.
$i + 2j = n$.

The number of solutions to this equation is the coefficient of $x^n$ in the product.