An interesting identity regarding partitions of $m$ into powers of two This question appeared in an exam I was giving-

Suppose we have $n$ balls and we place them in a sequence of bins as
follows. At least one ball is put into the first bin, and each
successive bin has at least as many balls as all the previous bins
combined. This process is continued until all the balls have been
placed into bins.
Prove that the number of ways of doing this is the same as the number
of partitions of n into powers of 2, not necessarily distinct.
Note: $1=2^0$ is also considered a power of two.

I think this identity is superb. It breaks my brains to even think that the two processes are equivalent. But, that doesn't help me to solve it.
All I can think of is that the tightest case of putting balls into bins is $1,1,2,4,8,\dots$ which is the sequence of powers of two. Also, I know that the number of partitions of $m$ into powers of two is the coefficient of $x^m$ in the product
\begin{equation*}
\prod_{n=0}^\infty \sum_{j=0}^{\infty} x^{2^n j}
\end{equation*}
But, none of these proved useful. Any help would be appreciated.
 A: Hint. Let $b_i$ be the number of balls in the $i$th bin for $i=1,\dots, N$ where $N$ is the total number of bins. Let $x_i=b_i-\sum_{j=1}^{i-1}b_j$ which is non negative by assumption. Then
$$\begin{cases}
b_1=x_1\\
b_1+b_2=b_1+(b_1+x_2)=2b_1+x_2=2x_1+x_2\\
b_1+b_2+b_3=b_1+b_2+(b_1+b_2+x_3)=2(b_1+b_2)+x_3=4x_1+2x_2+x_3\\
\dots
\end{cases}$$
and therefore $b_1+b_2+\dots+b_N=n$ if and only if
$$2^{N-1}x_1+2^{N-2}x_2+\dots+x_N=n \qquad (1).$$
So the number of ways of doing the given process is equal to the number of nonnegative integer solutions of equation (1).
A: Hint:
Show in both cases that if $a_n$ is the number of such partitions:

*

*$a_0=1$

*$a_{2k}=a_{2k-2}+a_k$

*$a_{2k+1}=a_{2k}$
For the second equation

*

*in your first case, either take a partition of $2k-2$ and add $2$ to the largest existing bin, or take a partition of $k$ and add a new bin with $k$.

*in your second case, either take a partition of $2k-2$ and add two $1$ parts, or take a partition of $k$ and double each part

For the third equation

*

*in your first case, take a partition of $2k$ and add $1$ to the largest existing bin

*in your second case, take a partition of $2k$ and add one $1$ part

