Croatian Mathematical Olympiad

Let $k_n = |\mathcal{K}_n|$, $j_n = \sum_{a \in \mathcal{K}_n} J(a)$ and $d_{n+1} = \sum_{a \in \mathcal{K}_{n+1}} a_2$. We need to prove that $j_n = d_{n+1}$ for every positive integer $n$. We prove the statement by complete mathematical induction.

It is clear that $j_1 = 1 = d_2$ and $j_2 = 1 = d_3$.

Let us assume that $n \ge 2$ is a positive integer such that $j_i = d_{i+1}$ for all $i \le n$.

First, we note that $d_{n+2} = k_n + d_n$. Indeed, for each cryptogram $a$ of $n+2$ for which $a_2 > 0$, we decrease $a_2$ by 1 and obtain a cryptogram of $n$. It follows that $d_{n+2}$ is equal to the number of cryptograms of $n$ increased by $d_n$.

Let us also prove that $j_{n+1} = k_n + d_n$. By the induction assumption, we need to prove that $j_{n+1} = k_n + j_{n-1}$.

We partition all cryptograms of $n + 1$ into two disjoint subsets: set A consisting of cryptograms having the last non-zero element equal to 1, and set B consisting of cryptograms having the last non-zero element greater than 1.

Cryptograms in A are in bijection with the cryptograms of $n$. Indeed, we can delete the last non-zero element of a cryptogram in A and add 1 to the element just in front of it. Conversely, for each cryptogram of $n$, we decrease the last non-zero element and add 1 to the element right after it.

It remains to prove that the set B contains in total $j_{n-1}$ ones. Let $a \in B$ be such that $a_i = 1$ for some $i \in \{1, 2, \dots, n\}$. Let $a_i = 0$ and let us increase $a_{i-1}$ by 1. If $i = 1$, let $a_1 = 0$. Furthermore, let $\ell > i$ be the smallest index such that $a_\ell > 0$, which exists because the last non-zero element is not 1. We decrease $a_\ell$ by 1 and increase $a_{\ell-1}$ by 1. Note that we obtain a cryptogram of $n-1$ which has 1 at the index $\ell-1$. This shows that each one occurring in B corresponds bijectively to a one in the set of cryptograms of $n-1$.

Finally, $j_{n+1} = k_n + j_{n-1}$ and the proof is finished.