加算と2倍のレパートリーのなす数の総数

$\overline{X}_{n+1}$の元は、$\overline{X}_n$の元$(x_1, x_2 \cdots, x_k)$から次の2通りで構成されます。

1. $(x_1+1,x_2, \cdots, x_k)$
2. $(1,x_1, x_2, \cdots, x_k)$

この構成法により$\overline{X}_{n+1}$の元は全てつくされます。
この操作を$X_n, X_{n+1}$で考えると、(1)は$x+1$、(2)は$2x+1$に対応しています。これにより、補題が示されます。

数学的帰納法で証明します。
$n=1$のとき、$X_1=\lbrace 1\rbrace, S_1=\lbrace 2\rbrace$より明らかです。
$n$のときに成り立つと仮定し、$n+1$のときを考えます。
補題1より、$X_{n+1}$の元$y$は$X_n$の元$x$を用いて$x+1$または$2x+1$と表されます。
帰納法の仮定より、$x+1$は$S_n$の元です。これにより、$x+2$と$2x+2$は$S_{n+1}$の元です。
$x+2=(x+1)+1,\ 2x+2=(2x+1)+1$
であるため、$X_{n+1} \rightarrow S_{n+1}, \ y \mapsto y+1$は全単射を与えることがわかります。
以上より、任意の$n$について主張が示されました。

$n=1,2$のときは明らかです。
$n \geq 3$のときを考えます。そのために$\overline{X}_n$を次の3つに分解します：
$(x_1, \cdots, x_k)$を$\overline{X}_n$の元としたとき、
(1) $x_1＝1$である元全体の集合。これは$(1, \boldsymbol{x}), \boldsymbol{x} \in \overline{X}_{n-1}$と表されるため、$\overline{X}_{n-1}$の元と1対1対応があります。
(2) $x_1＝2$である元全体の集合。これは$(2, \boldsymbol{x}), \boldsymbol{x} \in \overline{X}_{n-2}$と表されるため、$\overline{X}_{n-2}$の元と1対1対応があります。
(3) $x_1 \geq 3$である元全体の集合$\overline{Y}_n$。
これにより$X_n$の元は$\overline{X}_{n-1},\overline{X}_{n-2},\overline{Y}_n$の3つの集合の元から構成されることがわかります。

$\overline{X}_n$の分解法から、$X_n$の元において$\overline{X}_{n-1}$由来の元は$X_{n-1} \rightarrow X_n, \ x \mapsto 2x+1$、$\overline{X}_{n-2}$由来の元は$X_{n-2} \rightarrow X_n, \ x \mapsto 2x+2$で与えられます。
前者は奇数、後者は偶数であるため、これらの像に重複する数字は存在しません。
つまり$X_n$の元のうち、$\overline{X}_{n-1}$からくる元は$a_{n-1}$個、$\overline{X}_{n-2}$からくる元は$a_{n-2}$個存在することがわかりました。
後は$\overline{Y}_n$からくる元のうち、重複しない元が$n-2$個であることを示せば終了です。

さて$\overline{Y}_n$をさらに次の2つに分解します：
$(y_1, \cdots, y_k)$を$\overline{Y}_n$の元としたとき、
[1] $k=1,2$の元全体からなる集合$\overline{Y}^1_n$。
[2] $k \geq 3$の元全体からなる集合$\overline{Y}^2_n$。

前者は$\overline{Y}^1_n = \lbrace (n),(3,n-3),\cdots, (n-1,1) \rbrace$であり、全部で$n-2$個の元からなります（ただし、$n=3$のときは$(3)$と$(3,0)$を同一視します）。
この集合からくる$X_n$の元は、$\overline{X}_{n-1},\overline{X}_{n-2}$由来の元と重複しません。
なぜなら$\overline{Y}^1_n$の重み付き和による像$Y^1_n$は$Y^1_n = \lbrace n, n+1,\cdots , 2n-3\rbrace$であり、最大の数は$2n-3$です。
一方$X_{n-2}$の最小の数は$n-2$であるため、$\overline{X}_{n-2}$由来の元の最小値は$2n-2$です。
これにより$X_n$の元のうち、$\overline{Y}^1_n$由来の元が$n-2$個存在することがわかりました。

最後に$\overline{Y}^2_n$由来の元は、全て$\overline{X}_{n-1},\overline{X}_{n-2}$由来の元と重複することを示します。
それは次の等式から示されます：
$(x_1, \cdots, x_k) \in \overline{X}_n,\ x_1 \geq 3$に対し、
$x_1 + 2x_2 + 4x_3 = (x_1-2) + 2(x_2 + 3) + 4(x_3 - 1)$
$$x_1 + 2x_2 + \sum^{k-2}_{i=3}2^{i-1}x_i + 2^{k-2}x_{k-1} + 2^{k-1}x_k = (x_1-2) + 2(x_2 + 1) + \sum^{k-2}_{i=3}2^{i-1}x_i + 2^{k-2}(x_{k-1}+2) + 2^{k-1}(x_k -1)$$
が成り立つため、$(x_1, x_2, x_3)$と$(x_1-2, x_2 +3, x_3 -1)$、$(x_1, x_2, \cdots, x_{k-1}, x_k)$と$(x_1 - 2, x_2 + 1, \cdots, x_{k-1} + 2, x_k - 1)$の重み付き和はそれぞれ等しくなります。
つまり$k \geq 3, x_1 \geq 3$であるとき、この操作を繰り返すことによって重み付き和の値が等しい$x_1 = 1$または$x_1 = 2$である$\overline{X}_n$を見つけることができます。
このことは$\overline{Y}^2_n$由来の元は全て$\overline{X}_{n-1},\overline{X}_{n-2}$由来の元と重複することを意味します。

以上より、$X_n$の元は$\overline{X}_{n-1},\overline{X}_{n-2},\overline{Y}^1_n$からくる元で全てつくされるため、$a_n = a_{n-1} + a_{n-2} + n-2 \ (n \geq 3)$が示されました。