Congruence properties of binary partition function

Question

For every positive integer $n$, denote $b(n)$ be the number of binary partition of $n$, i.e., the number of partition of $n$ into power of two, where the power is decreasing. For instance, $b(5)=4$ since \begin{align*} &2^2+2^0, \\ &2^1+2^1+2^0, \\ &2^1+2^0+2^0+2^0, \\ &2^0+2^0+2^0+2^0. \end{align*} Also, for convenience, we set $b(0)=1$.

I want to show the following congruences: $$b(2^{2k+2}n)-b(2^{2k}n) \equiv 0 \pmod{2^{3k+2}}$$ and $$b(2^{2k+1}n)-b(2^{2k-1}n) \equiv 0 \pmod{2^{3k}}$$ for every positive integer $k$ and any positive integer $n$, using mathematical induction on $n$ and $k$.

Given that $b(n)$ have some relations:

1. $b(2n+1)=b(2n)$;
2. $b(2n)=b(2n-2)+b(n)$;
3. $b(2^mn)=\sum_{j=0}^{n} C_m(j)b(n-j)$,

for every positive integer $n$, where $C_{m+1}(j)=\sum_{i=0}^{2j}C_m(i)$, $C_1(j)=1$ for all $j \ge 0$, and $C_m(0)=1$ for all $m \ge 1$.

I want to prove the first congruence only, and the rest should follows.

By the third relation, I want to prove that $$\sum_{j=0}^{n} (C_{2k+2}(j)-C_{2k}(j))b(n-j) \equiv 0 \pmod {2^{3k+2}}. \tag{1}$$

For the base case, i.e., for $k=1=n$, we have $$\sum_{j=0}^{1} (C_{4}(j)-C_{2}(j))b(1-j) = (C_4(0)-C_2(0))b(1)+(C_4(1)-C_2(1))b(0) = 35-3 = 32 \equiv 0 \pmod {2^{3(1)+2}}.$$

For the inductive step, assume that Congruence $(1)$ holds. Want to show that it is also hold for $k+1$ and $n+1$, that is, $$\sum_{j=0}^{n} (C_{2k+4}(j)-C_{2k+2}(j))b(n-j) \equiv 0 \pmod {2^{3k+5}}. \tag{2}$$ and $$\sum_{j=0}^{n+1} (C_{2k+2}(j)-C_{2k}(j))b(n+1-j) \equiv 0 \pmod {2^{3k+2}}. \tag{3}$$ also holds.

But, I got stucked here and confusing what I should do. Any idea please? I need a help to show these congruences. Also, if any, I would very appreciated for another approach than using induction (simple and easy to understanding). Many thanks in advanced.

Answer 1

In Section 10.2 Rödseth's Theorem for Binary Partitions of The Theory of Partitions by G. Andrews we find the following:

• [G. Andrews]: ... The theorem above allows us to prove certain congruences for $b(4n)-b(n)$ originally conjectured by R. F. Churchhouse and proved independently by O. Rödseth and H. Gupta.

Theorem 10.2: If $k\geq 1$ and $n \equiv 1 \pmod {2}$, then \begin{align*} b(2^{2k+2}n)-b(2^kn)&\equiv 0 \pmod {2^{3k+2}}\tag{10.2.9}\\ b(2^{2k+1}n)-b(2^{2k-1}n)&\equiv 0 \pmod {2^{3k}}\tag{10.2.10}\\ \end{align*}

furthermore, (10.2.9) and (10.2.10) are best possible in that no higher power of $2$ divides $b(4n)-b(n)$.

The proof presented by G. Andrews is a proof by induction based on generating functions. Here I give some of the main ideas of the proof without going into all the details, since it is somewhat lengthy and technical.

Introduction: We define a generating function $B(q)$ for the $b(n), n\geq 0$ as \begin{align*} B(q)&=\sum_{n=0}^{\infty}b(n)q^n\\ &=\left(1+q+q^2+\cdots\right)\left(1+q^2+q^4+\cdots\right)\left(1+q^4+q^8+\cdots\right)\cdots\\ &=\prod_{n=0}^{\infty}\frac{1}{1-q^{2^{n}}}\tag{1} \end{align*} In order to work with generating functions to cope with expressions (10.2.9) and (10.2.10) we introduce an operator $U_m, m\geq 1$ as: \begin{align*} U_m\left(A\left(q\right)\right)=U_m\left(\sum_{n=0}^{\infty}a_nq^n\right)=\sum_{n=0}^{\infty}a_{mn}q^n \end{align*} Looking at (10.2.9) and (10.2.10) we take the operator $U_n$ and define a generating function $\mathcal{F}_m(q)$ as \begin{align*} \mathcal{F}_m(q)&=\left(U_{2^{m+1}}-U_{2^{m-1}}\right)B(q)\\ &=\sum_{n=0}^{\infty}\left(b\left(2^{m+1}n\right)-b\left(2^{m-1}n\right)\right)q^n\tag{2} \end{align*}

