九州大学 1996年度 前期日程 第2次学力試験理系数学 第5問

(1)
語 $W$ を $r$ 回繰り返した語を $W^r$ と書く。次の形を示す。 $$C_{2m+1}=(110{)}^{(4^m-1)\mathrm{/}3}1(m\geqq 1)$$ $$C_{2m}=(101{)}^{2(4^{m-1}-1)\mathrm{/}3}10(m\geqq 1)$$ である。

実際、$m=1$ では $$C_2=10=(101{)}^{0}10,C_3=1101=(110{)}^{1}1$$ で成り立つ。

いま $$C_{2m}=(101{)}^{s}10,C_{2m+1}=(110{)}^{r}1$$ と書けているとする。ただし $$s={\displaystyle \frac{2(4^{m-1}-1)}{3}},r={\displaystyle \frac{4^m-1}{3}}$$ である。

まず $$C_{2m+2}=C_{2m}{C}_{2m+1}{C}_{2m}=(101{)}^{s}10(110{)}^{r}1(101{)}^{s}10$$ である。中央の $10(110{)}^{r}1=(101{)}^{r+1}$ を用いると $$C_{2m+2}=(101{)}^{2s+r+1}10$$ となる。指数は $$2s+r+1={\displaystyle \frac{4(4^{m-1}-1)+(4^m-1)+3}{3}}={\displaystyle \frac{2(4^m-1)}{3}}$$ であるから、偶数番の形が次へ進む。

次に、いま得た $$C_{2m+2}=(101{)}^{s^{\mathrm{\prime }}}10,s^{\mathrm{\prime }}={\displaystyle \frac{2(4^m-1)}{3}}$$ を用いると $$C_{2m+3}=C_{2m+1}{C}_{2m+2}{C}_{2m+1}=(110{)}^{r}1(101{)}^{s^{\mathrm{\prime }}}10(110{)}^{r}1$$ である。中央の $$1(101{)}^{s^{\mathrm{\prime }}}10=(110{)}^{s^{\mathrm{\prime }}+1}$$ を用いると $$C_{2m+3}=(110{)}^{2r+s^{\mathrm{\prime }}+1}1$$ となる。指数は $$2r+s^{\mathrm{\prime }}+1={\displaystyle \frac{2(4^m-1)+2(4^m-1)+3}{3}}={\displaystyle \frac{4^{m+1}-1}{3}}$$ である。よって二つの形は数学的帰納法で示された。

したがって、$n$ が奇数のときは $C_n=(110{)}^{r}1$ である。最後の 1 個を取り去ると $(110{)}^r$、最初の 1 個を取り去ると $(101{)}^r$ となり、これは三文字語 $110$ の循環した語の繰り返しである。

また、$n$ が偶数のときは $C_n=(101{)}^{r}10$ である。最後の 2 個を取り去ると $(101{)}^r$、最初の 2 個を取り去ると $(110{)}^r$ となり、これも同じ三文字語の循環した語の繰り返しである。よって題意は示された。

(2) $$C_n=C_{n-2}{C}_{n-1}{C}_{n-2}$$ であるから、0 の個数 $a_n$ と 1 の個数 $b_n$ はそれぞれ $$a_n=a_{n-1}+2a_{n-2},b_n=b_{n-1}+2b_{n-2}$$ を満たす。初期値は $$a_1=0,a_2=1,b_1=1,b_2=1$$ である。

漸化式 $x_n=x_{n-1}+2x_{n-2}$ の形から、解は $2^n$ 型と $(-1{)}^n$ 型の和になる。初期値を代入すると $$a_n={\displaystyle \frac{1}{3}}\{2^{n-1}-(-1{)}^{n-1}\}$$ であり、また $$b_n={\displaystyle \frac{1}{3}}\{2^n+(-1{)}^{n-1}\}$$ である。実際、どちらも同じ漸化式を満たし、$n=1,2$ の初期値にも一致する。

したがって $${\displaystyle \frac{a_n}{b_n}}={\displaystyle \frac{2^{n-1}-(-1{)}^{n-1}}{2^n+(-1{)}^{n-1}}}$$ である。$n\to \mathrm{\infty }$ で $(-1{)}^{n-1}$ は $2^n$ に比べて無視できるので $$\underset{n\to \mathrm{\infty }}{\lim }{\displaystyle \frac{a_n}{b_n}}={\displaystyle \frac{1}{2}}$$ である。

(1) で得られる三文字周期の具体形を、そのまま0と1の個数の比に使う。個数の漸化式を解かず、奇数番・偶数番それぞれで端に付く高々2文字の影響が消えることから極限を求める。

(1)
次の二式を同時に帰納法で示す。$$C_{2m+1}=(110{)}^{(4^m-1)\mathrm{/}3}1,C_{2m}=(101{)}^{2(4^{m-1}-1)\mathrm{/}3}10.$$$m=1$ では $C_2=10$、$C_3=1101$ で成立する。二式を仮定して$$C_{2m+2}=C_{2m}{C}_{2m+1}{C}_{2m},C_{2m+3}=C_{2m+1}{C}_{2m+2}{C}_{2m+1}$$へ代入する。境界で$$10(110{)}^{r}1=(101{)}^{r+1},1(101{)}^{s}10=(110{)}^{s+1}$$となるため、指数をまとめれば上の二式の $m+1$ の場合が得られる。

奇数番は最初または最後の1文字を除くと $(110{)}^r$ またはその循環 $(101{)}^r$、偶数番は最初または最後の2文字を除くと $(110{)}^r$ または $(101{)}^r$ となる。よって題意が示された。

(2)
奇数番を $C_{2m+1}=(110{)}^{r}1$ と書けば$$a_{2m+1}=r,b_{2m+1}=2r+1.$$偶数番を $C_{2m}=(101{)}^{s}10$ と書けば$$a_{2m}=s+1,b_{2m}=2s+1.$$$m\to \mathrm{\infty }$ で $r,s\to \mathrm{\infty }$ だから、どちらの部分列でも$${\displaystyle \frac{a_n}{b_n}}⟶{\displaystyle \frac{1}{2}}\mathrm{.}$$したがって$${\displaystyle \underset{n\to \mathrm{\infty }}{\lim }{\displaystyle \frac{a_n}{b_n}}={\displaystyle \frac{1}{2}}}\mathrm{.}$$