2.2.22

順番に見ていくと

$$1$$

$$2 = 1+1$$

$$3 = 1+2 = 2+1 = 1+1+1$$

$$4 = 1+3 = 2+2 = 1+1+2 = 3+1 = 1+2+1 = 2+1+1 = 1+1+1+1$$

となり$$s(n) = 2^{n-1}$$と予想がつくのでこれを示そう。

これは漸化式の形で表せば$$s(n+1) = s(n) * 2$$となるので$$n$$の 表し方それぞれからちょうど2つずつ$$n+1$$の表し方を生やせば良い。 そこで$$n=a_1+\cdots+a_k$$ (ただし$$a_1,a_2,\ldots > 0$$)という表し方に対して

• $$n+1 = a_1 + \cdots + a_k + 1$$, (末尾に1を追加)
• $$n+1 = a_1 + \cdots + (a_k+1)$$, 　(末尾の要素に1を足す)

という2通りの$$n+1$$の表し方が作れることに着目する。 $$A(n)$$を数列$$\langle a_1, \ldots, a_k\rangle$$で和が$$n$$になるもののの集合とする。 $$A(n)$$から1つ目の操作でできる数列の集合を$$B(n)$$, 2つ目の操作でできる集合を$$C(n)$$としたとき、$$A(n+1) = B(n) \cup C(n)$$かつ$$B(n) \cap C(n) = \emptyset$$が示せれば十分である。

後者は$$B(n)$$の末尾の要素はすべて1であり、$$C(n)$$の末尾は2以上であることから明らかである。 前者は$$A(n+1) \supseteq B(n) \cup C(n)$$は明らか ($$A(n+1)$$は和が$$n+1$$になるすべての数列)。 逆に$$\textit{a} = \langle a_1,\ldots,a_k\rangle \in A(n+1)$$のとき$$a_k = 1$$ならば $$\langle a_1,\ldots,a_{k-1}\rangle \in A(n)$$なので$$\textit{a} \in B(n)$$である。 一方$$a_k>1$$ならば$$\langle a_1,\ldots,(a_k-1)\rangle \in A(n)$$なので$$\textit{a} \in C(n)$$であり示せた。