Claim reformulated: We can now state the claim formulated in theorem 10.2 in terms of generating functions.

• In order to show (10.2.10) we consider for $k\geq 1$: \begin{align*} \color{blue}{2^{-3k}\mathcal{F}_{2k}(q)}&=2^{-3k}\left(U_{2^{2k+1}}-U_{2^{2k-1}}\right)B(q)\\ &\,\,\color{blue}{=2^{-3k}\sum_{n=0}^{\infty}\left(b\left(2^{2k+1}n\right)-b\left(2^{2k-1}n\right)\right)q^n}\tag{3} \end{align*} and show that $2^{-3k}\mathcal{F}_{2k}(q)$ has integral coefficients only.

• In order to show (10.2.9) we consider for $k\geq 1$: \begin{align*} \color{blue}{2^{-3k-2}\mathcal{F}_{2k+1}(q)}&=2^{-3k-2}\left(U_{2^{2k+2}}-U_{2^{2k}}\right)B(q)\\ &\,\,\color{blue}{=2^{-3k-2}\sum_{n=0}^{\infty}\left(b\left(2^{2k+2}n\right)-b\left(2^{2k}n\right)\right)q^n}\tag{4} \end{align*} and show that $2^{-3k-2}\mathcal{F}_{2k+1}(q)$ has integral coefficients only.

Base step: $k=1$

We now show the claim for (3) and (4) for $k=1$. We want to calculate $\mathcal{F}_2$ and $\mathcal{F}_3$ and have at first to start with the calculation of $\mathcal{F}_1$.

Intermezzo I: Calculation of $\mathcal{F}_1(q)$: We obtain \begin{align*} \color{blue}{\mathcal{F}_{1}\left(q^4\right)}&=\left(U_{2^{4}}-U_{2^{0}}\right)B\left(q^4\right)\\ &=\sum_{n=0}^{\infty}\left(b(4n)-b(n)\right)q^{4n}\\ &=\frac{1}{4}\sum_{j=0}^3B\left(i^jq\right)-B\left(q^4\right)\tag{5.1}\\ &=\frac{1}{4}\sum_{j=0}^3\prod_{n=0}^{\infty}\frac{1}{1-i^{j2^{n}}q^{2^{n}}}-\prod_{n=0}^{\infty}\frac{1}{1-q^{2^{n+2}}}\tag{5.2}\\ &=\prod_{n=2}^{\infty}\frac{1}{1-q^{2^{n}}}\left(\frac{1}{4}\sum_{j=0}^3\frac{1}{\left(1-i^{j}q\right)\left(1-i^{2j}q^2\right)}-1\right)\tag{5.3}\\ &=\prod_{n=2}^{\infty}\frac{1}{1-q^{2^{n}}}\left(\frac{1}{4}\sum_{j=0}^3 \frac{\left(1+i^jq\right)\left(1+i^{2j}q^2\right)}{\left(1-q^4\right)^2}-1\right)\\ &=\frac{1}{\left(1-q^4\right)^2}\prod_{n=2}^{\infty}\frac{1}{1-q^{2^{n}}}\left(1+q^4-\left(1-q^4\right)^2\right)\\ &=\frac{q^4\left(3-q^4\right)}{\left(1-q^4\right)^3}\prod_{n=3}^{\infty}\frac{1}{1-q^{2^{n}}}\\ &\,\,\color{blue}{=\frac{q^4\left(3-q^4\right)}{\left(1-q^4\right)^3}\prod_{n=1}^{\infty}\frac{1}{1-\left(q^4\right)^{2^{n}}}}\tag{5.4}\\ \end{align*} Substituting $q^4\to q$ in (5.4) gives: \begin{align*} \color{blue}{\mathcal{F}_1(q)}&\color{blue}{=\frac{q(3-q)}{(1-q)^3}G(q)}\tag{5.5}\\ \color{blue}{G(q)}&\color{blue}{=\prod_{n=1}^{\infty}\frac{1}{1-q^{2^{n}}}=(1-q)B(q)}\tag{5.6} \end{align*}

