Let $n \geqslant 1$ be an integer. We have $n$ cubes with sides $1, 2, \cdots, n$. We want to stack them in a certain order, such that a cube of side $k$ can only be placed on a cube of side $\ell$ with $\ell \geqslant k-2$. How many such different stackings exist?
Let's prove by induction that for $n \geqslant 3$ there are $3^{n-1} \times 2$ such stackings. For $n=3$, the 6 possible stackings satisfy the required constraint.

Suppose the result is true for $n \geqslant 3$. Giving a stacking with $n+1$ cubes satisfying the conditions of the statement is equivalent to giving a stacking with the cubes of sides $1,2, \cdots, n$ and a position where to insert the $(n+1)$-th cube. The $(n+1)$-th cube can only be placed above a cube of side $n$ or $n-1$, or at the very bottom of the stack. Thus, by the induction hypothesis, there are $3 \times 3^{n-1} \times 2$ possibilities. By induction, we conclude that there are $3^{n-1} \times 2$ such stackings for $n$ cubes for all $n \geqslant 3$.

For $n=1$ there is one stacking, and for $n=2$ there are two, and all such stackings satisfy the required condition.