Understanding a Proof Related to Binary Partitions

Question

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

• For $q \in \Bbb C$ with $|q|<1$, \begin{align} \mathcal{F}_2(q) &= \frac{8qG(q)}{(1-q)^4} \tag{10.2.5} \label{1} \\ \mathcal{F}_3(q) + 4\mathcal{F}_2(q) &= \frac{64qG(q)}{(1-q)^5} \tag{10.2.7} \label{2} \\ \mathcal{F}_4(q) + 16\mathcal{F}_3(q) + 40\mathcal{F}_2(q) &= \frac{1024qG(q)}{(1-q)^6} \tag{10.2.8} \label{3}. \end{align}
• [G. Andrews]: It is now possible ti prove Theorem 10.1, which generalizes \eqref{1},\eqref{2}, and \eqref{3}.

THEOREM 10.1. There exist integers $c_j(m)$ such that for $m \ge 2$ $$\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}};$$ furthermore, $c_0(m)=1, 16 \mid c_1(m)$ if $m \ge 4$, $8 \mid c_2(m), 16 \nmid c_2(m)$, and $2^{2j} \mid c_j(m)$, for $3 \le j \le m-2$.

Also, G. Andrews the proof here by induction on $m$. I tried to follow the proof. I understand only in base step for $m=2,3,$ and $4$. I got confuse in the inductive step. How to write the inductive step?

Is it goes like follows: Assume the Theorem to be true for $m=s \ge 5$. We want to show that it also true for $m=s+1$. By the induction hypothesis, since $$\sum_{j=0}^{s-2} c_j(s) \mathcal{F}_{s-j}(q) = \frac{2^{\binom{s+1}{2}}qG(q)}{(1-q)^{s+2}},$$ then $$\sum_{j=0}^{s-1} c_j(s+1) \mathcal{F}_{s+1-j}(q) = \frac{2^{\binom{s+2}{2}}qG(q)}{(1-q)^{s+3}}.$$ Now, it is suffices to show the property of $c_j(s+1)$ for any $s \ge 5$, and so on?

Am I true? If yes, then I'm done since I'm only confusing on this step with doubt. Also, my second confusion was, why and how we define the integer $\delta_k(m+2)$ like in the Andrew's proof, that is,

Now, we define integers $\delta_k(m+2)$ for $0 \le k \le \lfloor \frac{m+1}{2} \rfloor$ by $$\frac{1}{2}\left((1+q)^{m+2} - (1-q)^{m+2} \right) = q \sum_{k=0}^{\lfloor \frac{m+1}{2} \rfloor} \delta_k(m+2) (1-q^2)^k;$$ this equation truly defines integers $\delta_k(m+2)$ since the left hand side of the equation is an odd polynomial. Furthermore, we see that $$\delta_0(m+2) = 2^{m+1}.$$

I didn't get it yet. How was $\delta_0(m+2)=2^{m+1}$?

Any ideas and helps? Thanks in advance.

Answer 1

Here I will follow the proof by induction of Theorem 10.1 presented by G. E. Andrews. I will go into more details than given in the book which might be helpful to understand some crucial steps. The proof is highly instructive, far from being obvious, at least for me and it was a pleasure to analyse and learn from it. In fact all OP is wondering about is part of the induction step and crucial in order to prove the claim.

Since the claim was already shown to be valid for $m=2,3$ and $4$ we show the claim is valid for $m\geq 5$. We recall the induction hypothesis:

Induction hypothesis: We assume for a given $m\geq 5$ \begin{align*} \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{1} \end{align*} and show the validity of the induction step

Induction step: \begin{align*} \color{blue}{\sum_{j=0}^{m-1} c_j(m+1) \mathcal{F}_{m-j+1}(q) = \frac{2^{\binom{m+2}{2}}qG(q)}{(1-q)^{m+3}}}\tag{2} \end{align*}

Hint: A strategy to prove (2) could be to start with the left-hand side of (2), transform it in a way to apply the assumed identity (1) and find this way the right-hand side of (2). It is not admissible to simply replace in both sides of (1) the variable $m$ by $m+1$. We have to constructively use the identity (1) to derive (2).

Some preliminaries: Before we start with the proof we need to recall some players of the game.

• We consider a generating function $B(q)$ of all binary partitions and define \begin{align*} \color{blue}{B(q)}&=\sum_{n=0}^{\infty}b(n)q^n\color{blue}{=\prod_{n=0}^{\infty}\left(1-q^{2^n}\right)^{-1}}\\ \color{blue}{G(q)}&=\prod_{n=1}^{\infty}\left(1-q^{2^n}\right)^{-1} \color{blue}{=(1-q)B(q)} \end{align*}

