(Mid-term training Valbonne 2019 group B)

Let $n \geqslant 1$ be an integer. We have $n$ cubes with sides $1, 2, \ldots, 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 $l$ with $l \geqslant k-2$. How many such different stackings exist?
Let's prove by induction that for $n \geqslant 2$ the property $P(n)$ "there exist $3^{n-2} \times 2$ such stackings" is true.

Initialization: For $n=2$, the 2 possible stackings satisfy the required constraint.

Hereditary: Suppose that the property $P(n)$ is true for $n \geqslant 2$. 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, \ldots, n$ as well as a position where to insert the $(n+1)$-th cube.

Indeed, if we are given a stacking conforming to $n+1$ cubes and we remove the one numbered $n+1$, the only potential change in neighbors concerns the cube ($s'$ exists) which is above $n+1$ and it ends up above a cube of value at least $n-1$, so the obtained configuration is conforming.

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-2} \times 2 = 3^{(n+1)-2} \times 2$ possibilities, which shows the property $P(n+1)$.

By induction, we conclude that there exist $3^{n-2} \times 2$ such stackings for $n$ cubes for all $n \geqslant 2$.

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

We note in this exercise that the hereditary property and thus a formula is sometimes valid only from a certain rank (here 2), but it is important not to forget to handle the other cases (here $1$)!