Comment:

• In (5.1) we use multisection of series.

• In (5.2) we use the series representation (1) for $B(q)$.

• In (5.3) we factor out the common product $\prod_{n=2}^{\infty}\frac{1}{1-q^{2^{n}}}$.

Base step $k=1$ (continued):

We calculate $\mathcal{F}_2$ with the help of $\mathcal{F}_1$ as \begin{align*} \color{blue}{\mathcal{F}_2\left(q^2\right)}&=\frac{1}{2}\left(\mathcal{F}_1(q)+\mathcal{F}_1(-q)\right)\\ &=\frac{1}{2}qG(q)\left(\frac{3-q}{(1-q)^3}-\frac{3+q}{(1+q)^3}\right)\\ &\,\,\color{blue}{=\frac{8q^2G(q)}{\left(1-q^2\right)^3}}\\ \color{blue}{\mathcal{F}_2(q)}&\color{blue}{=\frac{8qG(q)}{(1-q)^4}}\tag{6} \end{align*}

Comment:

• In (6) we use \begin{align*} G\left(q^2\right)=\prod_{n=1}^{\infty}\frac{1}{1-q^{2^{n+1}}}=\prod_{n=2}^{\infty}\frac{1}{1-q^{2^{n}}}=\left(1-q^2\right)G(q) \end{align*}

In a similar way we derive \begin{align*} \color{blue}{\mathcal{F}_3\left(q^2\right)}&=\frac{1}{2}\left(\mathcal{F}_2(q)+\mathcal{F}_2(-q)\right)\\ &=\frac{4qG(q)}{\left(1-q^2\right)^4}\left((1+q)^4-(1-q)^4\right)\\ &\,\,\color{blue}{=\frac{32q^2G(q)\left(1+q^2\right)}{\left(1-q^2\right)^4}}\\ \color{blue}{\mathcal{F}_3(q)}&\color{blue}{=\frac{32qG(q)(1+q)}{(1-q)^5}}\tag{7} \end{align*}

We obtain from (6) and (7) \begin{align*} \color{blue}{\frac{1}{8}\mathcal{F}_{2}(q)}&=\frac{qG(q)}{(1-q)^4} =\frac{qB(q)}{(1-q)^3}\tag{8.1}\\ &\equiv\frac{q}{(1-q)^2}\equiv\color{blue}{\sum_{j=0}^{\infty}q^{2j+1}\pmod{2}}\tag{8.2}\\ \color{blue}{\frac{1}{32}\mathcal{F}_{3}(q)}&=\frac{qG(q)(1+q)}{(1-q)^5} =\frac{qB(q)(1+q)}{(1-q)^4}\equiv\frac{qB(q)}{(1-q)^3}\tag{8.3}\\ &\equiv\frac{q}{(1-q)^2} \equiv\color{blue}{\sum_{j=0}^{\infty}q^{2j+1}\pmod{2}}\tag{8.2}\\ \end{align*} and the claim for $k=1$ follows. We note that thanks to the right-hand representation $\sum_{j=0}^{\infty}q^{2j+1}\pmod{2}$ we have additionally shown that no higher power of $2$ divides $b(4n)-b(n)$ as claimed in Theorem 10.2 above.

Comment:

• In (8.1) we use the identity (5.6).

• In (8.2) we note the sequence $(b(n))_{n\geq 0}=(1,1,2,2,4,4,6,6,10,10,14,14,\ldots)$ stored as A018819 in OEIS has even entries for $n\geq 2$. It follows for example from the first few entries of the sequence together with the identities \begin{align*} b(2n+1)&=b(2n)\\ b(2n)&=b(2n-2)+b(n) \end{align*} stated as 1.) and 2.) by OP (and easily verified using the generating function $G(q)$). It follows that \begin{align*} \frac{1}{1-q}B(q)&=\frac{1}{1-q}\sum_{n=0}^{\infty}b(n)q^n\\ &=\sum_{n=0}^{\infty}\left(\sum_{j=0}^nb(j)\right)q^n \equiv b(0)\equiv 1\pmod{2} \end{align*}