• In the following we want to relate $\mathcal{F}_{m}(q)$ with $\mathcal{F}_{m+1}(q)$ in order to apply the induction hypothesis. It turns out to be useful to introduce an operator $U_m$. Given a generating function $f(q)=\sum_{n=-\infty}^{\infty}a_nq^n$ the operator $U_m$ is defined as \begin{align*} \color{blue}{U_m\{f(q)\}=\sum_{n=-\infty}^{\infty}a_{mn}q^n} \end{align*} We are interested in the special case \begin{align*} U_2\{f\left(q^2\right)\}=\sum_{n=-\infty}^{\infty}a_{2n}q^{2n} \end{align*}

• We also need another operator $\mathcal{F}_m$ defined as \begin{align*} \color{blue}{\mathcal{F}_m(q)}&\color{blue}{=\left(U_{2^{m+1}}-U_{2^{m-1}}\right)B(q)}\tag{3}\\ &=\sum_{n=0}^{\infty}\left(b\left(2^{m+1}n\right)-b\left(2^{m-1}n\right)\right)q^n \end{align*}

• We derive a formula from (3) which is needed in the proof below. We obtain \begin{align*} \color{blue}{\frac{1}{2}}&\color{blue}{\left(\mathcal{F}_m(q)+\mathcal{F}_{m}(-q)\right)}\tag{4.1}\\ &=\frac{1}{2}\sum_{n=0}^\infty\left(b\left(2^{m+1}n\right)-b\left(2^{m+1}n\right)\right)q^n\\ &\qquad+\frac{1}{2}\sum_{n=0}^\infty\left(b\left(2^{m+1}n\right)-b\left(2^{m+1}n\right)\right)\left(-q^n\right)\\ &=\sum_{n=0}^{\infty}\left(b\left(2^{m+2}n\right)-b\left(2^mn\right)\right)q^{2n}\\ &\,\,\color{blue}{=\mathcal{F}_{m+1}\left(q^2\right)=U_2\mathcal{F}_m\left(q^2\right)}\tag{4.2} \end{align*}

Formula (4) looks quite useful as it connects $\mathcal{F}_m$ with $\mathcal{F}_{m+1}$.

Induction step part 1: We start with the left-hand side of (2) but for convenience with $q^2$ instead of $q$. Here we apply the induction hypothesis (1) the first time. We obtain \begin{align*} \color{blue}{\sum_{j=0}^{m-2}}&\color{blue}{c_j(m)\mathcal{F}_{m+1-j}\left(q^2\right)}\tag{5.1}\\ &=\sum_{j=0}^{m-2}c_j(m)U_2\mathcal{F}_{m-j}\left(q^2\right)\tag{$\to 4.2$}\\ &=\sum_{J=0}^{m-2}c_j(m)\frac{1}{2}\left(\mathcal{F}_{m-j}(q)+\mathcal{F}_{m-j}(-q)\right)\tag{$\to 4.1$}\\ &=\frac{1}{2}\,\frac{2^{\binom{m+1}{2}}qG(q)}{(1-q)^{m+2}} -\frac{1}{2}\,\frac{2^{\binom{m+1}{2}}(-q)G(-q)}{(1+q)^{m+2}}\tag{$\to 1$}\\ &=\frac{1}{2}\,2^{\binom{m+1}{2}}qG(q)\left(\frac{1}{(1-q)^{m+2}}-\frac{1}{(1+q)^{m+2}}\right)\\ &\color{blue}{=\frac{1}{2}\,\frac{2^{\binom{m+1}{2}}}{\left(1-q^2\right)^{m+2}} \left((1+q)^{m+2}-(1-q)^{m+2}\right)}\tag{5.2}\\ \end{align*}

A short break: Let's look at (5.2). The left factor looks promising compared with the right-hand side of (1) and (2). Somewhat problematic are the binomials $(1+q)^{m+2}$ and $(1-q)^{m+2}$. It would be nice if we had instead factors $(1-q^2)^k$ which could be cancelled/merged with the denominator $\left(1-q^2\right)^{m+2}$. This is the program for the next step.

Induction step part 2: We continue with the right-hand side of (5) and obtain

