Recurrence relations in the generating function of binary partitions

Question

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.

Answer 1

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.

Answer 2

The sequence $\,b(n)\,$ is OEIS sequence A018819 "Binary partition function: number of partitions of n into powers of 2.". The FORMULA section states:

$a(2m+1) = a(2m), a(2m) = a(2m-1) + a(m)$. Proof: If $n$ is odd there is a part of size $1$; removing it gives a partition of $n - 1$. If $n$ is even either there is a part of size $1$, whose removal gives a partition of $n - 1$, or else all parts have even sizes and dividing each part by $2$ gives a partition of $n/2$.

You asked

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?

but you did not explicitly state that you wanted to use the ordinary generating function $\,F(x).\,$ The first recurrence relation for $\,b(2n+1)\,$ is already given in the FORMULA entry. For $\,b(2n)\,$ we also get from the entry $\,b(2n) = b(2n-1)+b(n)\,$ but we already know that if $\,n\ge 1\,$ then $\,b(2n-1)=b(2n-2)\,$ and thus $\,b(2n)=b(2n-2)+b(n)\,$ as the second recurrence relation.

Your attempt using the g.f. $\,F(x)\,$ was flawed, but can be fixed up. $$ F(x) = \frac1{1-x}\prod_{n=1}^\infty \frac{1}{1-x^{2^{n}}} = \sum_{n=0}^\infty b(n)x^n. \tag{1}$$ Substitute $\,-x\,$ for $\,x\,$ to get $$ F(-x) = \frac1{1+x}\prod_{n=1}^\infty \frac{1}{1-x^{2^{n}}} = \sum_{n=0}^\infty b(n)(-x)^n. \tag{2}$$ Notice that $$ \frac12\Big(\frac1{1-x} + \frac1{1+x}\Big) = \frac1{1-x^2}, \quad \frac12\Big(\frac1{1-x} - \frac1{1+x}\Big) = \frac{x}{1-x^2}. \tag{3} $$ Add equation $(2)$ to $(1)$ and use equation $(3)$ to get the even part of $\,F(x)\,$ $$ \frac12(F(x)+F(-x)) = \frac1{1-x^2}\prod_{n=1}^\infty \frac{1}{1-x^{2^{n}}} = \sum_{n=0}^\infty \,b(2n)\,x^{2n}.\tag{4}$$ Subtract equation $(2)$ from $(1)$ and use equation $(3)$ to get the odd part $$ \frac12(F(x)-F(-x)) = \frac{x}{1-x^2}\prod_{n=1}^\infty \frac{1}{1-x^{2^{n}}} = \sum_{n=0}^\infty \,b(2n+1)\,x^{2n+1}.\tag{5}$$ Divide both sides of equation $(5)$ by $\,x\,$ to get $$ \frac1{1-x^2}\prod_{n=1}^\infty \frac{1}{1-x^{2^{n}}} = \sum_{n=0}^\infty \,b(2n+1)\,x^{2n}.\tag{6}$$ Equate coefficients in equations $(4)$ and $(6)$ to get $\,b(2n+1)=b(2n).\,$

From equation $(1)$ we get $$ (1-x)F(x) = \prod_{n=1}^\infty \frac{1}{1-x^{2^{n}}} = F(x^2) \tag{7}$$

and use equation $(1)$ again with $\,x\,$ replaced with $\,x^2\,$ to get $$ F(x^2) = \sum_{n=0}^\infty\, b(n)\,x^{2n} \tag{8}$$

and also $$ (1-x)F(x) = 1+\sum_{n=1}^\infty \,(b(n)-b(n-1))\, x^n. \tag{9} $$ Using equations $(7)$,$(8)$, and $(9)$ together to get $$ \sum_{k=0}^\infty\, b(k)\,x^{2k} = 1+\sum_{n=1}^\infty \,(b(n)-b(n-1))\, x^n. \tag{10} $$ Equating coefficients of $\,x^n\,$ when $\,n\,$ is even and odd gives the recurrence relations in the OEIS entry.

By the way, in equation $(4)$ replace $\,x^2\,$ with $\,x\,$ to get $$ \frac1{1-x}F(x) = \sum_{n=0}^\infty \,b(2n)\,x^n \tag{11}$$ and since $\,b(2n+1)=b(2n)\,$ the same left side is the generating function of $\,b(2n+1).\,$