Let $n>0$ be an integer. We have a two-pan balance and $n$ weights, whose weights are $2^{0}, 2^{1}, \ldots, 2^{n-1}$. We want to place these $n$ weights on the balance one by one in such a way that the right pan is never heavier than the left pan. At each step, we choose one of the weights that have not yet been placed on the balance, and place it either on the left or the right pan, until all the weights are on the balance. Determine how many ways there are to do this.
Damásdi Gábor's solution. $N$ weights can be placed on the scale in $1 \cdot 3 \cdot 5 \cdot \ldots \cdot(2 n-1)$ ways. We prove this by induction: for $n=1$ and $n=2$, this is easily verifiable. Suppose that for some $n$, there are $1 \cdot 3 \cdot 5 \cdot \ldots \cdot(2 n-1)$ ways to place the weights. We need to show that for $n+1$ weights, there are $(2 n+1)$ times as many ways as for $n$ weights.

Take any placement of the $n$ weights. We create a placement for $n+1$ weights in the following way: double the mass of each element, and then insert an additional step where we place a weight of mass 1.

Doubling the masses gives us the weights of masses $2, 4, \ldots, 2^n$, and we insert the weight of mass 1, so this is indeed a placement of $n+1$ weights. Doubling does not alter the order of magnitudes. Since the masses are even after doubling, the weight of mass 1 only ruins the placement if we insert it at the beginning and place it on the right side. Therefore, except for one case, we can place the weight of mass 1 on either side at any time, thus creating $2 n+1$ placements for $n+1$ weights. It remains to show that every placement for $n+1$ weights can be reached this way and that no placement can be reached from two different placements of $n$ weights.

Every placement for $n+1$ weights can be reached, since we can also describe the method in reverse: take a placement for $n+1$ weights. Remove the step where the weight of mass 1 is placed, and divide the masses by 2. This gives us a placement for $n$ weights from which the original placement for $n+1$ weights can be reached.

If we start from different placements, the weights of masses $2, 4, \ldots, 2^n$ will be in a different order in the placement for $n+1$ weights, meaning that each placement can only be reached in one way.

We have created $2 n+1$ placements for $n+1$ weights from each placement, thus proving the induction.