• In (8.3) we also use \begin{align*} \frac{1+q}{1-q}&=\left(1+q+q^2+q^3+\cdots\right)+\left(q+q^2+q^3+q^4\cdots\right)\\ &=1+2q+2q^2+2q^3+\cdots\equiv 1\pmod{2} \end{align*}

Intermezzo II: Another relationship between $\mathcal{F}_m(q)$ and $G(q)$:

In Order to prove the induction step we need a formula in terms of the generating functions $\mathcal{F}_m$ and $G(q)$ corresponding to OPs stated formula 3.). We can derive from (6) and (7) after some calculations \begin{align*} \mathcal{F}_3(q)+4\mathcal{F}_2(q)&=\frac{64qG(q)}{(1-q)^5}\tag{9}\\ \end{align*} and applying $U_2$ to (9) \begin{align*} \mathcal{F}_4(q)+16\mathcal{F}_3(q)+40\mathcal{F_2}(q)&=\frac{1024qG(q)}{(1-q)^6} \end{align*}

• This can be generalized and is stated by G. Andrews as Theorem 10.1.

  Theorem 10.1: There exist integers $c_j(m)$ such that for $m\geq 2$ \begin{align*} \color{blue}{\sum_{j=0}^{m-2}c_j(m)\mathcal{F}_{m-j}(q)=\frac{2^{\binom{m+1}{2}}qG(q)}{(1-q)^{m+2}}}\tag{10} \end{align*}

  furthermore, $c_0(m)=1, 16|c_1(m)$ if $m\geq 4, 8|c_2(m), 16 \not|\;\;\; c_2(m)$, and $2^{2j}|c_j(m)$, for $3\leq j\leq m-2$.

The following induction step is nearly verbatim from the book.

Induction step:

We are now ready to prove the induction step. Assuming that Theorem 10.2 is true for all integers less than $k$.

• Then by Theorem 10.1 we obtain \begin{align*} 2^{-3k}&\mathcal{F}_{2k}(q)+2^{-3k}c_1(2k)\mathcal{F}_{2k-1}(q)+2^{-3k}c_2(2k)\mathcal{F}_{2k-2}(q)\\ &+\sum_{j=3}^{2k-2}2^{-3k}c_j(2k)\mathcal{F}_{2k-j}(q) =\frac{2^{\binom{2k+1}{2}-3k}qG(q)}{(1-q)^{2k+2}} \end{align*} By Theorem 10.1, $16|c_1(2k), 8|c_2(2k)$, and $2^{2j}|c_j(2k)$, also for $k>1$, \begin{align*} \binom{2k+1}{2}-3k>0 \end{align*} Hence from the induction hypothesis we see that $2^{-3k}\mathcal{F}_{2k}(q)$ has integral coefficients. Furthermore since $16 \not|\;\;\; c_2(2k)$, \begin{align*} \color{blue}{2^{-3k}\mathcal{F}_{2k}(q)\equiv2^{-3k+3}\mathcal{F}_{2k-2}(q)\equiv\sum_{j=0}^{\infty}q^{2j+1}\pmod{2}} \end{align*} and the claim (3) which is the reformulated claim (10.2.10) follows.

• Now by Theorem 10.1 we obtain \begin{align*} 2^{-3k-2}&\mathcal{F}_{2k+1}(q)+2^{-3k-2}c_1(2k+1)\mathcal{F}_{2k}(q) +2^{-3k-2}c_2(2k+1)\mathcal{F}_{2k-1}(q)\\ &+\sum_{j=3}^{2k-2}2^{-3k-2}c_j(2k+1)\mathcal{F}_{2k+1-j}(q) =\frac{2^{\binom{2k+2}{2}-3k-2}qG(q)}{(1-q)^{2k+3}} \end{align*} Again by Theorem 10.1, $16|c_1(2k+1), 8|c_2(2k+1), 2^{2j}|c_j(2k)$, also for $k>1$, \begin{align*} \binom{2k+2}{2}-3k-2>0 \end{align*} Hence from the induction hypothesis we see that $2^{-3k-2}\mathcal{F}_{2k+1}(q)$ has integral coefficients. Furthermore since $16 \not|\;\;\; c_2(2k+1)$, \begin{align*} \color{blue}{2^{-3k-2}\mathcal{F}_{2k+1}(q)\equiv2^{-3k+1}\mathcal{F}_{2k-1}(q)\equiv\sum_{j=0}^{\infty}q^{2j+1}\pmod{2}} \end{align*} and the claim (4) which is the reformulated claim (10.2.9) follows. \begin{align*} \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\Box \end{align*}

