Recurrence relations in the generating function of binary partitions

Let $b(n)$ denote the number of binary partitions of $n$, that is, the number of partitions of $n$ as the sum of powers of $2$. Define \begin{equation*} F(x) = \sum_{n=0}^\infty b(n)x^n = \prod_{n=0}^\infty \frac{1}{1-x^{2^{n}}}. \end{equation*} Clearly, $F(x)$ satisfies the functional equation \begin{equation*} (1-x)F(x) = F(x^2). \end{equation*} Then, we have recurrence relation $b(2n+1)=b(2n)$ and $b(2n) = b(2n-2) + b(n), n\ge1$.

How to derive these recurrence relation from the given informations?

What I tried: We have \begin{equation*} \sum_{n=0}^\infty b(2n)x^n = \prod_{n=0}^\infty \frac{1}{1-x^{2^{2n}}} \end{equation*} and \begin{equation*} \sum_{n=0}^\infty b(2n+1)x^n = \prod_{n=0}^\infty \frac{1}{1-x^{2^{2n+1}}}. \end{equation*} But, I didn't get those recurrence relation.

Let $[x^n]g(x)$ denote the $n$th coefficient in the power series of some function $g$.

Note that $[x^n](1-x)F(x)=[x^n]F(x)-[x^{n-1}]F(x)$, if $n\gt1$, and this is allegedly equal to $[x^n]F(x^2)$. Since $F(x^2)=\sum_{n=0}^\infty b(n)(x^2)^n=\sum_{n=0}^\infty b(n)x^{2n}$, that is $[x^{2n}]F(x)=b(n)$, we find:

$$\begin{align}b(n)=[x^{2n}]F(x^2)&=[x^{2n}](1-x)F(x)\\&=[x^{2n}]F(x)-[x^{2n-1}]F(x)\\&=b(2n)-b(2n-1)\\b(n)+b(2n-1)&=b(2n)\end{align}$$

Which is the second relation.

Observe that there are no odd powers of $x$ in $F(x^2)$; thus $[x^{2n+1}]F(x^2)=0$ for all $n$. Using the same logic, you find $b(2n+1)-b(2n)=0$ which gives the first relation.

More detail:

$$\begin{align}(1-x)F(x)&=\sum_{n=0}^\infty b(n)x^n-\sum_{n=0}^\infty b(n)x^{n+1}\\&=b(0)+\sum_{n=1}^\infty b(n)x^n-\sum_{n=1}^\infty b(n-1)x^n\\&=b(0)+\sum_{n=1}^\infty(b(n)-b(n-1))x^n\\\therefore[x^n](1-x)F(x)&=b(n)-b(n-1)=[x^n]F(x)-[x^{n-1}]F(x)\end{align}$$

Note:

The relations you gave at the end of your question were not at all obvious to me, and in general they would not be true. I'm not sure how you arrived at them, but I believe the argument was wrong in some way.

Answer to your questions in the comments:

“What is the generating function for $b(2n)$?” asks: “What is the power series $G$ so that $[x^n]G=b(2n)$?” This might not have been what you were trying to find out, but I’ll answer it anyway. I know very little about combinatorics and generating function-ology (I have not read that resource, but it’s all yours to read for yourself if you’re interested!), but I can help you here. For any power series $f$, the power series: $E(x)=\frac{1}{2}(f(x)+f(-x))$ is purely even. In our case, we will find $E(x)=\sum_{n=0}^\infty b(2n)x^{2n}$, so the desired generator for $b(2n)$ is: $G_{2n}(x)=E(\sqrt{x})=\sum_{n=0}^\infty b(2n)x^n$. Furthermore, because $b(2n+1)=b(2n)$, the generator for $b(2n-1)=b(2n-2)$ is: $$\begin{align}G_{2n-1}(x)&=x\cdot(G_{2n}(x))\\&=x\left(\sum_{n=0}^\infty b(2n)x^n\right)\\&=\sum_{n=0}^\infty b(2n)x^{n+1}=\sum_{n=1}^\infty b(2n-2)x^n\\&=\sum_{n=1}^\infty b(2n-1)x^n\end{align}$$To be clear, these functions are what you asked for since: $[x^n]G_{2n}(x)=b(2n)$ and $[x^n]G_{2n-1}(x)=b(2n-1)$, for all valid $n$.

Note that these functions will have different product representations to what you suggested; an exercise for you (it’s probably difficult - I’ve not tried - so don’t worry too much) might be to use the generating functions I’ve given you to find the correct products! Having said that, I’m not convinced about the product formula; the product is an even function of $x$, but the power series has odd components - I’m not familiar with partitions however, so I’ll leave you to figure that out / challenge your teacher.

As for why the second relation “implies $b(n)$ is even”, I think you’re asking why I chose to calculate $[x^{2n}]$ in the first bit of working out. I did so just... because! It was what worked, in order to figure out the relations. Feel free to clarify your question.