\begin{align*} \color{blue}{\frac{1}{2}}&\color{blue}{\left((1+q)^{m+2}-(1-q)^{m+2}\right)}\\ &=\frac{1}{2}\sum_{k=0}^{m+2}\binom{m+2}{k}\left(q^k-(-q)^k\right)\\ &=\sum_{k=0}^{m+2}\binom{m+2}{2k+1}q^{2k+1}\\ &=q\sum_{k=0}^{\left\lfloor\frac{m+1}{2}\right\rfloor}\binom{m+2}{2k+1}q^{2k}\tag{6.1}\\ &\,\,\color{blue}{=q\sum_{k=0}^{\left\lfloor\frac{m+1}{2}\right\rfloor}\delta_k(m+2)\left(1-q^2\right)^k}\tag{6.2}\\ \end{align*}

Comment:

• In (6.1) we get the upper index since \begin{align*} 2k+1&\leq m+2\\ 2k&\leq m+1\\ k&\leq\left\lfloor\frac{m+1}{2}\right\rfloor \end{align*}

• In (6.2) we force the expression into an expansion of binomials $\left(1-q^2\right)^k$. This is admissible since we have the same terms $q^{2k}$ as in (6.1) when expanding the binomials and we can now set the coefficients $\delta_{k}(m+2)$ accordingly.

In the following we need to separate the first two summands with $k=0$ and $k=1$ and calculate $\delta_0$ and $\delta_1$ as follows.

• In order to calculate $\delta_0(m+2)$ we write (6.2) as \begin{align*} &\frac{1}{2}\left((1+q)^{m+2}-(1-q)^{m+2}\right)\\ &\qquad=q\delta_0(m+2) +q\sum_{k=1}^{\left\lfloor\frac{m+1}{2}\right\rfloor}\delta_k(m+2)\left(1-q^2\right)^k\tag{6.3} \end{align*} Evaluating left-hand side and right-hand side (6.3) at $q=1$ we obtain \begin{align*} \color{blue}{2^{m+1}=\delta_0(m+2)}\tag{6.4} \end{align*}
• In order to calculate $\delta_1(m+2)$ we divide (6.2) by $1-q^2$ and obtain \begin{align*} &\frac{\frac{1}{2}\,(1+q)^{m+2}-(1-q)^{m+2}}{\left(1-q^2\right)}\\ &\qquad=q\frac{\delta_0}{1-q^2}+\delta_1(m+2)+q\sum_{k=2}^{\left\lfloor\frac{m+1}{2}\right\rfloor}\delta_k(m+2)\left(1-q^2\right)^k\tag{6.4} \end{align*} We obtain $\delta_1(m+2)$ from (6.4) by calculating the limit $q\to 1$ and applying L'Hôpital's rule. Since $\delta_0(m+2)=2^{m+1}$ we obtain \begin{align*} \color{blue}{\delta_1(m+2)} &=\lim_{q\to 1}\frac{1}{2}\,\frac{(1+q)^{m+2}-(1-q)^{m+2}-2^{m+2}q}{1-q^2}\\ &=\lim_{q\to 1}\frac{1}{2}\,\frac{(m+2)(1+q)^{m+1}+(m+2)(1-q)^{m+1}-2^{m+2}}{-2q}\\ &=-(m+2)2^{m-1}+2^m\\ &\,\,\color{blue}{=-m2^{m-1}}\tag{6.5} \end{align*}

Combining (5.1), (5.2) and (6.2) we obtain \begin{align*} \color{blue}{\sum_{j=0}^{m-2}}&\color{blue}{c_j(m)\mathcal{F}_{m+1-j}\left(q^2\right)}\\ &=\frac{2^{\binom{m+1}{2}}q^2G(q)}{\left(1-q^2\right)^{m+2}}\,\frac{1}{2}\left((1+q)^{m+2}-(1-q)^{m+2}\right)\\ &=\frac{2^{\binom{m+1}{2}}qG\left(q\right)}{\left(1-q^2\right)^{m+2}} \sum_{k=0}^{\left\lfloor\frac{m+1}{2}\right\rfloor}\delta_k(m+2)\left(1-q^2\right)^k\\ &\,\,\color{blue}{=\frac{2^{\binom{m+1}{2}}q^2G\left(q^2\right)}{\left(1-q^2\right)^{m+3}} \sum_{k=0}^{\left\lfloor\frac{m+1}{2}\right\rfloor}\delta_k(m+2)\left(1-q^2\right)^k}\tag{7} \end{align*}