---

Add-on: With respect to OPs comment we consider the induction hypothesis and analyse in detail that $2^{-3k}\mathcal{F}_{2k}(q)$ has integral coefficients. From (10) we obtain letting $m=2k$ for $k\geq 1$: \begin{align*} \sum_{j=0}^{2k-2}c_j(2k)\mathcal{F}_{2k-j}(q)=\frac{2^{\binom{2k+1}{2}}qG(q)}{(1-q)^{2k+2}}\tag{11} \end{align*} We multiply (11) with $2^{-3k}$ and separate from the left-hand sum the first three terms. We obtain \begin{align*} 2^{-3k}&\mathcal{F}_{2k}(q)+2^{-3k}c_1(2k)\mathcal{F}_{2k-1}(q)+2^{-3k}c_2(2k)\mathcal{F}_{2k-2}(q)\\ &+\sum_{j=3}^{2k-2}2^{-3k}c_j(2k)\mathcal{F}_{2k-j}(q) =\frac{2^{\binom{2k+1}{2}-3k}qG(q)}{(1-q)^{2k+2}}\tag{12} \end{align*}

• We start with $\mathcal{F}_{2k-2}(q)$: We know from (3) and the induction hypthesis by taking $k-1$ that \begin{align*} 2^{-3(k-1)}\mathcal{F}_{2(k-1)}(q)=2^{-3k}\cdot 8\mathcal{F}_{2k-2}(q) \end{align*} has integral coefficients. Since we know from Theorem 10.1 that $8|c_2(2k)$ it follows \begin{align*} \color{blue}{2^{-3k}c_2(2k)\mathcal{F}_{2k-2}(q)} \end{align*} has integral coefficients.

• Now we look at $\mathcal{F}_{2k-1}(q)$: We know from (4) and the induction hypothesis by taking $k-1$ that \begin{align*} 2^{-3(k-1)-2}\mathcal{F}_{2(k-1)+1}(q)=2^{-3k}\cdot 2\mathcal{F}_{2k-1}(q) \end{align*} has integral coefficients. Since we know from Theorem 10.1 that $16|c_1(2k)$ it follows \begin{align*} \color{blue}{2^{-3k}c_1(2k)\mathcal{F}_{2k-1}(q)} \end{align*} has integral coefficients.

• Next we consider the terms $\mathcal{F}_{2k-2j}, j\geq 1$ of the sum with even index. We know from (3) and the induction hypothesis by taking $k-j$ that \begin{align*} 2^{-3(k-j)}\mathcal{F}_{2(k-j)}(q)=2^{-3k}\cdot 2^{3j}\mathcal{F}_{2k-2j}(q) \end{align*} has integral coefficients. Since we know from Theorem 10.1 that $2^{4j}|c_{2j}(2k)$ it follows \begin{align*} \color{blue}{2^{-3k}c_{2j}(2k)\mathcal{F}_{2k-2j}(q)} \end{align*} has integral coefficients.

• Now we consider the terms $\mathcal{F}_{2k-2j-1}, j\geq 1$ of the sum with odd index. We know from (4) and the induction hypothesis by taking $k-j$ that \begin{align*} 2^{-3(k-j-1)-2}\mathcal{F}_{2(k-j)-1}(q)=2^{-3k}\cdot 2^{3j+1}\mathcal{F}_{2k-2j-1}(q) \end{align*} has integral coefficients. Since we know from Theorem 10.1 that $2^{4j+2}|c_{2j+1}(2k)$ it follows \begin{align*} \color{blue}{2^{-3k}c_{2j+1}(2k)\mathcal{F}_{2k-2j-1}(q)} \end{align*} has integral coefficients.

• Finally we note that for $k>1$ we obtain \begin{align*} \binom{2k+2}{2}-3k-2>0 \end{align*} and it follows \begin{align*} \color{blue}{\frac{2^{\binom{2k+2}{2}-3k-2}qG(q)}{(1-q)^{2k+3}}} \end{align*} is a generating function with integral coefficients.

We conclude from (12) and the derivations above $2^{-3k}\mathcal{F}_{2k}(q)$ has integral coefficients and the induction hypothesis is shown for it. Similarly we derive that $2^{-3k-2}\mathcal{F}_{2k+1}(q)$ has integral coefficients.