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.
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)$.