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.