In the last step we use the identity \begin{align*} \color{blue}{G(q)}&=\prod_{n=1}^{\infty}\frac{1}{1-q^{2^n}}=\prod_{n=0}^{\infty}\frac{1}{1-q^{2^{n+1}}}\\ &=\frac{1}{1-q^2}\prod_{n=1}^{\infty}\frac{1}{1-q^{2^{n+1}}} \color{blue}{=\frac{1}{1-q^2}G\left(q^2\right)} \end{align*}

Another short break: Let's have a look at the identity (7).

• Here we have managed that $q$ occurs in squared form only, so that we can use identity (7) conveniently with $q$ instead of $q^2$.

• The factor in front of the sum is nearly the right-hand side of (2), nearly the right-hand side of the claimed induction step.

Induction step final part: We are on a promising path and will now apply the induction hypothesis (1) not once but even twice to get very close to the goal. We put $q$ instead of $q^2$ into (7) and obtain \begin{align*} \color{blue}{\sum_{j=0}^{m-2}}&\color{blue}{c_j(m)\mathcal{F}_{m+1-j}\left(q\right)}\\ &=\frac{2^{\binom{m+1}{2}}qG\left(q\right)}{\left(1-q\right)^{m+3}} \sum_{k=0}^{\left\lfloor\frac{m+1}{2}\right\rfloor}\delta_k(m+2)\left(1-q\right)^k\tag{$\to 7$}\\ &=\frac{2^{\binom{m+1}{2}}qG\left(q\right)}{\left(1-q\right)^{m+3}}\Big(2^{m+1}-m2^{m-1}(1-q)\\ &\qquad+\sum_{k=2}^{\left\lfloor\frac{m+1}{2}\right\rfloor}\delta_k(m+2)\left(1-q\right)^k\Big)\tag{8.1}\\ &=\frac{2^{\binom{m+2}{2}}qG\left(q\right)}{\left(1-q\right)^{m+3}} -m2^{m-1}\frac{2^{\binom{m+1}{2}}qG\left(q\right)}{\left(1-q\right)^{m+2}}\\ &\qquad+\sum_{k=2}^{\left\lfloor\frac{m+1}{2}\right\rfloor}\delta_k(m+2) \frac{2^{\binom{m+2}{2}}qG\left(q\right)}{\left(1-q\right)^{m+3-k}}\tag{8.2}\\ &=\frac{2^{\binom{m+2}{2}}qG\left(q\right)}{\left(1-q\right)^{m+3}} -m2^{m-1}\sum_{j=0}^{m-2}c_j(m)\mathcal{F}_{m-j}(q)\\ &\qquad+\sum_{k=2}^{\left\lfloor\frac{m+1}{2}\right\rfloor}\delta_k(m+2) 2^{\binom{m+1}{2}-\binom{m-k+2}{2}}\\ &\qquad\qquad\cdot\sum_{h=0}^{m-k-1}c_h(m-k+1)\mathcal{F}_{m-k-h+1}(q)\tag{8.3}\\ &\;\;\color{blue}{=\frac{2^{\binom{m+2}{2}}qG\left(q\right)}{\left(1-q\right)^{m+3}} -m2^{m-1}\sum_{j=1}^{m-2}c_{j-1}(m)\mathcal{F}_{m+1-j}(q)}\\ &\qquad\color{blue}{+\sum_{k=2}^{\left\lfloor\frac{m+1}{2}\right\rfloor}\delta_k(m+2) 2^{\binom{m+1}{2}-\binom{m-k+2}{2}}}\\ &\qquad\qquad\color{blue}{\cdot\sum_{j=k}^{m-1}c_{j-k}(m-k+1)\mathcal{F}_{m+1-j}(q)}\tag{8.4}\\ \end{align*} This is the fundamental step of the proof. All the transformations beforehand have been done in order to apply the induction hypothesis (twice) in (8.3). In fact here we are essentially done and have successfully mastered the job. We'll see why in a minute.

Comment:

• In (8.1) we separate the first two summands.

• In (8.2) we multiply out and see the first term is precisely the right-hand side of the induction step (2).

• In (8.3) we observe the second term is besides a factor $m2^{m-1}$ the left-hand side of the induction hypothesis and we are allowed to take the right-hand side of this assumed identity.

  We also use the strong induction for the term in the sum and apply the induction hypothesis with $m-k+1$, $k\geq 2$. Since here we apply (2) in the form \begin{align*} \sum_{h=0}^{m-k-1} c_h(m-k+1) \mathcal{F}_{m-k-h+1}(q) = \frac{2^{\binom{m-k+2}{2}}qG(q)}{(1-q)^{m-k+3}} \end{align*} Note, in order to apply this formula we have to compensate for the power of $2$ and we do this by dividing by $2^{\binom{m-k+2}{2}}$ resulting in $2^{\binom{m+2}{2}-\binom{m-k+2}{2}}$.

