1

Let $b(n)$ be the binary partition function of $n$, i.e., the number of partition of $n$ for which all parts are the powers of two, and have properties $b(2n+1)=b(2n)$ and $b(2n)=b(n)+b(2n-2)$ for all positive integer $n$.

Prove that $b(n) \equiv 0 \pmod 2$ for all $n \ge 2$.

Proof: Clearly, $b(2)=b(3)=2 \equiv 0 \pmod 2$. Now, let $b(m) \equiv 0 \pmod 2$ for all $m \in [2,2n-1]$ where $n \ge 2.$ Then $$b(2n+1)=b(2n)=b(n)+b(2n-2) \equiv 0 \pmod 2,$$ since $n,2n-2 \in [2,2n-1]$. Now, extend the interval to be $[2,2n+1]$ and the result follows by induction.

My question is, how to solve the induction? Any ideas? Thanks in advanced.

1 Answers1

1

If I am not mistaken, you just need to prove $b(2n+1)=b(2n)$ and $b(2n)=b(2n-2)+b(n).$

$1.$ Let's first show $b(2n+1)=b(2n)$.

Notice that every partition of $2n+1$ "definitely" contains $1$. Remove $1$, and now we have a partition of $2n$; hence $b(2n)\ge b(2n+1)$. Moreover, out of every partition of $2n$ we can simply obtain a partition of $2n+1$ (just by adding $1$); hence $b(2n)\le b(2n+1)$. So, $b(2n)=b(2n+1).$

$2.$ Now, we show $b(2n)=b(2n-2)+b(n)$, or "equivalently", $b(2n)=b(2n-1)+b(n).$

Consider a partition of $2n$. Either it contains $1$ or it doesn't contain $1.$ If it contains $1$, then remove $1$, and we have a partition of $2n-1$. If it doesn't contain $1$ divide the numbers of the partition by $2$, and now we have a partition of $n$. Hence, $b(2n)\le b(2n-1)+b(n)$.

Conversely, out of every partition of $n$ (by multiplying by $2$) and every partition of $2n-1$ (by adding $1$), we can obtain a "distinct" partition of $2n$. Hence $b(2n)\ge b(2n-1)+b(n)$. Therefore $b(2n)=b(2n-1)+b(n)$.

Reza Rajaei
  • 5,183
  • Pardon, but I still didn't get this one. Why is it suffices? How can we conclude that $b(n)$ is even from there? –  Jan 05 '23 at 10:37
  • you know that $b(2)$ is even hence $b(3)$ is even because we proved that $b(2n+1)=b(2n)$, and $b(4)$ is even as well because $b(2n)=b(2n-2)+b(n)$. Notice that we are using strong induction and sum of two even numbers is even. – Reza Rajaei Jan 05 '23 at 10:43
  • Could you give the details for the strong induction, please? I still didn't get it yet,, –  Jan 05 '23 at 12:45
  • Indeed, we assume the claim is true for all numbers less than $n$. By the relations, we have shown that $b(n)$ can be written as the sum of some previous numbers. Since all the previous numbers are even, hence the claim is true for $n$. Actually, that is why we try to write each number based on the previous numbers, whether it is even or odd. – Reza Rajaei Jan 05 '23 at 15:13
  • Aaaaah I see. Finally, I got this. Thanks for the detailed explanation. –  Jan 06 '23 at 01:41