• In (8.4) we finally do some index transformations to alway get $\mathcal{F}_{m+1-j}$ as factor. In the right-most sum we use $k+h=j, k\geq 2, h\geq 0$.

Final part: We transform the identity (8.4) and put it into a form that makes it easy to compare it with the formula in induction step (2). We obtain \begin{align*} \color{blue}{\sum_{j=0}^{m-2}}&\color{blue}{c_j(m)\mathcal{F}_{m+1-j}\left(q\right)}\color{blue}{+m2^{m-1}\sum_{j=1}^{m-2}c_{j-1}(m)\mathcal{F}_{m+1-j}(q)}\\ &\color{blue}{-\sum_{k=2}^{\left\lfloor\frac{m+1}{2}\right\rfloor}\delta_k(m+2) 2^{\binom{m+1}{2}-\binom{m-k+2}{2}}}\\ &\qquad\color{blue}{\cdot\sum_{h=0}^{m-k-1}c_h(m-k+1)\mathcal{F}_{m-k-h+1}(q)}\\ &\,\,\color{blue}{=\frac{2^{\binom{m+2}{2}}qG\left(q\right)}{\left(1-q\right)^{m+3}}}\tag{9}\\ &\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\Box \end{align*} On the other hand we have (2) in the form \begin{align*} \color{blue}{\sum_{j=0}^{m-1} c_j(m+1) \mathcal{F}_{m-j+1}(q) = \frac{2^{\binom{m+2}{2}}qG(q)}{(1-q)^{m+3}}}\tag{10} \end{align*} Conclusion: The right-hand sides of (9) and (10) match. The coefficients $c_j(m+1)$ of $\mathcal{F}_{m-j+1}(q)$ can now be compared with the corresponding coefficients of $\mathcal{F}_{m-j+1}(q)$ in (9) and we see they are integral numbers, since they are integer multiples of $c_j(m)$ and $c_h(m-k+1)$ which are integral numbers according to the induction hypothesis.

We calculate the coefficients $c_j(m+1)$ of $\mathcal{F}_{m+1-j}, 0\leq j\leq m-1$

• $j=0$: Only the first sum in (9) contributes to $\mathcal{F}_{m+1}$. We have \begin{align*} c_0(m+1)\mathcal{F}_{m+1}(q)&=c_0(m)\mathcal{F}_{m+1}(q)\\ \color{blue}{c_{0}(m+1)}&\color{blue}{=c_0(m)=1} \end{align*}
• $j=1$: Only the first two sums in (9) contribute to $\mathcal{F}_{m}$. We have since $c_0(m)=1$ \begin{align*} c_1(m+1)\mathcal{F}_m(q)&=\left(c_1(m)+m2^{m-1}c_0(m)\right)\mathcal{F}_m(q)\\ &=\left(c_1(m)+m2^{m-1}\right)\mathcal{F}_m(q)\\ \color{blue}{c_{1}(m+1)}&\color{blue}{=c_1(m)+m2^{m-1}} \end{align*}
• $j=2$: The contribution to $\mathcal{F}_{m-1}$ is \begin{align*} &c_2(m+1)\mathcal{F}_{m-1}(q)\\ &\qquad=\left(c_2(m)+m2^{m-1}c_1(m)+\delta_2(m+2)2^{\binom{m+1}{2}-\binom{m}{2}}c_0(m-1)\right) \mathcal{F}_{m-1}(q)\\ &\color{blue}{c_2(m+1)}\color{blue}{=c_2(m)+m2^{m-1}c_1(m)+\delta_2(m+2)2^{\binom{m+1}{2}-\binom{m}{2}}} \end{align*} and finally
• $2<j_0\leq m+1$: We obtain by comparison of the coefficients of $\mathcal{F}_{m+1-j_0}(q)$ in (9) and (10): \begin{align*} \color{blue}{c_{j_0}(m+1)}&\color{blue}{=c_{j_0}(m)+m2^{m-1}c_{j_0-1}(m)}\\ &\qquad\color{blue}{-\sum_{k=2}^{\left\lfloor\frac{m+1}{2}\right\rfloor}\delta_k(m+2) 2^{\binom{m+1}{2}-\binom{m-k+2}{2}}} \end{align*}

Note: The proof of the divisibility properties of the $c_j(m+1), 0\leq j\leq m+1$ in Theorem 10.1 is not too hard and left to OP.